Codevs2018 反病毒软件

2018 反病毒软件

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond

 查看运行结果

题目描述 Description

其实这个“反病毒软件”(Anti-Virus SOFTware),是相关部门应对H9N7人流感研发的。

相关部门的监控范围里只有N个城市,从1到N编号。初始时,这些城市都没有任何病例出现。由于在某一个城市出现过多的病例不太好,相关部门需要随时知道,从X到Y(含X和Y)这些城市当中,病例最多的城市与病例第二多的城市的病例数之差为多少。

一共会有Q个事件发生,具体见【输入】。

输入描述 Input Description

第一行为两个整数N,Q,以空格隔开。

接下来Q行,每行代表一个事件。第i+1行代表第i个事件,这一行有三个整数Ci,Xi,Yi,其中Ci为1或2。如果Ci为1,表示在城市Xi又新发现了Yi个病例;如果Ci为2,表示询问从Xi到Yi,病例最多的城市与病例第二多的城市的病例数之差为多少。

输出描述 Output Description

对于输入中的每一个Ci=2的事件,输出一行,即询问的结果。

样例输入 Sample Input

4

2 1 4

1 2 3

2 2 4

1 3 2

2 1 3

1 2 2

2 1 4

样例输出 Sample Output

0

3

1

3

数据范围及提示 Data Size & Hint

【样例说明】

初始时各个城市的病例数为{0,0,0,0}。

从1到4最多的病例数为0,第二多的病例数为0,差值为0,输出0。

城市2发现了3个新病例,病例数变为{0,3,0,0}。

从2到4最多的病例数为3,第二多的病例数为0,差值为3,输出3。

城市3发现了2个新病例,病例数变为{0,3,2,0}。

从1到3最多的病例数为3,第二多的病例数为2,差值为1,输出1。

城市2发现了2个新病例,病例数变为{0,5,2,0}。

从1到4最多的病例数为5,第二多的病例数为2,差值为3,输出3。

【数据规模与约定】

对于40%的数据,N,Q≤1000。

对于100%的数据,2≤N,Q≤100000,且对于每一个Ci=2,满足Xi<Yi。

分类标签 Tags 点此展开 

题解:首先对这个出题人表示严重吐槽——假如存在两个并列第一多的城市,那么不是不应该第一第二都取这个值么?我这么做结果WA得很惨,然后我再加了个等号让第一第二可以取一样的值,然后就AC了!?!?对这题的题目表述表示不解。。。汗

不难搞的线段树,点修改的话该怎么干怎么干,然后区间的话主要就是个核心运算——merge操作,别的没了

 1 type vet=record
 2                 a1,a0:longint;
 3       end;
 4 var
 5    i,j,k,l,m,n:longint;
 6    a2:vet;
 7    a:array[0..500050] of vet;
 8    d:array[0..500050] of longint;
 9    c:array[0..10] of longint;
10 procedure swap(var x,y:longint);inline;
11           var z:longint;
12           begin
13                z:=x;x:=y;y:=z;
14           end;
15 function max(x,y:longint):longint;inline;
16          begin
17               if x>y then max:=x else max:=y;
18          end;
19 function min(x,y:longint):longint;inline;
20          begin
21               if x<y then min:=x else min:=y;
22          end;
23 
24 function merge(a2,a3:vet):vet;inline;
25           var i,j,k,l:longint;a4:vet;
26           begin
27                c[1]:=a2.a0;c[2]:=a2.a1;
28                c[3]:=a3.a0;c[4]:=a3.a1;
29                a4.a0:=0;a4.a1:=0;
30                for i:=1 to 4 do
31                    begin
32                         if c[i]>=a4.a0 then
33                            begin
34                                 a4.a1:=a4.a0;
35                                 a4.a0:=c[i];
36                            end
37                         else 
38                             begin
39                                 if (c[i]>a4.a1) and (c[i]<a4.a0) then a4.a1:=c[i];
40                             end;
41                    end;
42                exit(a4);
43           end;
44 procedure built(z,x,y:longint);inline;
45           begin
46                if x=y then
47                   d[x]:=z
48                else
49                    begin
50                         built(z*2,x,(x+y) div 2);
51                         built(z*2+1,(x+y) div 2+1,y);
52                    end;
53                a[z].a0:=0;a[z].a1:=0;
54           end;
55 procedure doit(x,y:longint);
56           begin
57                x:=d[x];
58                a[x].a0:=a[x].a0+y;a[x].a1:=0;
59                while x>1 do
60                      begin
61                           a[x div 2]:=merge(a[x],a[x+1-2*(x mod 2)]);
62                           x:=x div 2;
63                      end;
64           end;
65 function cal(z,x,y,l,r:longint):vet;
66          var a3,a2:vet;
67          begin
68               if l>r then
69                  begin
70                       a2.a0:=0;
71                       a2.a1:=0;
72                       exit(a2);
73                  end;
74               if (x=l) and (y=r) then exit(a[z]);
75               exit(merge(cal(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2)),cal(z*2+1,(x+y) div 2+1,y,max(l,(x+y) div 2+1),r)));
76          end;
77 begin
78      readln(n);
79      built(1,1,n);
80      while not(eof) do
81          begin
82               readln(j,k,l);
83               case j of
84                    1:doit(k,l);
85                    2:begin
86                           a2:=cal(1,1,n,k,l);
87                           writeln(a2.a0-a2.a1);
88                    end;
89               end;
90          end;
91      readln;
92 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码代码的陈同学

异常处理的反模式

异常设计实践 中有位读者评论:又记录日志又抛异常反模式设计。其实我并不知道反模式,本文是对于反模式的学习整理,数据都来自参考资料。

19950
来自专栏IMWeb前端团队

写给前端专家的一封公开信:关于分号(翻译)

本文作者:IMWeb frankfang 原文出处:IMWeb社区 未经同意,禁止转载 原文 Sean Silva 给我发来一封信: 我最近在浏览你...

20270
来自专栏Android机动车

Java 基础(一)——重新理解面向对象

如何利用对象完成真正有用的工作呢?必须有一种办法能向对象发出请求,令其做一些实际的事情。接口就是对一个对象的行为进行规范,使对象具有做某些事情的能力。

8710
来自专栏玄魂工作室

CTF实战30 CTF题目练习和讲解五(讲解部分)

该培训中提及的技术只适用于合法CTF比赛和有合法授权的渗透测试,请勿用于其他非法用途,如用作其他非法用途与本文作者无关

25330
来自专栏圣杰的专栏

DDD理论学习系列(7)-- 值对象

? 1.引言 提到值对象,我们可能立马就想到值类型和引用类型。而在C#中,值类型的代表是strut和enum,引用类型的代表是class、interface、...

31570
来自专栏Java后端技术栈

开发中我们需要遵循的几个设计原则!

在软件开发中,前人对软件系统的设计和开发总结了一些原则和模式, 不管用什么语言做开发,都将对我们系统设计和开发提供指导意义。本文主要将总结这些常见的原则和具体阐...

10320
来自专栏申龙斌的程序人生

零基础学编程009:只显示2位小数

我们仍要继续解决这个问题:如何用Python打印这篇枯燥的《复利数据表》? (1+0.01) ^ 1 = 1.01 (1+0.01) ^ 2 = 1.02 (...

32470
来自专栏游戏杂谈

字符串比较

网上看到有人也说是他遇到的一道笔试题,那我想这道题目其实还考过很多人。只不过当时是给我笔让我写出来,一下子懵住了,没缓过神来。写的算法时间复杂度为O(n*m),...

29420
来自专栏数据结构与算法

2017.5.20欢(bei)乐(ju)赛解题报告

预计分数:100+20+50=first 实际分数:20+0+10=gg 水灾(sliker.cpp/c/pas) 1000MS  64MB 大雨应经下了几天雨...

32770
来自专栏牛客网

听说有人想要爱奇艺面经?

24400

扫码关注云+社区

领取腾讯云代金券