静态treap+线段树---zoj_2112
?????? http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2112
?????? 终于A了这惊天地泣鬼神的一题，练习了线段树和treap。。。此题要求对于N个正整数，给定M个操作，操作有两种1)输入 i j k，要求输出a[i]到a[j]中第k大的数.2)i q，将
a[i]修改为q.
?????? 这题的特点是数据量很大，N<=50000,M<=10000,时限为10S。。。。，一般的思路，查询求第k大，有topk算法，基于排序的是O(NlogN),不排序的随机划分可以达到O(N),对于修改操作O(1)，如果操作中大多数为查询操作的话，算法的上届为O(M*N)，不太靠谱。
?????? 需要到区间查询+topK,那么考虑使用线段树+平衡树，每一个区间的域中定义一个属性，指向区间对应的平衡树的根。这里平衡使用了treap，写起来简单。。TAT，我太水了。
?????? 这里有个关键的问题，如何在上述结构中查询区间的第K大，二分，有点奇怪，但很精妙，二分第K大的数，可以取区间(-inf,inf)，对于每个K在区间中找到小于K的个数，记为
S(K)，那么要找到第i大的数就是要找到最大的K使得S(K)<i,S(k+1)>=i.
?????? 再分析一下效率，对于查询，每次从最大的区间开始查询，中间经过区间的分裂，最后找到若干个区间和线段树中的区间完全对等。然后开始在对应的treap中开始统计个数。最后把分裂的若干个区间的个数加起来即可。找区间logN,treap中统计logN,那么对于每次查询上届为O(logN*logN)?这是一个模糊的上届，我个人感觉不是很准确。其实仔细想一下，越早找对应到区间，那么在区间的treap里对应的节点就越多，而越晚找到区间，treap里的节点就越少，那么查询的效率其实就是O(logN)?。。。。我还没仔细证过，姑且这么认为。。。
?????? 对于每一次修改，先删除，再插入。找到每一个包含该节点的区间里的treap,共有logN个区间，区间treap的节点数为（1，2，4，。。。N/2,N），那么总的修改消耗为O(logN+log(N-1)+....log(1))，记一个上界为O(logN*logN).
????? 那么总共的M次查询，总共的消耗即为O(M*logN*logN*32),但实际上肯定比这个要小。
????? 对于空间的使用，静态的treap在删除节点之后的那份空间其实是可以利用的，我代码里没有使用。静态的线段树也浪费了2*N的空间，这个似乎是静态线段树的局限性吧。
???? 最后，我的treap里加了一个域c统计树中的元素个数，这个域在旋转操作的时候也要同时操作。
zoj_2112.cpp
???
#include<cstdio>#include<algorithm>#include<time.h>using namespace std;const int MAXM=1000000;int total,a[50005];int inf=1000000005;struct block{int l,r,root;}b[200005];struct treap{int l,r,p,v,c;}tr[MAXM];void leftR(int &a){int b=tr[a].r;//!!count numint tot=tr[a].c;tr[a].c=tot-tr[b].c+tr[tr[b].l].c;tr[b].c=tot;//rotatetr[a].r=tr[b].l;tr[b].l=a;a=b;}void rightR(int &a){int b=tr[a].l;//!!count numint tot=tr[a].c;tr[a].c=tot-tr[b].c+tr[tr[b].r].c;tr[b].c=tot;//rotatetr[a].l=tr[b].r;tr[b].r=a;a=b;}void ins(int &node,int value,int p){if(node==0){tr[++total].l=0;tr[total].r=0;tr[total].v=value;tr[total].p=p;tr[total].c=1;node=total;return;}if(value<=tr[node].v){ins(tr[node].l,value,p);tr[node].c++;if(tr[tr[node].l].p>tr[node].p)rightR(node);}else{ins(tr[node].r,value,p);tr[node].c++;if(tr[tr[node].r].p>tr[node].p)leftR(node);}}int del(int &root,int value){if(tr[root].v==value){if(tr[root].l!=0&&tr[root].r!=0){if(tr[tr[root].l].p>tr[tr[root].r].p){rightR(root);tr[root].c--;return del(tr[root].r,value);}else{leftR(root);tr[root].c--;return del(tr[root].l,value);}}else if(tr[root].l!=0&&tr[root].r==0){rightR(root);tr[root].c--;return del(tr[root].r,value);}else if(tr[root].l==0&&tr[root].r!=0){leftR(root);tr[root].c--;return del(tr[root].l,value);}else{tr[root].l=0;tr[root].r=0;tr[root].p=0;tr[root].v=0;root=0;return root;}}else if(tr[root].v>value){tr[root].c--;return del(tr[root].l,value);}else{tr[root].c--;return del(tr[root].r,value);}}void change(int p,int pos,int pre,int curr){if(pos<b[p].l||pos>b[p].r)return;int r=del(b[p].root,pre);ins(b[p].root,curr,rand());if(b[p].l<b[p].r){change(2*p,pos,pre,curr);change(2*p+1,pos,pre,curr);}return;}int getnum(int pos,int s,int e,int th){if(b[pos].l==s&&b[pos].r==e){int root=b[pos].root;int tmp=root;int res=0;while(tmp!=0){if(tr[tmp].v>=th)tmp=tr[tmp].l;else {res=res+1+tr[tr[tmp].l].c;tmp=tr[tmp].r;}}return res;}else{int mid=(b[pos].l+b[pos].r)/2;if(e<=mid){int r=getnum(2*pos,s,e,th);return r;}if(s>mid){int r=getnum(2*pos+1,s,e,th);return r;}int u=getnum(2*pos,s,mid,th);int v=getnum(2*pos+1,mid+1,e,th);return u+v;}}void build(int pos,int l,int r){b[pos].l=l;b[pos].r=r;b[pos].root=0;for(int i=l;i<=r;++i)ins(b[pos].root,a[i],rand());if(l<r){int mid=(l+r)/2;build(2*pos,l,mid);build(2*pos+1,mid+1,r);}}int cases,m,n;int main(){freopen("e:\\zoj\\2011-9\\zoj_2112.txt","r",stdin);scanf("%d",&cases);srand((unsigned)time(0));while(cases--){total=0;scanf("%d %d",&m,&n);for(int i=1;i<=m;++i)scanf("%d ",&a[i]);build(1,1,m);for(int i=1;i<=n;++i){//getchar();char c=getchar();if(c=='Q'){int e,f,i;scanf("%d %d %d ",&e,&f,&i);int l=-inf;int r=inf;while(l<r){int mid=(l+r)/2;int sss=getnum(1,e,f,mid);if(sss<i)l=mid+1;elser=mid;}printf("%d\n",l-1);}else{int i,d;scanf("%d %d ",&i,&d);change(1,i,a[i],d);a[i]=d;}}}return 0;}?
?