1058: [ZJOI2007]报表统计

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
Sample Output
2
2
1
HINT

对于30%的数据，N ≤ 1000 , M ≤ 5000 对于100%的数据，N , M ≤500000 对于所有的数据，序列内的整数不超过5*108。

囧，又是splay，又被卡常数了，每次基本上都是对着数据调才调过的

我用两颗splay树，一个存所有的数（每次查前驱和后继更新答案），一个存所有的差值

当minsortgap为0时就不用再更新它了，还有，因为相邻的差值有一部分是不会被删除的，所以用min记录这些值中最小的值，大于等于min的差值就不用管它了（既不用删除，也不用插入）

搞了这么久终于过了（不过很慢，1300ms+）

  1 const
  2     maxn=500010;
  3 type
  4     node=record
  5       son:array[0..1]of longint;
  6       x,count,fa:longint;
  7     end;
  8 var
  9     tree:array[0..maxn*10]of node;
 10     a,b:array[0..maxn]of longint;
 11     n,m,mingap,minsortgap,min,tot,root1,root2:longint;
 12     flag:boolean;
 13  
 14 procedure down(var x:longint;y:longint);
 15 begin
 16     if x>y then x:=y;
 17 end;
 18  
 19 procedure rotate(x,w:longint;var root:longint);
 20 var
 21     y:longint;
 22 begin
 23     y:=tree[x].fa;
 24     tree[y].son[w]:=tree[x].son[w xor 1];
 25     if tree[x].son[w xor 1]<>0 then tree[tree[x].son[w xor 1]].fa:=y;
 26     tree[x].son[w xor 1]:=y;
 27     if root=y then root:=x
 28     else
 29       if tree[tree[y].fa].son[0]=y then tree[tree[y].fa].son[0]:=x
 30       else tree[tree[y].fa].son[1]:=x;
 31     tree[x].fa:=tree[y].fa;
 32     tree[y].fa:=x;
 33 end;
 34  
 35 procedure splay(x,z:longint;var root:longint);
 36 var
 37     y:longint;
 38 begin
 39     while tree[x].fa<>z do
 40       begin
 41         y:=tree[x].fa;
 42         if tree[y].fa=z then
 43           if tree[y].son[0]=x then rotate(x,0,root)
 44           else rotate(x,1,root)
 45         else
 46           if tree[tree[y].fa].son[0]=y then
 47             if tree[y].son[0]=x then
 48               begin
 49                 rotate(y,0,root);
 50                 rotate(x,0,root);
 51               end
 52             else
 53               begin
 54                 rotate(x,1,root);
 55                 rotate(x,0,root);
 56               end
 57           else
 58             if tree[y].son[0]=x then
 59               begin
 60                 rotate(x,0,root);
 61                 rotate(x,1,root);
 62               end
 63             else
 64               begin
 65                 rotate(y,1,root);
 66                 rotate(x,1,root);
 67               end;
 68       end;
 69 end;
 70  
 71 function pre(now:longint):longint;
 72 begin
 73     now:=tree[now].son[0];
 74     while tree[now].son[1]<>0 do
 75       now:=tree[now].son[1];
 76     exit(now);
 77 end;
 78  
 79 function succ(now:longint):longint;
 80 begin
 81     now:=tree[now].son[1];
 82     while tree[now].son[0]<>0 do
 83       now:=tree[now].son[0];
 84     exit(now);
 85 end;
 86  
 87 procedure delete(x:longint);
 88 var
 89     now,l,r:longint;
 90 begin
 91     now:=root2;
 92     while true do
 93       begin
 94         if now=0 then exit;
 95         if tree[now].x=x then break;
 96         if tree[now].x>x then now:=tree[now].son[0]
 97         else now:=tree[now].son[1];
 98       end;
 99     splay(now,0,root2);
100     if tree[root2].count>1 then dec(tree[root2].count)
101     else
102       begin
103         if (tree[root2].son[0]=0) or (tree[root2].son[1]=0) then
104         begin
105           if tree[root2].son[1]<>0 then mingap:=tree[succ(root2)].x;
106           root2:=tree[root2].son[0]+tree[root2].son[1];
107           tree[root2].fa:=0;
108           exit;
109         end;
110         l:=pre(root2);
111         r:=succ(root2);
112         splay(l,0,root2);
113         splay(r,l,root2);
114         tree[r].son[0]:=0;
115       end;
116 end;
117  
118 procedure insert(x:longint;var root:longint);
119 var
120     now:longint;
121 begin
122     now:=root;
123     if root=0 then
124     begin
125       inc(tot);
126       root:=tot;
127       tree[tot].x:=x;
128       tree[tot].count:=1;
129       if root=root2 then down(mingap,x);
130       exit;
131     end;
132     while true do
133       begin
134         if tree[now].x=x then
135           if root=root1 then
136             begin
137               minsortgap:=0;
138               flag:=true;
139               exit;
140             end
141           else
142             begin
143               inc(tree[now].count);
144               exit;
145             end;
146         if tree[now].x>x then
147           if tree[now].son[0]=0 then break
148           else now:=tree[now].son[0]
149         else
150           if tree[now].son[1]=0 then break
151           else now:=tree[now].son[1];
152       end;
153     inc(tot);
154     tree[tot].x:=x;
155     tree[tot].count:=1;
156     if x<tree[now].x then tree[now].son[0]:=tot
157     else tree[now].son[1]:=tot;
158     tree[tot].fa:=now;
159     splay(tot,0,root);
160     if root=root1 then
161       begin
162         if tree[root].son[0]<>0 then down(minsortgap,tree[root].x-tree[pre(root)].x);
163         if tree[root].son[1]<>0 then down(minsortgap,tree[succ(root)].x-tree[root].x);
164       end
165     else down(mingap,x);
166 end;
167  
168 procedure init;
169 var
170     i:longint;
171 begin
172     read(n,m);
173     minsortgap:=maxlongint;
174     mingap:=maxlongint;
175     min:=maxlongint;
176     for i:=1 to n do
177       begin
178         read(a[i]);
179         b[i]:=a[i];
180         if flag=false then insert(a[i],root1);
181         if i>1 then insert(abs(a[i]-a[i-1]),root2);
182       end;
183     readln;
184 end;
185  
186 procedure work;
187 var
188     i,x,y:longint;
189     c:char;
190     s:string;
191 begin
192     for i:=1 to m do
193       begin
194         read(c);
195         case c of
196           'I':begin
197             readln(c,c,c,c,c,x,y);
198             if x<n then
199             begin
200               if min>abs(b[x+1]-y) then insert(abs(b[x+1]-y),root2);
201               if min>abs(a[x]-b[x+1]) then delete(abs(a[x]-b[x+1]));
202             end;
203             down(min,abs(a[x]-y));
204             if flag=false then insert(y,root1);
205             a[x]:=y;
206           end;
207           'M':begin
208             readln(s);
209             if length(s)>7 then writeln(minsortgap)
210             else
211               begin
212                 down(mingap,min);
213                 writeln(mingap);
214               end;
215           end;
216         end;
217       end;
218 end;
219  
220 begin
221     init;
222     work;
223 end.

View Code