fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define REP(i,a,b) for(i=a;i<b;i++)
  3. #define rep(i,n) REP(i,0,n)
  4. #define ll long long
  5. #define ull unsigned ll
  6. #define MAX 100005
  7. #define INF LONG_LONG_MAX
  8. using namespace std;
  9. ll arr[MAX],tree[4*MAX];
  10. inline ll scanll()
  11. {
  12.     ll n=0;
  13.     char ch=getchar_unlocked();
  14.     while(ch<'0'||ch>'9')
  15.         ch=getchar_unlocked();
  16.     while(ch>='0'&&ch<='9')
  17.     {
  18.         n=(n<<3)+(n<<1)+ch-'0';
  19.         ch=getchar_unlocked();
  20.     }
  21.     return n;
  22. }
  23. inline int scan()
  24. {
  25.     int n=0;
  26.     char ch=getchar_unlocked();
  27.     while(ch<'0'||ch>'9')
  28.         ch=getchar_unlocked();
  29.     while(ch>='0'&&ch<='9')
  30.     {
  31.         n=(n<<3)+(n<<1)+ch-'0';
  32.         ch=getchar_unlocked();
  33.     }
  34.     return n;
  35. }
  36.  
  37. inline void fastWrite(ll a)
  38. {
  39.     char snum[20];
  40.     int i=0;
  41.     do
  42.     {
  43.         snum[i++]=a%10+48;
  44.         a=a/10;
  45.     }
  46.     while(a!=0);
  47.     	i=i-1;
  48.     while(i>=0)
  49.         putchar_unlocked(snum[i--]);
  50.     putchar_unlocked('\n');
  51. }
  52. void build_tree(int node,int l,int r)
  53. {
  54. 	if(l>r)
  55. 		return;
  56. 	if(l==r)
  57. 	{
  58. 		tree[node]=arr[l];
  59. 		return;
  60. 	}
  61. 	build_tree(node*2,l,(l+r)/2);
  62. 	build_tree(node*2+1,(l+r)/2+1,r);
  63.  
  64. 	tree[node]=max(tree[node*2],tree[node*2+1]);
  65. }
  66. void update_tree(int node,int a,int b,int i,int j,ll val)
  67. {
  68. 	if(a>b || i>b || a>j)
  69. 		return;
  70. 	if(a==b)
  71. 	{
  72. 		tree[node]=val;
  73. 		return;
  74. 	}
  75. 	int mid=(a+b)/2;
  76. 	update_tree(node*2,a,mid,i,j,val);
  77. 	update_tree(node*2+1,mid+1,b,i,j,val);
  78.  
  79. 	tree[node]=max(tree[node*2],tree[node*2+1]);
  80. }
  81. void update_tree_max(int node,int a,int b,int i,int j,ll val)
  82. {
  83. 	if(a>b || i>b || a>j)
  84. 		return;
  85. 	if(a==b)
  86. 	{
  87. 		//cout<<tree[node]<<endl;
  88. 		if(val==tree[node])
  89. 			tree[node]=-INF;
  90. 		return;
  91. 	}
  92. 	int mid=(a+b)/2;
  93. 	update_tree_max(node*2,a,mid,i,j,val);
  94. 	update_tree_max(node*2+1,mid+1,b,i,j,val);
  95. 	tree[node]=max(tree[node*2],tree[node*2+1]);
  96. }
  97. void update_tree_original(int node,int a,int b,int i,int j,ll val)
  98. {
  99. 	if(a>b || i>b || a>j)
  100. 		return;
  101. 	if(a==b)
  102. 	{
  103. 		if(-INF==tree[node])
  104. 			tree[node]=val;
  105. 		return;
  106. 	}
  107. 	int mid=(a+b)/2;
  108. 	update_tree_original(node*2,a,mid,i,j,val);
  109. 	update_tree_original(node*2+1,mid+1,b,i,j,val);
  110.  
  111. 	tree[node]=max(tree[node*2],tree[node*2+1]);
  112. }
  113. ll query_tree(int node,int a,int b,int i,int j)
  114. {
  115. 	if(a>b || a>j || b<i)
  116. 		return -INF;
  117. 	if(a>=i && b<=j)
  118. 	{
  119. 		return tree[node];
  120. 	}
  121. 	int left=query_tree(node*2,a,(a+b)/2,i,j);
  122. 	int right=query_tree(node*2+1,(a+b)/2+1,b,i,j);
  123. 	int res=max(left,right);
  124. 	return res;
  125. }
  126. int main()
  127. {
  128. 	int n,i,q;
  129. 	n=scan();
  130. 	rep(i,n)
  131. 		arr[i]=scanll();
  132. 	build_tree(1,0,n-1);
  133. 	q=scan();
  134. 	while(q--)
  135. 	{
  136. 		char ch;
  137. 		scanf("%c",&ch);
  138. 		int x,y;
  139. 		ll val;
  140. 		if(ch=='U')
  141. 		{
  142. 			x=scan();
  143. 			val=scanll();
  144. 			--x;
  145. 			update_tree(1,0,n-1,x,x,val);
  146. 		}
  147. 		else
  148. 		{
  149. 			x=scan();
  150. 			y=scan();
  151. 			--x;
  152. 			--y;
  153. 			ll first=0,ans=0;
  154. 			first=query_tree(1,0,n-1,x,y);
  155. 			update_tree_max(1,0,n-1,x,y,first);
  156. 			ans=query_tree(1,0,n-1,x,y)+first;
  157. 			update_tree_original(1,0,n-1,x,y,first);
  158. 			fastWrite(ans);
  159. 		}
  160. 	}
  161. 	return 0;
  162. }
Success #stdin #stdout 0s 7008KB
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/HIQ6uD
language:
C++14 (gcc 8.3)
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!