【BZOJ 1058】【ZJOI 2007】报表统计【Treap】

Description

在最开始的时候，有一个长度为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写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？

题解

维护两个treap即可。 第一个 维护每个点，每次新加入一个点时，找到前驱后继，维护第3个操作的答案。 第二个 每次加入点时，维护相邻两个点之差的绝对值。

注意：——>“易被卡常”

优化

1、对于第2个操作，我们注意到，加入一个点位置是pos时，pos与pos-1的差值不会消失，所以可以用一个may来维护pos与前驱的之间的值。

2、而pos与pos+1之间可能加入数字，所以用treap维护，不过，若差值小于may，就不用再加入treap中了。

3、还有，对于第3个操作，在统计是只要发现有两个数字相同，就做个标记，到后面询问时直接输出0即可。

（以上所说的差值都要加绝对值） 细节见代码

代码

#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; #define N 500005 #define inf 1000000000 int seq[N][2]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct node{ node* ch[2]; int r,v,s,ss; node(int v):v(v) { ch[0] = ch[1] = NULL; r = rand(); s = ss = 1; } int cmp(int x) { if(x == v) return -1; return x < v ? 0 : 1; } void maintain() { s = ss; if(ch[0])s += ch[0]->s; if(ch[1])s += ch[1]->s; } }*root1,*root2; int ans = inf; bool flag;//这是注意里的优化3 void rotate(node* &o,int d) { node *k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; o->maintain(); k->maintain(); o = k; } void insert(node* &o,int x) { if(o == NULL) o = new node(x); else { int d = o->cmp(x); if(d == -1){o->ss++; o->s++; if(flag) ans = -1;return;} else { insert(o->ch[d],x); if(o->ch[d]->r > o->r) rotate(o,d^1); } } o->maintain(); } void remove(node* &o,int x) { if(o == NULL)return; int d = o->cmp(x); if(d == -1) { if(o->ss > 1){o->ss --;o->s --;return;} else { node* u = o; if(o->ch[0] && o->ch[1]) { int d2 = (o->ch[0]->r > o->ch[1]->r ? 1 : 0); rotate(o,d2);remove(o->ch[d2],x); } else { if(!o->ch[0]) o = o->ch[1]; else o = o->ch[0]; delete u; } } } else remove(o->ch[d],x); if(o) o->maintain(); } int ask_min(node* o) {while(o->ch[0]) o = o ->ch[0]; return o->v;} int ans1; void ask_before(node* o,int x) { if(o == NULL)return; if(o->v < x) { ans1 = o->v; ask_before(o->ch[1],x); }else ask_before(o->ch[0],x); } void ask_after(node* o,int x) { if(o == NULL)return; if(o->v > x) { ans1 = o->v; ask_after(o->ch[0],x); } else ask_after(o->ch[1],x); } int main() { int n,m,x,y; char str[20]; n=read();m=read(); flag = true; for(int i = 1;i <= n;i++) { x=read(); seq[i][1]=seq[i][0]=x; insert(root1,x); if(ans != -1) { int minn = inf; ask_before(root1,x); minn = min(minn,abs(ans1-x)); ask_after(root1,x); minn = min(minn,abs(ans1-x)); ans = min(ans,minn); } } insert(root1,inf);insert(root1,-inf); flag = false; for(int i = 1;i < n;i++) insert(root2,abs(seq[i][0]-seq[i+1][0])); int may=inf; while(m--) { scanf("%s",str); if(str[4] == 'R') { x=read();y=read(); flag = true; insert(root1,y); if(ans != -1) { int minn = inf; ask_before(root1,y); minn = min(minn,abs(ans1-y)); ask_after(root1,y); minn = min(minn,abs(ans1-y)); ans = min(ans,minn); } flag = false; if(abs(seq[x][1]-y) < may) may = abs(seq[x][1]-y);//优化1 if(x != n) { if(abs(seq[x+1][0]-y) < may)insert(root2,abs(seq[x+1][0]-y)); if(abs(seq[x+1][0]-seq[x][1]) < may)remove(root2,abs(seq[x+1][0]-seq[x][1])); }//这里有优化2 seq[x][1] = y; } else if(str[4] == 'G') printf("%d\n",min(ask_min(root2),may)); else if(str[4] == 'S') printf("%d\n",ans == -1 ? 0 : ans); } return 0; }

唉，在BZOJ上无限TLE后的最终成果。