Input
Output
对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。
Sample Input
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
6
HINT
Source
用以上的知识就可以解决了
#include <bits/stdc++.h> #define ll long long using namespace std; inline int read(){ int x=0;int f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return x*f; } const int MAXN=5e5+10; struct Chair_Man_Tree{ int son[2],sum; }T[MAXN]; struct node{ int a,b,k; char op; }Q[MAXN]; int arr[MAXN],fsort[MAXN],root[MAXN],rsum=0,sum=0,n,m,cnt=0,top[2],prevL[MAXN],prevR[MAXN]; namespace zhangenming{ inline int lowbit(int x) {return x&-x;} void init(){ n=read();m=read(); sum=n; for(int i=1;i<=n;i++){ fsort[i]=arr[i]=read(); } for(int i=1;i<=m;i++){ char op[5]; scanf("%s",op); Q[i].op=op[0];Q[i].a=read();Q[i].b=read(); if(op[0]=='Q') Q[i].k=read(); else fsort[++sum]=Q[i].b; } sort(fsort+1,fsort+sum+1); rsum=unique(fsort+1,fsort+sum+1)-fsort-1; } inline int Newnode(int sum,int son0,int son1){ T[++cnt].sum=sum;T[cnt].son[0]=son0; T[cnt].son[1]=son1;return cnt; } inline void build(int &root,int last,int pos,int leftt,int rightt){ root=Newnode(T[last].sum+1,T[last].son[0],T[last].son[1]); if(leftt==rightt) return; int mid=(rightt+leftt)>>1; if(pos<=mid) build(T[root].son[0],T[last].son[0],pos,leftt,mid); else build(T[root].son[1],T[last].son[1],pos,mid+1,rightt); } inline int Get(int leftt,int rightt,int rnk){ if(leftt==rightt) return leftt; int summ=0; for(int i=1;i<=top[0];i++) summ-=T[T[prevL[i]].son[0]].sum; for(int i=1;i<=top[1];i++) summ+=T[T[prevR[i]].son[0]].sum; int mid=(leftt+rightt)>>1; if(rnk<=summ){ for(int i=1;i<=top[0];i++) prevL[i]=T[prevL[i]].son[0]; for(int i=1;i<=top[1];i++) prevR[i]=T[prevR[i]].son[0]; return Get(leftt,mid,rnk); } else{ for(int i=1;i<=top[0];i++) prevL[i]=T[prevL[i]].son[1]; for(int i=1;i<=top[1];i++) prevR[i]=T[prevR[i]].son[1]; return Get(mid+1,rightt,rnk-summ); } } int k=0; inline void insert(int leftt,int rightt,int &root,int pos,int val){ if(!root) root=Newnode(0,0,0); T[root].sum+=val; if(leftt==rightt) return; int mid=(rightt+leftt)>>1; if(pos<=mid) insert(leftt,mid,T[root].son[0],pos,val); else insert(mid+1,rightt,T[root].son[1],pos,val); } void solve(){ for(int i=1;i<=n;i++){ arr[i]=lower_bound(fsort+1,fsort+rsum+1,arr[i])-fsort; build(root[i+n],root[i+n-1],arr[i],1,rsum); } for(int i=1;i<=m;i++){ if(Q[i].op=='Q'){ top[0]=top[1]=0; prevL[++top[0]]=root[((Q[i].a-1)==0?0:Q[i].a+n-1)]; prevR[++top[1]]=root[Q[i].b+n]; for(int j=Q[i].a-1;j>=1;j-=lowbit(j)){ prevL[++top[0]]=root[j]; } for(int j=Q[i].b;j>=1;j-=lowbit(j)){ prevR[++top[1]]=root[j]; } printf("%d\n",fsort[Get(1,rsum,Q[i].k)]); } else{ for(int j=Q[i].a;j<=n;j+=lowbit(j)){ insert(1,rsum,root[j],arr[Q[i].a],-1); } arr[Q[i].a]=lower_bound(fsort+1,fsort+1+rsum,Q[i].b)-fsort; for(int j=Q[i].a;j<=n;j+=lowbit(j)){ insert(1,rsum,root[j],arr[Q[i].a],1); } } } } } int main(){ //freopen("All.in","r",stdin); //freopen("bai.out","w",stdout); using namespace zhangenming; init(); solve(); return 0; }
优质内容筛选与推荐>>
1、SQL server 2000异地备份
2、python第3天:数据类型
3、通过假日去获得交易日
4、robotframework自动化系列:文本类型的下拉框
5、solr的认识、linux下安装、java下使用(含下载资源)