小 Q 的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小 Q 希望可以帮妈妈分担一些工作，作为她的生日礼物之一。
经过仔细观察，小 Q 发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。
在最开始的时候，有一个长度为 nn 的整数序列 aa，并且有以下三种操作：
INSERT i k：在原数列的第 ii 个元素后面添加一个新元素 kk；如果原数列的第 ii 个元素已经添加了若干元素，则添加在这些元素的最后（见样例说明）。MIN_GAP：查询相邻两个元素的之间差值（绝对值）的最小值。MIN_SORT_GAP：查询所有元素中最接近的两个元素的差值（绝对值）。
于是小 Q 写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？
题解：
过的极其艰难的一道题，不得不说自己距离数据结构高手的差距还很大很大。
思路就是开两个Treap，分别维护两种差值。
省选的数据强度很大，一开始自己的思路根本没问题，但是只有0分，以至于对着题解的代码一行一行改才通过，太痛苦了，不知道一开始哪个点写错了。
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+100; const int inf=1e9; vector<int> g[maxn]; int a[maxn]; int n,m; int Min; int f; //treap树 struct Treap { struct Treap_tree { int ch[2]; int v; int dat;//优先级 int size;//子树节点数 int cnt;//重复数 }t[maxn]; int tot; int root; int newNode (int v) { tot++; t[tot].v=v; t[tot].dat=rand();//随机优先级 t[tot].size=1; t[tot].cnt=1; return tot; } void pushup (int x) { t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt; } void build () { root=newNode(-inf); t[root].ch[1]=newNode(inf); pushup(root); } void rotate (int &id,int d) { int tt=t[id].ch[d^1]; t[id].ch[d^1]=t[tt].ch[d]; t[tt].ch[d]=id; id=tt; pushup(t[id].ch[d]); pushup(id); } void ins (int &id,int v) { if (!id) { id=newNode(v); return; } if (v==t[id].v) t[id].cnt++; else { ins(t[id].ch[v>t[id].v],v); if (t[id].dat<t[t[id].ch[v>t[id].v]].dat) rotate(id,v<t[id].v); } pushup(id); } void remove (int &id,int v) { if (!id) return; if (v==t[id].v) { if (t[id].cnt>1) { t[id].cnt--; pushup(id); return; } if (t[id].ch[0]||t[id].ch[1]) { if (!t[id].ch[1]||t[t[id].ch[0]].dat>t[t[id].ch[1]].dat) { rotate(id,1); remove(t[id].ch[1],v); } else { rotate(id,0); remove(t[id].ch[0],v); } pushup(id); } else id=0; return; } remove(t[id].ch[v>t[id].v],v); pushup(id); } int rk (int id,int v) { if (!id) return 0; if (v==t[id].v) return t[t[id].ch[0]].size+1; else if (v<t[id].v) return rk(t[id].ch[0],v); else return t[t[id].ch[0]].size+t[id].cnt+rk(t[id].ch[1],v); } int kth (int id,int k) { if (!id) return inf; if (k<=t[t[id].ch[0]].size) return kth(t[id].ch[0],k); else if (k<=t[t[id].ch[0]].size+t[id].cnt) return t[id].v; else return kth(t[id].ch[1],k-t[t[id].ch[0]].size-t[id].cnt); } int get_pre (int id,int v) { int pre; while (id) { if (t[id].v<v) pre=t[id].v,id=t[id].ch[1]; else id=t[id].ch[0]; } return pre; } int get_next (int id,int v) { int nxt; while (id) { if (t[id].v>v) nxt=t[id].v,id=t[id].ch[0]; else id=t[id].ch[1]; } return nxt; } int dfs (int id) { if (!t[id].ch[0]) return t[id].v; return min(t[id].v,dfs(t[id].ch[0])); } }tree1,tree2; map<int,int> p; char op[5]; int main() { scanf("%d%d",&n,&m); Min=inf; for (int i=1;i<=n;i++) { g[i].clear(); scanf("%d",a+i); g[i].push_back(a[i]); tree1.ins(tree1.root,a[i]); p[a[i]]++; if (p[a[i]]>1) Min=0; } for (int i=2;i<=n;i++) tree2.ins(tree2.root,abs(g[i][0]-g[i-1][0])); sort(a+1,a+1+n); for (int i=2;i<=n;i++) Min=min(Min,a[i]-a[i-1]); for (int i=1;i<=m;i++) { scanf("%s", op); if (op[0]=='I') { int x,k; scanf("%d%d",&x,&k); if (Min) { int lst=tree1.get_pre(tree1.root,k),nxt=tree1.get_next(tree1.root,k); tree1.ins(tree1.root,k); Min=min(Min,min(abs(lst-k),abs(nxt-k)));//查找前驱和后继来更新答案 } tree2.remove(tree2.root,abs(g[x][(int)g[x].size()-1]-g[x+1][0])); //删除原先答案 tree2.ins(tree2.root,abs(g[x][(int)g[x].size()-1]-k)); tree2.ins(tree2.root,abs(k-g[x+1][0])); //加入现在答案 g[x].push_back(k); //插入这个数 p[k]++; if (p[k]>1) Min=0; } if (op[4] == 'G') printf("%d ",tree2.dfs(tree2.root));//查找最小差值 if (op[4] == 'S') printf("%d ",Min); } return 0; }