fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. const int maxn = 100005;
  5.  
  6. namespace SegmentTree{
  7.     #define Left (node*2)
  8.     #define Right (node*2+1)
  9.     #define mid ((lo+hi)/2)
  10.  
  11.     ll lazy[maxn*5];
  12.     ll minTree[maxn*5];
  13.     ll maxTree[maxn*5];
  14.  
  15.     void build(int node, int lo, int hi){
  16.         minTree[node] = maxTree[node] = lazy[node] = 0;
  17.         if(lo == hi) return;
  18.         build(Left, lo, mid);
  19.         build(Right, mid+1, hi);
  20.     }
  21.  
  22.     void lazyPropagation(int node, int lo, int hi){
  23.         minTree[node] += lazy[node]; maxTree[node] += lazy[node];
  24.         if(lo != hi) {lazy[Left] += lazy[node]; lazy[Right] += lazy[node];}
  25.         lazy[node] = 0;
  26.     }
  27.  
  28.     void updateRange(int node, int lo, int hi, int i, int j, ll val){
  29.         lazyPropagation(node,lo,hi);
  30.         if(lo>hi || lo>j || hi<i) return;
  31.         if(lo>=i && hi<=j) {lazy[node] += val; lazyPropagation(node,lo,hi); return;}
  32.         updateRange(Left,lo,mid,i,j,val);
  33.         updateRange(Right,mid+1,hi,i,j,val);
  34.         minTree[node] = min(minTree[Left], minTree[Right]);
  35.         maxTree[node] = max(maxTree[Left], maxTree[Right]);
  36.     }
  37.  
  38.     ll queryMax(int node, int lo, int hi, int i, int j){
  39.         if(lo>hi || lo>j || hi<i) return LLONG_MIN;
  40.         lazyPropagation(node,lo,hi);
  41.         if(lo>=i && hi<=j) return maxTree[node];
  42.         ll p1 = queryMax(Left, lo, mid,i,j);
  43.         ll p2 = queryMax(Right,mid+1,hi,i,j);
  44.         return max(p1, p2);
  45.     }
  46.  
  47.     ll queryMin(int node, int lo, int hi, int i, int j){
  48.         if(lo>hi || lo>j || hi<i) return 0;
  49.         lazyPropagation(node,lo,hi);
  50.         if(lo>=i && hi<=j) return minTree[node];
  51.         ll p1 = queryMin(Left, lo, mid,i,j);
  52.         ll p2 = queryMin(Right,mid+1,hi,i,j);
  53.         return min(p1, p2);
  54.     }
  55. }
  56. using namespace SegmentTree;
  57.  
  58. ll a[maxn];
  59. int main(){
  60.     int t;
  61.     scanf("%d", &t);
  62.  
  63.     for(int cs=1; cs<=t; cs++){
  64.         int n, q;
  65.         scanf("%d %d", &n, &q);
  66.  
  67.         build(1, 1, n);
  68.         for(int i=1; i<=n; i++){
  69.             scanf("%lld", &a[i]);
  70.             updateRange(1, 1, n, i, n, a[i]);
  71.         }
  72.  
  73.         for(int i=1; i<=q; i++){
  74.             char cmd;
  75.             scanf(" %c", &cmd);
  76.  
  77.             if(cmd == 'U'){
  78.                 int x; ll y;
  79.                 scanf("%d %lld",&x, &y);
  80.                 updateRange(1, 1, n, x, n, y - a[x]);
  81.                 a[x] = y;
  82.             }
  83.             else{
  84.                 int l, r;
  85.                 scanf("%d %d",&l, &r);
  86.                 ll ret = queryMax(1, 1, n, r, n);
  87.                 ret -= queryMin(1, 1, n, 1, l-1);
  88.                 printf("%lld\n", ret);
  89.             }
  90.         }
  91.     }
  92. }
Success #stdin #stdout 0s 4480KB
comments (?)
stdin
copy 
1
5 5
-1 2 -2 1 -3
Q 3 5
Q 2 4
U 1 1
Q 2 4
Q 3 5
stdout
copy 
-2
1
2
-1
https://ideone.com/GmGmDA
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!