题意：带修改的第K大
#include<cstdio> #include<iostream> #include<cstring> #define N 400010 #define inf 1000000000 using namespace std; int a[N],ans[N],sum[N],tmp[N],n,m,num,cnt; struct node{ int x,y,s,k,tp,cur; };node q[N],q1[N],q2[N]; void modify(int x,int v){ while(x<=n){ sum[x]+=v; x+=x&(-x); } } int query(int x){ int tot=0; while(x){ tot+=sum[x]; x-=x&(-x); } return tot; } void solve(int head,int tail,int l,int r){ if(head>tail)return; if(l==r){ for(int i=head;i<=tail;i++) if(q[i].tp==3)ans[q[i].s]=l; return; } int mid=l+r>>1; for(int i=head;i<=tail;i++){ if(q[i].tp==1&&q[i].y<=mid)modify(q[i].x,1); if(q[i].tp==2&&q[i].y<=mid)modify(q[i].x,-1); if(q[i].tp==3) tmp[i]=query(q[i].y)-query(q[i].x-1); } for(int i=head;i<=tail;i++){ if(q[i].tp==1&&q[i].y<=mid)modify(q[i].x,-1); if(q[i].tp==2&&q[i].y<=mid)modify(q[i].x,1); } int l1=0,l2=0; for(int i=head;i<=tail;i++){ if(q[i].tp==3){ if(q[i].cur+tmp[i]>=q[i].k) q1[++l1]=q[i]; else q[i].cur+=tmp[i],q2[++l2]=q[i]; } else { if(q[i].y<=mid) q1[++l1]=q[i]; else q2[++l2]=q[i]; } } for(int i=1;i<=l1;i++) q[head+i-1]=q1[i]; for(int i=1;i<=l2;i++) q[head+l1+i-1]=q2[i]; solve(head,head+l1-1,l,mid); solve(head+l1,tail,mid+1,r); } void work(){ for(int i=1;i<=n;i++){ scanf("%d",&a[i]); q[++num].x=i;q[num].y=a[i];q[num].tp=1;q[num].s=0; } scanf("%d",&m); for(int i=1;i<=m;i++){ int op;scanf("%d",&op); if(op==1){ int x,y;scanf("%d%d",&x,&y); q[++num].x=x;q[num].y=a[x];q[num].tp=2;q[num].s=0; q[++num].x=x;q[num].y=y;q[num].tp=1;q[num].s=0; a[x]=y; } else { int x,y,k;scanf("%d%d%d",&x,&y,&k); q[++num].x=x;q[num].y=y;q[num].k=k;q[num].tp=3;q[num].s=++cnt; } } solve(1,num,-inf,inf); for(int i=1;i<=cnt;i++) printf("%d ",ans[i]); } int main(){ while(scanf("%d",&n)!=EOF){ memset(ans,0,sizeof(ans)); memset(tmp,0,sizeof(tmp)); memset(sum,0,sizeof(sum)); memset(q,0,sizeof(q)); num=cnt=0; work(); } return 0; }