fork download 
  1. #include <vector>
  2. #include <algorithm>
  3. #include <cstdio>
  4. using namespace std;
  5. typedef vector<int> vi;
  6. const int INF=987654321;
  7. struct RangeResult{ int m1, m2; };
  8. RangeResult merge(const RangeResult& a, const RangeResult& b){
  9. 	if( a.m1 < b.m1 ) return { b.m1, max(b.m2, a.m1) };
  10. 	else return { a.m1, max(a.m2, b.m1) };
  11. }
  12. struct snode {
  13.     int i, j; RangeResult res;
  14.     snode *l, *r;
  15.     ~snode() { delete l; delete r; }
  16.     snode(int i, int j, const vi& arr ): i(i), j(j) {
  17.         if (j - i == 1) {
  18.             l = r = NULL;
  19.             res = { arr[i], 0 };
  20.         } else {
  21.             int k = i + j >> 1;
  22.             l = new snode(i, k, arr);
  23.             r = new snode(k, j, arr);
  24.             res = merge(l->res, r->res);
  25.         }
  26.     }
  27.     void update(int P, int V){
  28.         if( i == P && j == P+1 ){
  29.             res = { V, 0 };
  30.         }else if( j <= P || P < i ){
  31.             return;
  32.         }else{
  33.         	if(l) l->update(P,V), r->update(P,V);
  34.         	res = merge( l->res, r->res );
  35.         }
  36.     }
  37.     RangeResult query(int I, int J){
  38.         if( I <= i && j <= J){
  39.             return res;
  40.         }else if( j <= I || J <= i ){
  41.             return {0,0};
  42.         }else{
  43.             return merge( l->query(I,J), r->query(I,J) );
  44.         }
  45.     }
  46. };
  47. struct segment {
  48.     snode *root;
  49.     segment() : root(0) {}
  50.     void init(int n, const vi& arr) {
  51.         if(root) delete root;
  52.         root = new snode(0, n, arr);
  53.     }
  54.     void update(int p, int v){
  55.     	root->update(p, v);
  56.     }
  57.     int query(int i, int j){
  58.         RangeResult res=root->query(i, j+1);
  59.         return res.m1+res.m2;
  60.     }
  61. };
  62. int N,Q, a,b; char cmd[3];
  63. int main() {
  64. 	scanf("%d",&N); vi A(N);
  65. 	for(int i=0;i<N;i++) scanf("%d",&A[i]);
  66. 	segment tree; tree.init(N, A);
  67. 	scanf("%d",&Q);
  68. 	while(Q--){
  69. 		scanf("%s%d%d",cmd,&a,&b);
  70. 		if(cmd[0]=='Q')
  71. 			printf("%d\n",tree.query(a-1, b-1));
  72. 		else if(cmd[0]=='U')
  73. 			tree.update(a-1, b);
  74. 	}
  75. 	return 0;
  76. }
Success #stdin #stdout 0s 3252KB
comments (?)
stdin 
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 
7
9
11
12
https://ideone.com/CuCdH7
http://w...content-available-to-author-only...j.com/problems/KGSS/
language:
C++14 (gcc 8.3)
created:
10 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!