题目
做法
单点修改主席树
纯粹按模板题的做法，建完主席树后修改一个点后面所有的树都得修改\(O(mnlogn)\)，T飞了
树状数组套主席树，在主席树根结点上用树状数组跳着修改O(mlogn^2)
My complete code
// luogu-judger-enable-o2#include#include #include #include #include #include using namespace std;typedef long long LL;const LL maxn=1e5+10;struct node{ LL l,r,k,val,now;}q[maxn];LL n,m,num,num1,num2,cnt; LL b[maxn<<1],a[maxn],lt[maxn<<7],rt[maxn<<7],date[maxn<<7],root[maxn],que1[maxn],que2[maxn];inline LL read(){ char c; LL f=1; c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } LL x=0; while(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar(); } return x*f;}inline LL lowbit(LL x){ return x&-x;}inline void update(LL x,LL l,LL r,LL c,LL val){ while(true){ LL mid=(l+r)>>1; date[x]+=val; if(l==r) return; if(c<=mid){ if(!lt[x]) lt[x]=++num; x=lt[x],r=mid; }else{ if(!rt[x]) rt[x]=++num; x=rt[x],l=mid+1; } }}inline void add(LL x,LL v){ LL now=std::lower_bound(b+1,b+1+cnt,a[x])-b; for(LL i=x;i<=n;i+=lowbit(i)){ if(!root[i]) root[i]=++num; update(root[i],1,cnt,now,v); }}inline LL query(LL l,LL r,LL k){ while(l!=r){ LL sum=0,mid=(l+r)>>1; for(LL i=1;i<=num1;++i) sum+=date[lt[que1[i]]]; for(LL i=1;i<=num2;++i) sum-=date[lt[que2[i]]]; if(sum>=k){ for(LL i=1;i<=num1;++i) que1[i]=lt[que1[i]]; for(LL i=1;i<=num2;++i) que2[i]=lt[que2[i]]; r=mid; }else{ for(LL i=1;i<=num1;++i) que1[i]=rt[que1[i]]; for(LL i=1;i<=num2;++i) que2[i]=rt[que2[i]]; return query(mid+1,r,k-sum); l=mid+1,k-=sum; } } return l;}int main(){ n=read(),m=read(); for(LL i=1;i<=n;++i) a[i]=b[++cnt]=read(); for(LL i=m;i>=1;--i){ char s[100]; scanf(" %s",s); if(s[0]=='Q') q[i].l=read(),q[i].r=read(),q[i].k=read(); else q[i].k=0, q[i].now=read(),q[i].val=read(), b[++cnt]=q[i].val; } std::sort(b+1,b+cnt+1); cnt=std::unique(b+1,b+1+cnt)-b-1; for(LL i=1;i<=n;++i) add(i,1); while(m){ if(q[m].k){ num1=num2=0; for(LL j=q[m].r;j;j-=lowbit(j)) que1[++num1]=root[j]; for(LL j=q[m].l-1;j;j-=lowbit(j)) que2[++num2]=root[j]; printf("%lld\n",b[query( 1,cnt,q[m].k )]); }else{ add(q[m].now,-1), a[q[m].now]=q[m].val, add(q[m].now,1); } --m; } return 0;}