fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define vi vector<int>
  3. #define va vector<ans>
  4. #define N 1000005
  5. using namespace std;
  6.  
  7. int n;
  8. struct ans{
  9.     //val: Value at the node in the original st
  10.     //lazy: Value at the node in the lazy st
  11.     int val, lazy;
  12.     ans(int _val=1, int _lazy=-1)
  13.         :val(_val), lazy(_lazy){}
  14. };
  15.  
  16. ans st[N<<2];
  17. int a[N];
  18.  
  19. ans op(ans u, ans v) {
  20.     ans w;
  21.     w.val = u.val + v.val;
  22.     return w;
  23. }
  24.  
  25. void propagate(int i,int l,int r)
  26. {
  27.     st[i].val += st[i].lazy * (r-l+1);
  28.     int lc = (i<<1) , rc = (i<<1)|1;
  29.     if(l != r){
  30.         st[lc].lazy += st[i].lazy,\
  31.         st[rc].lazy += st[i].lazy;
  32.     }
  33.     st[i].lazy = 0;
  34. }
  35.  
  36. void build(int i, int l, int r)
  37. {
  38.     if(l == r){
  39.         st[i].val = a[l];
  40.     }
  41.     else{
  42.         int lc = (i<<1) , rc = (i<<1)|1 , m = (l+r)>>1;
  43.         build(lc, l, m);
  44.         build(rc, m+1, r);
  45.         st[i] = op(st[lc], st[rc]);
  46.     }
  47. }
  48.  
  49. void update(int ql, int qr, int x, int i, int l,int r)
  50. {
  51.     propagate(i, l, r);
  52.  
  53.     int m = (l + r) >> 1;
  54.     int lc = i << 1, rc = (i << 1) | 1;
  55.  
  56.     if(ql <= l && qr >= r){
  57.         st[i].lazy = x;
  58.         propagate(i, l, r);
  59.         return;
  60.     }
  61.  
  62.     if(qr < l || ql > r)
  63.         return;
  64.     else{
  65.         update(ql, qr, x, lc, l, m);
  66.         update(ql, qr, x, rc, m+1, r);
  67.         st[i] = op(st[lc], st[rc]);
  68.     }
  69. }
  70.  
  71. ans query(int ql,int qr, int i, int l, int r)
  72. {
  73.     propagate(i, l, r);
  74.  
  75.     if(ql <= l && qr >= r)
  76.         return st[i];
  77.  
  78.     // if(qr < l || ql > r)
  79.     //  return ans();
  80.  
  81.     int m = (l + r) >> 1;
  82.     int lc = i << 1, rc = (i << 1) | 1;
  83.  
  84.     if(qr <= m)
  85.         return query(ql, qr, lc, l, m);
  86.     if(ql > m)
  87.         return query(ql, qr, rc, m+1, r);
  88.  
  89.     return op(query(ql,qr,lc,l,m), query(ql,qr,rc,m+1,r));
  90. }
  91.  
  92. /*void print_tree()
  93. {
  94.     for(int i=0;i<n;i++)
  95.         cerr << query(i, i, 1, 0, n-1).val <<'\n';
  96. }*/
  97.  
  98. main()
  99. {
  100.     cout << st[0].val << ' ' << st[0].lazy << '\n';
  101. }
  102.  
Success #stdin #stdout 0s 50392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 -1
https://ideone.com/uhnzKd
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!