API tools faq
paste
Advertisement
Abrar_Al_Samit

Multiples of 3 (SPOJ)

Abrar_Al_Samit
Jun 8th, 2021
169
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.38 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8.  
  9. #define debug(x) cerr << '[' << (#x) << "] = " << x << '\n';
  10.  
  11. template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;
  12.  
  13. struct Data{
  14.     int mod[3] = {0};
  15. };
  16.  
  17. const int maxn = 100005;
  18. Data segment_tree[maxn<<2];
  19. int lazy[maxn<<2];
  20. void toggle(int extent, Data& a) {
  21.     while(extent-->0)
  22.         swap(a.mod[2], a.mod[1]), swap(a.mod[0], a.mod[1]);
  23. }
  24. Data combine(Data a, Data b) {
  25.     for(int i=0; i<3; ++i) a.mod[i] += b.mod[i];
  26.     return a;
  27. }
  28. void update(int l, int r, int L, int R, int node) {
  29.     if(r<L || l>R) return;
  30.     if(l>=L && r<=R) {
  31.         ++lazy[node];
  32.         lazy[node] %= 3;
  33.         toggle(1, segment_tree[node]);
  34.         return;
  35.     }
  36.     int mid = (l+r)>>1;
  37.     update(l, mid, L, R, node*2);
  38.     update(mid+1, r, L, R, node*2+1);
  39.     segment_tree[node] = combine(segment_tree[node*2], segment_tree[node*2+1]);
  40.     toggle(lazy[node], segment_tree[node]);
  41. }
  42. Data query(int l, int r, int L, int R, int node) {
  43.     if(l>R || r<L) {
  44.         Data ret;
  45.         return ret;
  46.     }
  47.     if(l>=L && r<=R) {
  48.         return segment_tree[node];
  49.     }
  50.     int mid = (l+r)>>1;
  51.     Data ret = combine(query(l, mid, L, R, node*2), query(mid+1, r, L, R, node*2+1));
  52.     toggle(lazy[node], ret);
  53.     return ret;
  54. }
  55. void build(int l, int r, int node) {
  56.     if(l==r) {
  57.         segment_tree[node].mod[0] = 1;
  58.         return;
  59.     }
  60.     int mid = (l+r)>>1;
  61.     build(l, mid, node*2);
  62.     build(mid+1, r, node*2+1);
  63.     segment_tree[node].mod[0] = r-l+1;
  64. }
  65. void PlayGround() {
  66.     int n, q; cin >> n >> q;
  67.     build(1, n, 1);
  68.     while(q--) {
  69.         int type; cin >> type;
  70.         if(type==1) {
  71.             int l, r; cin >> l >> r;
  72.             ++l, ++r;
  73.             Data got = query(1, n, l, r, 1);
  74.             cout << got.mod[0] << '\n';
  75.         } else {
  76.             int l, r; cin >> l >> r;
  77.             ++l, ++r;
  78.             update(1, n, l, r, 1);
  79.         }
  80.     }
  81.     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  82. }
  83. int main() {
  84.     ios_base::sync_with_stdio(0);
  85.     cin.tie(0);
  86.     cout.tie(0);
  87.     #ifndef ONLINE_JUDGE
  88.         freopen("input.txt", "r", stdin);
  89.     #endif
  90.     PlayGround();
  91.     return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!