fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int maxn = 1e5;
  5. ll a[maxn+5],n,q;
  6. struct segmentTree{
  7.     ll r[3] = {0,0,0};
  8.     ll lazy = 0;
  9. };
  10. segmentTree st[4*maxn+5];
  11. void push_up(ll id) {
  12.     st[id].r[0] = st[2*id].r[0] + st[2*id+1].r[0];
  13.     st[id].r[1] = st[2*id].r[1] + st[2*id+1].r[1];
  14.     st[id].r[2] = st[2*id].r[2] + st[2*id+1].r[2];
  15. }
  16. void switch_state(ll id, ll k) {
  17.     ll val0 = st[id].r[0];
  18.     ll val1 = st[id].r[1];
  19.     ll val2 = st[id].r[2];
  20.     st[id].r[(0+k)%3] = val0;
  21.     st[id].r[(1+k)%3] = val1;
  22.     st[id].r[(2+k)%3] = val2;
  23. }
  24. void push_down(ll id) {
  25.     ll val = st[id].lazy;
  26.     switch_state(2*id,val);
  27.     switch_state(2*id+1,val);
  28.     st[2*id].lazy+=val;
  29.     st[2*id+1].lazy+=val;
  30.     st[id].lazy = 0;
  31. }
  32. void build(ll id, ll l, ll r) {
  33.     if(l == r) {
  34.         st[id].r[0] = (a[l] % 3 == 0);
  35.         st[id].r[1] = (a[l] % 3 == 1);
  36.         st[id].r[2] = (a[l] % 3 == 2);
  37.         return;
  38.     }
  39.     ll m = (l+r)/2;
  40.     build(2*id,l,m);
  41.     build(2*id+1,m+1,r);
  42.     push_up(id);
  43. }
  44. void update(ll id, ll l, ll r, ll u, ll v){
  45.     if(r < u || v < l || r < l || v < u) return;
  46.     if(u <= l && r <= v) {
  47.         switch_state(id,1);
  48.         st[id].lazy++;
  49.         return;
  50.     }
  51.     ll m = (l+r)/2;
  52.     push_down(id);
  53.     update(2*id,l,m,u,v);
  54.     update(2*id+1,m+1,r,u,v);
  55.     push_up(id);
  56. }
  57. ll get(ll id, ll l, ll r, ll u, ll v) {
  58.     if(r < u || v < l || r < l || v < u) return 0;
  59.     if(u <= l && r <= v) return st[id].r[0];
  60.     ll m = (l+r)/2;
  61.     push_down(id);
  62.     return get(2*id,l,m,u,v) + get(2*id+1,m+1,r,u,v);
  63. }
  64. void AC() {
  65.     cin >> n >> q;
  66.     for(int i = 1; i <= n; i++) cin >> a[i];
  67.     build(1,1,n);
  68.     while(q--) {
  69.         ll type,l,r; cin >> type >> l >> r;
  70.         if(type == 1) update(1,1,n,l,r);
  71.         else cout << get(1,1,n,l,r) << '\n';
  72.     }
  73. }
  74. int main() {
  75.     ios::sync_with_stdio(false);
  76.     cin.tie(nullptr);
  77.     AC();
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 5528KB
comments (?)
stdin
copy 
5 3
1 2 2 3 2
2 2 4
1 1 5
2 3 5
stdout
copy 
1
2
https://ideone.com/tKGDwG
language:
C++ (gcc 8.3)
created:
3 hours 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!