Problem Description

There are

N boys in CodeLand.

Boy i has his coding skill Ai.

CRB wants to know who has the suitable coding skill.

So you should treat the following two types of queries.

Query 1: 1 l v

The coding skill of Boy l has changed to v.

Query 2: 2 l r k

This is a report query which asks the k-th smallest value of coding skill between Boy l and Boy r(both inclusive).

Input

There are multiple test cases.

The first line contains a single integer

N.

Next line contains N space separated integers A1, A2, …, AN, where Ai denotes initial coding skill of Boy i.

Next line contains a single integer Q representing the number of queries.

Next Q lines contain queries which can be any of the two types.

1 ≤ N, Q ≤ 105

1 ≤ Ai, v ≤ 109

1 ≤ l ≤ r ≤ N

1 ≤ k ≤ r – l + 1

 

Output

For each query of type 2, output a single integer corresponding to the answer in a single line.

 

Sample Input

5 1 2 3 4 5 3 2 2 4 2 1 3 6 2 2 4 2

Sample Output

3 4

 

题解:

按时间顺序加入,所有的修改拆成删除和添加两个操作,分别对应树状数组中的加减.

维护时间顺序即可

1 #include 
       
          2 #include 
        
           3 #include 
         
            4 #include 
          
             5 #include 
           
              6 #include 
            
              7 using namespace std; 8 const int N=100005; 9 int gi(){ 10 int str=0;char ch=getchar(); 11 while(ch>'9' || ch<'0')ch=getchar(); 12 while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar(); 13 return str; 14 } 15 int n,m,a[N],top=0,ans[N]; 16 struct node{ 17 int x,y,cnt,k,id; 18 }t[N*4],q1[N*4],q2[N*4]; 19 int Tree[N*4]; 20 void add(int sta,int ad){ 21 for(int i=sta;i<=n;i+=(i&(-i)))Tree[i]+=ad; 22 } 23 int getsum(int sta){ 24 int sum=0; 25 for(int i=sta;i>=1;i-=(i&(-i)))sum+=Tree[i]; 26 return sum; 27 } 28 int l1=0,l2=0; 29 void count(int ll,int rr,int dl,int dr) 30 { 31 for(int i=ll;i<=rr;i++) 32 { 33 if(t[i].k) 34 t[i].cnt=getsum(t[i].y)-getsum(t[i].x-1); 35 else if(t[i].y<=dr) 36 add(t[i].x,t[i].cnt); 37 } 38 for(int i=ll;i<=rr;i++) 39 if(!t[i].k && t[i].y<=dr) 40 add(t[i].x,-t[i].cnt); 41 l1=0;l2=0; 42 for(int i=ll;i<=rr;i++) 43 { 44 if(t[i].k) 45 { 46 if(t[i].cnt>=t[i].k) 47 q1[++l1]=t[i]; 48 else 49 t[i].k-=t[i].cnt,q2[++l2]=t[i]; 50 } 51 else 52 { 53 if(t[i].y<=dr) 54 q1[++l1]=t[i]; 55 else 56 q2[++l2]=t[i]; 57 } 58 } 59 int now=ll-1; 60 for(int i=1;i<=l1;i++) 61 t[++now]=q1[i]; 62 for(int i=1;i<=l2;i++) 63 t[++now]=q2[i]; 64 } 65 void div(int ll,int rr,int dl,int dr) 66 { 67 if(dl==dr) 68 { 69 for(int i=ll;i<=rr;i++) 70 if(t[i].k)ans[t[i].id]=dl; 71 return ; 72 } 73 int mid=(dl+dr)>>1; 74 count(ll,rr,dl,mid); 75 int to=l1; 76 if(to) 77 div(ll,ll+to-1,dl,mid); 78 if(to<=rr-ll) 79 div(ll+to,rr,mid+1,dr); 80 } 81 void Clear(){ 82 top=0; 83 memset(ans,0,sizeof(ans)); 84 memset(t,0,sizeof(t)); 85 } 86 void work() 87 { 88 Clear(); 89 for(int i=1;i<=n;i++) 90 { 91 a[i]=gi(); 92 t[++top]=((node){i,a[i],1,0,0}); 93 } 94 m=gi(); 95 int flag,x,y,z; 96 for(int i=1;i<=m;i++) 97 { 98 flag=gi(); 99 if(flag==1)100 {101 x=gi();y=gi();102 t[++top]=((node){x,a[x],-1,0,0});103 t[++top]=((node){x,y,1,0,0});104 a[x]=y;105 }106 else107 {108 x=gi();y=gi();z=gi();109 t[++top]=(node){x,y,0,z,i};110 }111 }112 div(1,top,1,1e9);113 for(int i=1;i<=m;i++)if(ans[i])printf("%d\n",ans[i]);114 }115 int main()116 {117 while(~scanf("%d",&n))118 work();119 return 0;120 }
            
           
          
         
        
       

 

还有主席树维护的树状数组，但是MLE,这种题目如果数据小可以用

 

1 #include 
       
          2 #include 
        
           3 #include 
         
            4 #include 
          
             5 #include 
           
              6 #include 
            
              7 using namespace std; 8 const int N=100001; 9 int n,m,a[N],b[N<<1]; 10 struct Ques{ 11 int flag,x,y,k; 12 }q[N]; 13 int num=0,bel[N]; 14 int getrank(int x){ 15 int l=1,r=num,mid; 16 while(l<=r) 17 { 18 mid=(l+r)>>1; 19 if(b[mid]==x)return mid; 20 if(x>b[mid])l=mid+1; 21 else r=mid-1; 22 } 23 } 24 struct Tree{ 25 int ls,rs,cnt; 26 }t[N*600]; 27 int root[N],tot=0; 28 void add(int &rt,int l,int r,int val,int ad) 29 { 30 t[++tot]=t[rt];rt=tot;t[rt].cnt+=ad; 31 if(l==r)return ; 32 int mid=(l+r)>>1; 33 if(val<=mid)add(t[rt].ls,l,mid,val,ad); 34 else add(t[rt].rs,mid+1,r,val,ad); 35 } 36 void updata(int sta,int val,int ad) 37 { 38 for(int i=sta;i<=n;i+=(i&(-i)))add(root[i],1,num,val,ad); 39 } 40 int nl[N],nr[N]; 41 int query(int ll,int rr,int rank) 42 { 43 int l=1,r=num,mid; 44 int lenl=0,lenr=0,sl,sr; 45 for(int i=ll;i>=1;i-=(i&(-i)))nl[++lenl]=root[i]; 46 for(int i=rr;i>=1;i-=(i&(-i)))nr[++lenr]=root[i]; 47 while(l
             
              >1; 50 sl=sr=0; 51 for(int i=1;i<=lenl;i++)sl+=t[t[nl[i]].ls].cnt; 52 for(int i=1;i<=lenr;i++)sr+=t[t[nr[i]].ls].cnt; 53 if(sr-sl>=rank) 54 { 55 for(int i=1;i<=lenl;i++)nl[i]=t[nl[i]].ls; 56 for(int i=1;i<=lenr;i++)nr[i]=t[nr[i]].ls; 57 r=mid; 58 } 59 else 60 { 61 for(int i=1;i<=lenl;i++)nl[i]=t[nl[i]].rs; 62 for(int i=1;i<=lenr;i++)nr[i]=t[nr[i]].rs; 63 l=mid+1;rank-=sr-sl; 64 } 65 } 66 return b[r]; 67 } 68 void Clear() 69 { 70 tot=0;num=0; 71 memset(root,0,sizeof(root)); 72 memset(t,0,sizeof(t)); 73 } 74 void work() 75 { 76 Clear(); 77 for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[++num]=a[i]; 78 scanf("%d",&m); 79 for(int i=1;i<=m;i++) 80 { 81 scanf("%d",&q[i].flag); 82 if(q[i].flag==2){ 83 scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].k); 84 } 85 else{ 86 scanf("%d%d",&q[i].x,&q[i].y); 87 b[++num]=q[i].y; 88 } 89 } 90 sort(b+1,b+num+1); 91 for(int i=1;i<=n;i++)bel[i]=getrank(a[i]); 92 for(int i=1;i<=n;i++)updata(i,bel[i],1); 93 for(int i=1;i<=m;i++) 94 { 95 if(q[i].flag==1) 96 { 97 updata(q[i].x,bel[q[i].x],-1); 98 updata(q[i].x,q[i].y=getrank(q[i].y),1); 99 bel[q[i].x]=q[i].y;100 }101 else102 printf("%d\n",query(q[i].x-1,q[i].y,q[i].k));103 }104 }105 int main()106 {107 //freopen("pp.in","r",stdin);108 //freopen("pp.out","w",stdout);109 while(~scanf("%d",&n))110 work();111 return 0;112 }