Advertisement
ThegeekKnight16

TTM

May 26th, 2023
923
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.53 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 1e5 + 10;
  4. vector<long long int> sum, lz;
  5. vector<int> e, d;
  6. int raiz[MAXN];
  7. long long int v[MAXN];
  8.  
  9. int create()
  10. {
  11.     sum.push_back(0LL);
  12.     e.push_back(0);
  13.     d.push_back(0);
  14.     lz.push_back(0LL);
  15.     return sum.size()-1;
  16. }
  17.  
  18. void copy(int pos, int novo)
  19. {
  20.     sum[novo] = sum[pos];
  21.     e[novo] = e[pos];
  22.     d[novo] = d[pos];
  23.     lz[novo] = lz[pos];
  24. }
  25.  
  26. void refresh(int pos, int ini, int fim)
  27. {
  28.     //cerr << "Entrou no refresh, ini: " << ini << ", fim: " << fim << '\n';
  29.     if (lz[pos] == 0) return;
  30.     //cerr << "sum Antes: " << sum[pos] << '\n';
  31.     sum[pos] += lz[pos] * (fim - ini + 1);
  32.     //cerr << "sum Depois: " << sum[pos] << '\n';
  33.  
  34.     if (ini != fim)
  35.     {
  36.         int novoE = create();
  37.         copy(e[pos], novoE);
  38.         e[pos] = novoE;
  39.         lz[e[pos]] += lz[pos];
  40.  
  41.         int novoD = create();
  42.         copy(d[pos], novoD);
  43.         d[pos] = novoD;
  44.         lz[d[pos]] += lz[pos];
  45.     }
  46.  
  47.     lz[pos] = 0;
  48. }
  49.  
  50. int update(int pos, int ini, int fim, int p, int q, long long int val)
  51. {
  52.     refresh(pos, ini, fim);
  53.     int novo = create();
  54.     copy(pos, novo);
  55.     //cerr << "ini: " << ini << ", fim: " << fim << '\n';
  56.     //cerr << sum[pos] << " " << sum[novo] << '\n';
  57.     //if (pos == 0) return novo;
  58.     if (q < ini || p > fim) return novo;
  59.     if (p <= ini && fim <= q)
  60.     {
  61.         lz[novo] += val;
  62.         refresh(novo, ini, fim);
  63.         return novo;
  64.     }
  65.  
  66.     int m = (ini + fim) >> 1;
  67.  
  68.     int aux = update(e[novo], ini, m, p, q, val);
  69.     e[novo] = aux;
  70.  
  71.     aux = update(d[novo], m+1, fim, p, q, val);
  72.     d[novo] = aux;
  73.  
  74.     sum[novo] = sum[e[novo]] + sum[d[novo]];
  75.     return novo;
  76. }
  77.  
  78. long long int query(int pos, int ini, int fim, int p, int q)
  79. {
  80.     refresh(pos, ini, fim);
  81.     if (pos == 0) return 0;
  82.     //cerr << "ini: " << ini << ", fim: " << fim << ", sum: " << sum[pos] <<'\n';
  83.     if (q < ini || p > fim) return 0;
  84.     if (p <= ini && fim <= q) return sum[pos];
  85.     int m = (ini + fim) >> 1;
  86.     return (query(e[pos], ini, m, p, q) + query(d[pos], m+1, fim, p, q));
  87. }
  88.  
  89. void build(int pos, int ini, int fim)
  90. {
  91.     if (ini == fim)
  92.     {
  93.         sum[pos] = v[ini];
  94.         return;
  95.     }
  96.     int m = (ini + fim) >> 1;
  97.  
  98.     if (e[pos] == 0)
  99.     {
  100.         int aux = create();
  101.         e[pos] = aux;
  102.     }
  103.  
  104.     if (d[pos] == 0)
  105.     {
  106.         int aux = create();
  107.         d[pos] = aux;
  108.     }
  109.  
  110.     build(e[pos], ini,  m );
  111.     build(d[pos], m+1, fim);
  112.  
  113.     sum[pos] = sum[e[pos]] + sum[d[pos]];
  114. }
  115.  
  116. int main()
  117. {
  118.     ios_base::sync_with_stdio(false);
  119.     cin.tie(NULL);
  120.     create(); raiz[0] = create();
  121.     int N, M;
  122.     cin >> N >> M;
  123.     for (int i = 1; i <= N; i++) cin >> v[i];
  124.     build(raiz[0], 1, N);
  125.  
  126.     int time = 0;
  127.     for (int m = 1; m <= M; m++)
  128.     {
  129.         char c;
  130.         cin >> c;
  131.         if (c == 'C')
  132.         {
  133.             int X, Y;
  134.             long long int val;
  135.             cin >> X >> Y >> val;
  136.             time++;
  137.             raiz[time] = update(raiz[time-1], 1, N, X, Y, val);
  138.         }
  139.         else if (c == 'Q')
  140.         {
  141.             int X, Y;
  142.             cin >> X >> Y;
  143.             cout << query(raiz[time], 1, N, X, Y) << '\n';
  144.         }
  145.         else if (c == 'H')
  146.         {
  147.             int X, Y, T;
  148.             cin >> X >> Y >> T;
  149.             cout << query(raiz[T], 1, N, X, Y) << '\n';
  150.         }
  151.         else if (c == 'B')
  152.         {
  153.             int T;
  154.             cin >> T;
  155.             time = T;
  156.         }
  157.     }
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement