首页 > 代码库 > BZOJ1058: [ZJOI2007]报表统计
BZOJ1058: [ZJOI2007]报表统计
1058: [ZJOI2007]报表统计
Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 1738 Solved: 606
[Submit][Status]
Description
小Q的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小Q希望可以帮妈妈分担一些工作，作为她的生日礼物之一。经过仔细观察，小Q发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。在最开始的时候，有一个长度为N的整数序列，并且有以下三种操作： INSERT i k 在原数列的第i个元素后面添加一个新元素k； 如果原数列的第i个元素已经添加了若干元素，则添加在这些元素的最后（见下面的例子） MIN_GAP 查询相邻两个元素的之间差值（绝对值）的最小值 MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值（绝对值） 例如一开始的序列为 5 3 1 执行操作INSERT 2 9将得到： 5 3 9 1 此时MIN_GAP为2，MIN_SORT_GAP为2。 再执行操作INSERT 2 6将得到： 5 3 9 6 1 注意这个时候原序列的第2个元素后面已经添加了一个9，此时添加的6应加在9的后面。这个时候MIN_GAP为2，MIN_SORT_GAP为1。于是小Q写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？
Input
第一行包含两个整数N，M，分别表示原数列的长度以及操作的次数。第二行为N个整数，为初始序列。接下来的M行每行一个操作，即“INSERT i k”，“MIN_GAP”，“MIN_SORT_GAP”中的一种（无多余空格或者空行）。
Output
对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令，输出一行答案即可。
Sample Input
3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
Sample Output
2
2
1
2
1
HINT
对于30%的数据，N ≤ 1000 , M ≤ 5000 对于100%的数据，N , M ≤500000 对于所有的数据，序列内的整数不超过5*108。
Source
最近怎么老是遇见这种剧恶心的题目。。。这是专门恶心pascal选手呢吧？
。。。。。。。。。。。。。。。
写一个 树状数组计算当前插入位置，
写一个splay维护相邻的最小值，
再写一个treap求前驱、后继，
打一个快排预处理第一次的答案
。。。。。。。。。。。。。。。。
我写出来连变量名都不想写了。。。哪天想受虐的再过来调吧。。。
代码“
1 var 2 function min(x,y:longint):longint; 3 begin 4 if x<y then exit(x) else exit(y); 5 end; 6 function max(x,y:longint):longint; 7 begin 8 if x>y then exit(x) else exit(y); 9 end; 10 procedure sort(l,r:longint); 11 var i,j,x,y:longint; 12 begin 13 i:=l;j:=r;x:=b[(i+j)>>1]; 14 repeat 15 while b[i]<x do inc(i); 16 while b[j]>x do dec(j); 17 if i<=j then 18 begin 19 y:=b[i];b[i]:=b[j];b[j]:=y; 20 inc(i);dec(j); 21 end; 22 until i>j; 23 if i<r then sort(i,r); 24 if j>l then sort(l,j); 25 end; 26 procedure pushup(x:longint); 27 var l,r:longint; 28 begin 29 s[x]:=s[c[x,0]]+s[c[x,1]]+1; 30 mi[x]:=min(pre[x],min(mi[c[x,0]],mi[c[x,1]])); 31 end; 32 procedure rotate(x:longint;var k:longint);inline; 33 var y,z,l,r:longint; 34 begin 35 y:=fa[x];z:=fa[y]; 36 l:=ord(c[y,1]=x);r:=l xor 1; 37 if y=k then k:=x else c[z,ord(c[z,1]=y)]:=x; 38 fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y; 39 c[y,l]:=c[x,r];c[x,r]:=y; 40 pushup(y);pushup(x); 41 end; 42 procedure splay(x:longint;var k:longint);inline; 43 var y,z:longint; 44 begin 45 while x<>k do 46 begin 47 y:=fa[x];z:=fa[y]; 48 if y<>k then 49 if (c[z,0]=y) xor (c[y,0]=x) then rotate(x,k) 50 else rotate(y,k); 51 rotate(x,k); 52 end; 53 end; 54 function find(x,rank:longint):longint;inline; 55 var l,r:longint; 56 begin 57 l:=c[x,0];r:=c[x,1]; 58 if s[l]+1=rank then exit(x) 59 else if s[l]>=rank then exit(find(l,rank)) 60 else exit(find(r,rank-s[l]-1)); 61 end; 62 procedure build(l,r,f:longint);inline; 63 var x,y,z,mid:longint; 64 begin 65 if l>r then exit; 66 mid:=(l+r)>>1; 67 x:=id[mid];y:=id[f]; 68 v[x]:=a[mid];pre[x]:=abs(a[mid]-a[mid-1]); 69 c[y,ord(mid>f)]:=x;fa[x]:=y; 70 if l=r then 71 begin 72 s[x]:=1;mi[x]:=pre[x]; 73 exit; 74 end; 75 build(l,mid-1,mid);build(mid+1,r,mid); 76 pushup(x); 77 end; 78 procedure split(l,r:longint;var x,y:longint);inline; 79 begin 80 x:=find(rt,l);y:=find(rt,r); 81 splay(x,rt);splay(y,c[x,1]); 82 end; 83 procedure init; 84 begin 85 readln(n); 86 a[1]:=-inf;a[n+1]:=-inf; 87 for i:=2 to n+1 do begin read(a[i]);b[i]:=a[i];end; 88 sort(1,n); 89 ans:=maxlongint; 90 for i:=2 to n do ans:=min(ans,b[i]-b[i-1]); 91 end; 92 procedure add(x:longint); 93 begin 94 while x<=n do 95 begin 96 inc(d[x]); 97 inc(x,x and (-x)); 98 end; 99 end;100 function sum(x:longint):longint;101 begin102 sum:=0;103 while x>0 do104 begin105 inc(sum,d[x]);106 dec(x,x and (-x));107 end;108 end;109 procedure l_rotate(var x:longint);110 var111 y:longint;112 begin113 y:=r[x];114 r[x]:=l[y];115 l[y]:=x;116 x:=y;117 end;118 procedure r_rotate(var x:longint);119 var120 y:longint;121 begin122 y:=l[x];123 l[x]:=r[y];124 r[y]:=x;125 x:=y;126 end;127 128 procedure insert(var k,key:longint);129 begin130 if k=0 then131 begin132 inc(m);133 vv[m]:=key;134 hr[m]:=random(maxlongint);135 k:=m;136 exit;137 end;138 if key<=vv[k] then139 begin140 insert(l[k],key);141 if hr[l[k]]>hr[k] then142 r_rotate(k);143 exit;144 end;145 if key>vv[k] then146 begin147 insert(r[k],key);148 if hr[r[k]]>hr[k] then149 l_rotate(k);150 exit;151 end;152 end;153 function pred(var t,key:longint):longint;154 begin155 if t=0 then156 exit(-1);157 if key<=vv[t] then158 pred:=pred(l[t],key)159 else begin160 pred:=pred(r[t],key);161 if pred=-1 then162 pred:=vv[t];163 end;164 end;165 function succ(var t,key:longint):longint;166 begin167 if t=0 then168 exit(-1);169 if vv[t]<=key then170 succ:=succ(r[t],key)171 else begin172 succ:=succ(l[t],key);173 if succ=-1 then174 succ:=vv[t];175 end;176 end;177 procedure solveinsert;178 begin179 readln(pos,val);180 l:=sum(pos)+pos;r:=l+2;split(l,r,x,y);181 inc(tot);182 c[y,0]:=tot;fa[tot]:=y;s[tot]:=1;183 v[tot]:=val;pre[tot]:=abs(v[tot]-v[x]);mi[tot]:=pre[tot];184 pre[y]:=abs(v[y]-v[tot]);185 pushup(y);pushup(x);186 add(pos);187 ans:=min(ans,abs(pred(root,val)-val));188 ans:=min(ans,abs(succ(root,val)-val));189 insert(root,val);190 end;191 procedure main;192 begin193 for i:=1 to n+2 do id[i]:=i;194 for i:=2 to n+1 do insert(root,a[i]);195 build(1,n+2,0);rt:=(n+3)>>1;196 for i:=1 to m do197 begin198 reac(ch,ch,ch,ch,ch);199 case ch of200 ‘R‘:solveinsert;201 ‘G‘:writeln(mi[rt]);202 ‘S‘:writeln(ans);203 end;204 end;205 end;206 begin207 assign(input,‘input.txt‘);assign(output,‘output.txt‘);208 reset(input);rewrite(output);209 init;210 main;211 close(input);close(output);212 end.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。