SHARE
TWEET

Untitled

a guest Oct 21st, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using namespace std;
  2. #include                    <bits/stdc++.h>
  3. #define     DB(x)           cerr << #x << " is " << (x) << endl;
  4. #define     FIO             ios::sync_with_stdio(false);// cin.tie(nullptr); cout.tie(nullptr) // ===  === === === === === ===>
  5. #define     pb              push_back
  6. #define     fs              first
  7. #define     sc              second
  8. #define     endl            "\n"
  9. typedef     long long           ll;
  10. typedef     long double         ld;
  11. int const mxn = 1e5+2;
  12. int const mod = 1e9+7;
  13.  
  14. struct NOde{
  15.     int s, mx, mn;
  16. };
  17.  
  18. int n, q, aa[mxn];
  19. NOde tt[mxn<<2];
  20.  
  21. NOde Join(NOde a, NOde b){
  22.     NOde rs;
  23.     rs.mn = min(a.mn,b.mn);
  24.     rs.mx = max(a.mx,b.mx);
  25.     rs.s = a.s + b.s;
  26.     return rs;
  27. }
  28.  
  29. void Build(int l, int r, int idx){
  30.     if (l == r){
  31.         tt[idx].s = tt[idx].mn = tt[idx].mx = aa[l];
  32.         return;
  33.     }  
  34.     int mid = (l+r)>>1;
  35.     Build(l,mid,idx*2);
  36.     Build(mid+1,r,idx*2+1);
  37.     tt[idx] = Join(tt[idx*2],tt[idx*2+1]);
  38. }
  39.  
  40. NOde Query(int l, int r, int u, int v, int idx){
  41.     if (l > v || r < u) return {0,INT_MIN,INT_MAX};
  42.     if (u <= l && r <= v) return tt[idx];
  43.     int mid = (l+r)>>1;
  44.     return Join(Query(l,mid,u,v,idx*2), Query(mid+1,r,u,v,idx*2+1));
  45. }
  46.  
  47. void Update(int l, int r, int idx, int pos, int val){
  48.     if (l == r){
  49.         tt[idx].mn = tt[idx].mx = tt[idx].s = val;
  50.         aa[l] = val;
  51.         return;
  52.     }
  53.     int mid = (l+r)>>1;
  54.     if (pos <= mid) Update(l,mid,idx*2,pos,val);
  55.     else Update(mid+1,r,idx*2+1,pos,val);
  56.     tt[idx] = Join(tt[idx*2],tt[idx*2+1]);
  57. }
  58.  
  59. void SOL(){
  60.     cin >> n >> q;
  61.     for (int i=1; i<=n; ++i){
  62.         cin >> aa[i];
  63.     }
  64.     Build(1,n,1);
  65.     for (int i=1; i<=q; ++i){
  66.         int x, l, r; cin >> x >> l >> r;
  67.         if (x == 1){
  68.             NOde node = Query(1,n,l,r,1);
  69.             cout << node.s - node.mx - node.mn << "\n";
  70.         } else {
  71.             Update(1,n,1,l,r);
  72.         }
  73.     }
  74. }  
  75. /*
  76. */
  77. int main(){FIO; SOL(); return 0;}
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top