【题目分析】
上次用树状数组套主席树做的,这次用整体二分去水。
把所有的查询的结果一起进行二分,思路很好。
【代码】
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <set> #include <map> #include <string> #include <algorithm> #include <vector> #include <iostream> #include <queue> using namespace std; #define maxn 100005 #define inf (0x3f3f3f3f) int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } struct node{ int x,y,k; int id,opt; void print() { printf("%d %d %d %d %d\n", x, y, k, id, opt); } }now; int n,m,a[maxn],ans[maxn]; char s[15]; node q[maxn<<1],q1[maxn],q2[maxn]; int cnt=0,bit[maxn<<1],tot=0; void add(int x,int f) { // printf("add %d %d\n",x,f); for (;x<=n;x+=x&-x) bit[x]+=f; } int sum(int x) { int ret=0; // printf("sum %d ",x); for (;x;x-=x&-x) ret+=bit[x]; // printf("is %d\n",x,ret); return ret; } void solve(int ql,int qr,int l,int r) { // printf("solve %d %d %d %d\n",ql,qr,l,r); if (ql>qr) return ; if (l==r) { for (int i=ql;i<=qr;++i) if (q[i].opt==2) ans[q[i].id]=l; return; } int mid=l+r>>1,p1=0,p2=0; for (int i=ql;i<=qr;++i) { if (q[i].opt==1) { if (q[i].x<=mid) { add(q[i].id,q[i].y); q1[++p1]=q[i]; } else q2[++p2]=q[i]; } else { int tmp=sum(q[i].y)-sum(q[i].x-1); // printf("tmp is %d\n"); if (q[i].k<=tmp) q1[++p1]=q[i]; else { // cout<<q[i].x<<" "<<q[i].y<<"goto r "<<endl; q[i].k-=tmp; q2[++p2]=q[i]; } } } for (int i=1;i<=p1;++i) if (q1[i].opt==1) add(q1[i].id,-q1[i].y); for (int i=1;i<=p1;++i) q[ql+i-1]=q1[i]; for (int i=1;i<=p2;++i) q[ql+p1+i-1]=q2[i]; // getchar(); solve(ql,ql+p1-1,l,mid); solve(ql+p1,qr,mid+1,r); } int main() { n=read();m=read(); for (int i=1;i<=n;++i) { a[i]=now.x=read();now.y=1;now.k=inf; now.id=i; now.opt=1; q[++cnt]=now; } for (int i=1;i<=m;++i) { scanf("%s",s); if (s[0]=='Q') { now.x=read();now.y=read();now.k=read(); now.id=++tot;now.opt=2; q[++cnt]=now; } else { int xx=read(); now.x=a[xx];now.y=-1;now.k=inf;now.id=xx;now.opt=1; q[++cnt]=now; a[xx]=read(); now.x=a[xx];now.y=1;now.k=inf;now.id=xx;now.opt=1; q[++cnt]=now; } } // for (int i=1;i<=cnt;++i) q[i].print(); solve(1,cnt,0,inf); for (int i=1;i<=tot;++i) printf("%d\n",ans[i]); }