本文共 2213 字，大约阅读时间需要 7 分钟。
权值线段树套区间线段树的裸题，加了离散化就好了
#include #include #include #include using namespace std;void read(int &x) { char ch; bool ok; for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1; for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;}#define rg registerconst int maxn=1e5+10;int n,m,id,nmp[maxn*2],x[maxn],y[maxn],z[maxn],num,a[maxn],b[maxn*2],ls[maxn*20],rs[maxn*20],sum[maxn*20],rt[maxn*4];char op[maxn][3];struct segment_tree{ void update(int x){sum[x]=sum[ls[x]]+sum[rs[x]];} void change(int &k,int l,int r,int a,int b) { if(!k)k=++id;int mid=(l+r)>>1; if(l==r){sum[k]+=b;return ;} if(a<=mid)change(ls[k],l,mid,a,b); else change(rs[k],mid+1,r,a,b); update(k); } int get(int x,int l,int r,int a,int b) { if(!x)return 0;int mid=(l+r)>>1,ans=0; if(a<=l&&b>=r)return sum[x]; if(a<=mid)ans+=get(ls[x],l,mid,a,b); if(b>mid)ans+=get(rs[x],mid+1,r,a,b); return ans; }}s[maxn*4];map mp;void change(int x,int l,int r,int a,int b,int c){ s[x].change(rt[x],1,n,a,c); if(l==r)return ;int mid=(l+r)>>1; if(b<=mid)change(x<<1,l,mid,a,b,c); else change(x<<1|1,mid+1,r,a,b,c);}int get(int x,int l,int r,int a,int b,int c){ if(l==r)return l;int mid=(l+r)>>1,now=s[x<<1].get(rt[x<<1],1,n,a,b); if(c<=now)return get(x<<1,l,mid,a,b,c); else return get(x<<1|1,mid+1,r,a,b,c-now);}int main(){ read(n),read(m);num=n; for(rg int i=1;i<=n;i++)read(a[i]),b[i]=a[i]; for(rg int i=1;i<=m;i++) { scanf("%s",op[i]+1),read(x[i]),read(y[i]); if(op[i][1]=='Q')read(z[i]); else b[++num]=y[i]; } sort(b+1,b+num+1);int tot=0; for(rg int i=1;i<=num;i++)if(b[i]!=b[i-1])mp[b[i]]=++tot,nmp[tot]=b[i]; for(rg int i=1;i<=n;i++)change(1,0,num,i,mp[a[i]],1); for(rg int i=1;i<=m;i++) { if(op[i][1]=='C') { change(1,0,num,x[i],mp[a[x[i]]],-1); a[x[i]]=y[i]; change(1,0,num,x[i],mp[a[x[i]]],1); } else printf("%d\n",nmp[get(1,0,num,x[i],y[i],z[i])]); }}
转载于:https://www.cnblogs.com/lcxer/p/10422040.html