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