【BZOJ 1901】 Zju2112 Dynamic Rankings|树状数组套主席树

本文主要是介绍【BZOJ 1901】 Zju2112 Dynamic Rankings|树状数组套主席树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

很奇怪 把数组开到main里就RE。。。

用垃圾回收内存卡到 17MB

不过我好像养成写长代码的坏习惯了。。。。。

#include <cstdio> 
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 10010struct H
{int L,R;int sum;
}seg[MAXN*100];struct QQQ 
{int opt;int x,y,z;
}q[MAXN];// hahs 离散 
int hash[MAXN*2];
int cnt;
int Get_Hash(int x)
{int L=1,R=cnt;while(L<R){int mid=(L+R)/2;if(x<=hash[mid]) R=mid;else L=mid+1;}return L;
}int lowbit(int x)
{return x&-x;
}int LL[MAXN],RR[MAXN],LN,RN;int n,m;
int init[MAXN]; 
int laji[MAXN*100],top;int Q(int l,int r,int k)
{if(l==r) return l;int SL=0;int SR=0;for(int i=1;i<=LN;i++) SL+=seg[seg[LL[i]].L].sum;for(int i=1;i<=RN;i++) SR+=seg[seg[RR[i]].L].sum;int mid=(l+r)/2;if(k<=SR-SL){for(int i=1;i<=LN;i++) LL[i]=seg[LL[i]].L;for(int i=1;i<=RN;i++) RR[i]=seg[RR[i]].L;return Q(l,mid,k);}else{for(int i=1;i<=LN;i++) LL[i]=seg[LL[i]].R;for(int i=1;i<=RN;i++) RR[i]=seg[RR[i]].R;k-=SR-SL;return Q(mid+1,r,k);}
}void IN(int &x)
{x=laji[top--];
}
void OUT(int &x)
{if(x==0) return ;seg[x]=(H){0,0,0};laji[++top]=x;x=0;
}
void Seg_Remove(int now,int l,int r,int x)
{if(l==r) {seg[now].sum--;return ;}int mid=(l+r)/2;if(x<=mid) Seg_Remove(seg[now].L,l,mid,x);else Seg_Remove(seg[now].R,mid+1,r,x);if(seg[seg[now].L].sum==0) OUT(seg[now].L);if(seg[seg[now].R].sum==0) OUT(seg[now].R);seg[now].sum=seg[seg[now].L].sum+seg[seg[now].R].sum;
}
void Seg_Add(int now,int l,int r,int x)
{if(l==r){seg[now].sum++;return ;}int mid=(l+r)/2;if(x<=mid){if(seg[now].L==0) IN(seg[now].L);Seg_Add(seg[now].L,l,mid,x);}else{if(seg[now].R==0) IN(seg[now].R);Seg_Add(seg[now].R,mid+1,r,x);}seg[now].sum=seg[seg[now].L].sum+seg[seg[now].R].sum;
}
int root[MAXN];void Remove(int x,int y)
{while(x<=n){Seg_Remove(root[x],1,cnt,y);x+=lowbit(x);}
}
void Add(int x,int y)
{while(x<=n){if(root[x]==0) IN(root[x]);Seg_Add(root[x],1,cnt,y);x+=lowbit(x);}
}
int team[MAXN*2];
int main()
{cin >>n >>m;int top=0;for(int i=1;i<=n;i++) {scanf("%d",&init[i]);team[++top]=init[i];}for(int i=1;i<=m;i++){char s[5];scanf("%s",s+1);if(s[1]=='Q'){scanf("%d %d %d",&q[i].x,&q[i].y,&q[i].z);q[i].opt=1;}else{scanf("%d %d",&q[i].x,&q[i].y);team[++top]=q[i].y;q[i].opt=2;}}sort(team+1,team+1+top);hash[1]=team[1];cnt=1;for(int i=2;i<=top;i++)if(team[i]!=team[i-1])hash[++cnt]=team[i];for(int i=1;i<=n;i++)init[i]=Get_Hash(init[i]);for(int i=1;i<=m;i++)if(q[i].opt==2)q[i].y=Get_Hash(q[i].y);for(int i=1;i<MAXN*100;i++)laji[++top]=i;for(int i=1;i<=n;i++)Add(i,init[i]);for(int i=1;i<=m;i++){if(q[i].opt==1){LN=0;RN=0;for(int j=q[i].x-1;j>0;j-=lowbit(j))LL[++LN]=root[j];for(int j=q[i].y;j>0;j-=lowbit(j))RR[++RN]=root[j];printf("%d\n",hash[Q(1,cnt,q[i].z)]);}else{Remove(q[i].x,init[q[i].x]);init[q[i].x]=q[i].y;Add(q[i].x,init[q[i].x]);}}return 0;
}

这篇关于【BZOJ 1901】 Zju2112 Dynamic Rankings|树状数组套主席树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---