fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #include <ext/pb_ds/detail/standard_policies.hpp>
  5.  
  6. const double pi = 3.141592653589793238462643383279;
  7. using namespace std;
  8. using namespace __gnu_pbds;
  9. //typedef
  10. //------------------------------------------
  11. typedef vector<int> VI;
  12. typedef vector<VI> VVI;
  13. typedef vector<string> VS;
  14. typedef pair<int, int> PII;
  15. typedef pair<long long, long long> PLL;
  16. typedef pair<int, PII> TIII;
  17. typedef long long LL;
  18. typedef unsigned long long ULL;
  19. typedef vector<LL> VLL;
  20. typedef vector<VLL> VVLL;
  21.  
  22.  
  23. //container util
  24. //------------------------------------------
  25. #define ALL(a)  (a).begin(),(a).end()
  26. #define RALL(a) (a).rbegin(), (a).rend()
  27. #define PB push_back
  28. #define MP make_pair
  29. #define SQ(a) ((a)*(a))
  30. #define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
  31. #define EXIST(s,e) ((s).find(e)!=(s).end())
  32. #define SORT(c) sort((c).begin(),(c).end())
  33.  
  34.  
  35. //repetition
  36. //------------------------------------------
  37. #define FOR(i,s,n) for(int i=s;i<(int)n;++i)
  38. #define REP(i,n) FOR(i,0,n)
  39. #define MOD 1000000007
  40.  
  41.  
  42. #define rep(i, a, b) for(int i = a; i < (b); ++i)
  43. #define trav(a, x) for(auto& a : x)
  44. #define all(x) x.begin(), x.end()
  45. #define sz(x) (int)(x).size()
  46.  
  47. typedef long long ll;
  48. typedef pair<int, int> pii;
  49. typedef vector<int> vi;
  50.  
  51. #define chmin(x,y) x=min(x,y)
  52. #define chmax(x,y) x=max(x,y)
  53.  
  54. const long double EPS = 1e-6, PI = acos((long double)-1);
  55.  
  56. //ここから編集
  57.  
  58. struct Node{
  59.   ll c1, c2, c3;
  60.   Node():c1(0),c2(0),c3(0){}
  61.   Node(int a, int b, int c):c1(a), c2(b), c3(c){}
  62.  
  63. };  
  64. template<typename T>
  65. struct LazySegmentTree{
  66.   const T INF = numeric_limits<T>::max();
  67.   int n0;
  68.   vector<Node> node;
  69.   vector<int> lazy;
  70.  
  71.   LazySegmentTree(int N){
  72.     int n = N;
  73.     n0 = 1;
  74.     while(n0 < n) n0 <<= 1;
  75.     node.resize(2*n0-1);
  76.     lazy.assign(2*n0-1, 0);
  77.     for(int i=0; i<n; i++) node[i+n0-1] = Node(1,0,0);
  78.     for(int i=n0-2; i>=0; i--) node[i] = Node(node[i*2+1].c1 + node[i*2+2].c1, 0, 0);
  79.   }
  80.  
  81.   void eval(int k){
  82.     lazy[k] %= 3;
  83.     if(lazy[k] == 0) return;
  84.  
  85.     if(lazy[k] == 1){
  86.       node[k] = Node(node[k].c3, node[k].c1, node[k].c2);
  87.     }else if(lazy[k] == 2){
  88.       node[k] = Node(node[k].c2, node[k].c3, node[k].c1);
  89.     }
  90.     if(k < n0-1){
  91.       lazy[k*2+1] += lazy[k];
  92.       lazy[k*2+2] += lazy[k];
  93.     }
  94.     lazy[k] = 0;
  95.   }
  96.  
  97.   void update(int a, int b, int k, int l, int r){
  98.     eval(k);
  99.     if(a <= l && r <= b){
  100.       lazy[k] += 1;
  101.       eval(k);
  102.     }else if(a < r && l < b) {
  103.       update(a, b, k*2+1, l, (l+r)/2);
  104.       update(a, b, k*2+2, (l+r)/2, r);
  105.       node[k] = Node(node[k*2+1].c1+node[k*2+2].c1,node[k*2+1].c2+node[k*2+2].c2,node[k*2+1].c3+node[k*2+2].c3);
  106.     }
  107.   }
  108.  
  109.   void update(int l, int r) { update(l, r, 0, 0, n0); }
  110.  
  111.   T query(int a, int b, int k, int l, int r){
  112.     eval(k);
  113.     if(r <= a || b <= l) return 0;
  114.     else if(a <= l && r <= b){
  115.       return node[k].c1;
  116.     }else{
  117.       T vl = query(a, b, k*2+1, l, (l+r)/2);
  118.       T vr = query(a, b, k*2+2, (l+r)/2, r);
  119.       return vl + vr;
  120.     }
  121.   }
  122.   T query(int l, int r) { return query(l, r, 0, 0, n0); }
  123.  
  124.   inline T operator[](int a) { return query(a, a + 1); }
  125. };
  126.  
  127.  
  128. int main() {
  129.   cin.tie(0);
  130.   ios::sync_with_stdio(false);
  131.   cout << fixed << setprecision(10);
  132.  
  133.   int N, Q; cin >> N >> Q;
  134.  
  135.   LazySegmentTree<ll> seg(N);
  136.   REP(i,Q){
  137.     int type, a, b;
  138.     cin >> type >> a >> b;
  139.     if(type == 0){
  140.       seg.update(a, b+1);
  141.     }else{
  142.       cout << seg.query(a, b+1) << endl;
  143.     }
  144.  
  145.   }
  146.   return 0;
  147. }
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3
stdout
copy 
4
1
0
2
https://ideone.com/Wn8CdR
problem MULTQ3, based on SPOJ submission 26592084 (CPP14), 2020-09-16 15:25:53
language:
C++14 (gcc 8.3)
created:
5 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!