参考了这篇博客：http://blog.csdn.net/v5zsq/article/details/50775827
树套树感觉好麻烦，就学了下整体二分，发现还是挺简单的。每个询问都进入了第32层，所以复杂度大概是O（nlogn*32）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include<cstdio>#include<algorithm>using namespace std;const int N=100005,INF=0x3f3f3f3f;int c[N];void add(int x,int y){ for (int i=x;i<N;i+=i&-i) c[i]+=y;}int get(int x){ int tmp=0; for (int i=x;i;i-=i&-i) tmp+=c[i]; return tmp;}int n,m;int a[N];int ans[N];struct event{ int tp,x,y,z,id;}Q[N*3],q1[N*3],q2[N*3];int f[N*3];int tot;void solve(int l,int r,int head,int tail){ if (head>tail) return; //这句很关键，否则递归次数会变成2*INF次 if (l==r) { for (int i=head;i<=tail;i++) if (Q[i].tp==3) ans[Q[i].id]=l; return; } int mid=(l+r)/2; for (int i=head;i<=tail;i++) { if (Q[i].tp==1&&Q[i].y<=mid) add(Q[i].x,1); if (Q[i].tp==2&&Q[i].y<=mid) add(Q[i].x,-1); if (Q[i].tp==3) f[i]=get(Q[i].y)-get(Q[i].x-1); } //对于每个询问搞出区间内不大于mid的个数 for (int i=head;i<=tail;i++) { if (Q[i].tp==1&&Q[i].y<=mid) add(Q[i].x,-1); if (Q[i].tp==2&&Q[i].y<=mid) add(Q[i].x,1); } //清空树状数组 int cnt1=0,cnt2=0; for (int i=head;i<=tail;i++) { if (Q[i].tp<3) { if (Q[i].y<=mid) q1[++cnt1]=Q[i]; else q2[++cnt2]=Q[i]; } else { if (f[i]<Q[i].z) Q[i].z-=f[i],q2[++cnt2]=Q[i]; else q1[++cnt1]=Q[i]; } }//分离询问 int tmp=0; for (int i=1;i<=cnt1;i++) Q[head+tmp]=q1[i],tmp++; for (int i=1;i<=cnt2;i++) Q[head+tmp]=q2[i],tmp++; solve(l,mid,head,head+cnt1-1); solve(mid+1,r,head+cnt1,tail);}int main(){ while(~scanf("%d",&n)) { tot=0; for (int i=1;i<=n;i++) { scanf("%d",&a[i]); Q[++tot]={1,i,a[i],i}; //把一开始的值也当作事件来看待 } scanf("%d",&m); for (int i=1;i<=m;i++) { ans[i]=-INF; int tp,x,y,z; scanf("%d%d%d",&tp,&x,&y); if (tp==1) { Q[++tot]={2,x,a[x],0,i}; Q[++tot]={1,x,y,0,i}; a[x]=y; //修改就是删除一个数再插入一个数 } else { scanf("%d",&z); Q[++tot]={3,x,y,z,i}; } } solve(0,INF,1,tot); for (int i=1;i<=m;i++) if (ans[i]!=-INF) printf("%d\n",ans[i]); }} |
