fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define mp make_pair
  3. #define N 100001
  4. using namespace std;
  5. int a[N],n; pair<int,int> s[5*N];
  6. inline int scan(){
  7.     char c = getchar_unlocked();
  8.     int x = 0;
  9.     while(c<'0'||c>'9'){
  10.         c=getchar_unlocked();
  11.     }
  12.     while(c>='0'&&c<='9'){
  13.         x=(x<<1)+(x<<3)+c-'0';
  14.         c=getchar_unlocked();
  15.     }
  16.     return x;
  17. }
  18. void make(int l, int r, int node){
  19. 	if(l==r) s[node]=mp(a[l],l);
  20. 	else{
  21. 		int mid=l+r;
  22. 		mid/=2;
  23. 		make(l,mid,2*node);
  24. 		make(mid+1,r,1+ 2*node);
  25. 		s[node]=max(s[2*node], s[1+ 2*node]);
  26.       //  cout<<l<<" "<<r<<" "<<s[node].first<<" "<<s[node].second<<endl;
  27. 	}
  28. }
  29. void update(int l,int r,int node,int pos,int val){
  30.     if(l==r){
  31.         s[node]=mp(val,pos);
  32.     }
  33.     else{
  34.         int mid=(l+r)>>1;
  35.         int lc=node<<1;
  36.         int rc=lc|1;
  37.         if(mid>=pos){
  38.             update(l,mid,lc,pos,val);
  39.         }
  40.         else{
  41.             update(mid+1,r,rc,pos,val);
  42.         }
  43.         s[node]=max(s[lc],s[rc]);
  44.     }
  45. }
  46. pair<int,int> query(int start, int end, int node, int l, int r){
  47. 	if(l<=start && end<=r) return s[node];
  48. 	else if(l>end || r<start) return mp(-1,0);
  49. 	int mid=start+end;
  50. 	mid/=2;
  51. 	return max(query(start,mid,2*node,l,r),query(mid+1,end,1+ 2*node,l,r));
  52. }
  53. int main(){
  54. 	n=scan();
  55. 	for(int i=1; i<=n; i++) a[i]=scan();
  56. 	int q;
  57. 	q=scan();
  58. 	make(1,n,1);
  59.     //cout<<query(1,n,1,1,4).first;
  60. 	while(q--){
  61. 		char k;
  62. 		cin>>k;
  63. 		int l,r; l=scan(); r=scan();
  64. 		if(k=='Q'){
  65. 			int max_ind=query(1,n,1,l,r).second;
  66. 			int max_val=a[max_ind];
  67. 			int val=max_val;
  68.             //cout<<max_val<<endl;
  69. 			update(1,n,1,max_ind,-1);
  70. 			int max2_ind=query(1,n,1,l,r).second;
  71. 			int max2_val=a[max2_ind];
  72.             //cout<<max2_val<<endl;
  73. 			update(1,n,1,max_ind,max_val);
  74. 			cout<<max_val+max2_val<<endl;
  75.             //cout<<endl<<endl;
  76. 		}
  77. 		else{
  78. 			update(1,n,1,l,r);
  79. 			a[l]=r;
  80. 		} 
  81. 	}
  82. }
Success #stdin #stdout 0s 7032KB
comments (?)
stdin
copy 
5
1 2 3 4 5
6
Q 2 4
Q 2 5
U 1 6
Q 1 5
U 1 7
Q 1 5
stdout
copy 
7
9
11
12
https://ideone.com/F6UQE9
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!