主席树,其实就是N颗线段树
只是他们公用了一部分节点(๑•̀ㅂ•́)و✧
我大部分的代码是从一位大佬的那里看到的
我这个垃圾程序连Poj2104上的数据都过不了TLE
so希望神犇能给我看看,顺便给和我一样的底层人物一点指针的帮助
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #define N 100100 5 using namespace std; 6 struct XDS{ 7 int l,r,dat; 8 XDS *lc,*rc; 9 XDS(){l=r=dat=0,lc=rc=NULL;} 10 };XDS *ro[N]; 11 int n,qn,num[N],val[N],len; 12 void prerun(){//这是离散化的预处理 13 sort(val+0,val+n); 14 len=unique(val+0,val+n)-val; 15 } 16 int fvind(int x){//离散化get 17 return lower_bound(val+0,val+len,x)-val+1; 18 } 19 void Empty_total(XDS *&rt,int l,int r){//以l为左,r为右处理一颗空树,初始化 20 rt=new XDS(); 21 rt->l=l; 22 rt->r=r; 23 if(l==r)return ; 24 int mid=(l+r)/2; 25 Empty_total(rt->lc,l,mid); 26 Empty_total(rt->rc,mid+1,r); 27 } 28 void dfs(XDS *rt){//调试用的,不用管 29 if(rt==NULL)return; 30 cout<<rt<<" "<<rt->l<<" "<<rt->r<<" "<<rt->dat<<"\n"; 31 dfs(rt->lc); 32 dfs(rt->rc); 33 } 34 void add(XDS *his,XDS *&nrt,int v){//his:从上一个转移过来,nrt :现在在搞的 (同位转移)增加一个|V:离散化后 35 if(his==NULL)return ;//结束 36 if(nrt==NULL)nrt=new XDS();//新开节点 37 int l=his->l;nrt->l=l; 38 int r=his->r;nrt->r=r; 39 if(l==r){ 40 nrt->dat=his->dat+1; 41 return ; 42 } 43 int mid=(l+r)/2; 44 if(v<=mid){//值在左侧 45 nrt->rc=his->rc;//直接拿右侧 46 add(his->lc,nrt->lc,v);//查左 47 } 48 else{//值在右侧 49 nrt->lc=his->lc;//直接拿左侧 50 add(his->rc,nrt->rc,v);//查右 51 } 52 nrt->dat=nrt->lc->dat+nrt->rc->dat; 53 } 54 int query(XDS *lrt,XDS *rrt,int k){//在lrt与rrt之间查第K大 55 int l=1,r=len;//二分查找 56 while(l<r){ 57 int mid=(l+r)/2; 58 int cnt=rrt->lc->dat-lrt->lc->dat;/*两个树的左子树差 59 即在这个区间内在[0,mid]范围内的增加值 */ 60 if(cnt>=k){//比k个多,往左搜 61 r=mid; 62 lrt=lrt->lc; 63 rrt=rrt->lc;//同步浏览 64 } 65 else {//比k个少,往右 66 l=mid+1; 67 k-=cnt; 68 lrt=lrt->rc; 69 rrt=rrt->rc; 70 } 71 } 72 return l; 73 } 74 int main(){ 75 scanf("%d%d",&n,&qn); 76 for(int i=1;i<=n;i++){ 77 scanf("%d",&num[i]); 78 val[i-1]=num[i]; 79 } 80 prerun(); 81 Empty_total(ro[0],1,len); 82 // dfs(ro[0]); 83 for(int i=1;i<=n;i++){ 84 add(ro[i-1],ro[i],fvind(num[i])); 85 } 86 int a,b,c; 87 for(int i=1;i<=qn;i++){ 88 scanf("%d%d%d",&a,&b,&c); 89 // cout<<query(ro[a-1],ro[b],c)<<endl; 90 printf("%d\n",val[query(ro[a-1],ro[b],c)-1]); 91 } 92 return 0; 93 }Code在这里