Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 1e5 + 10;
- vector<long long int> sum, lz;
- vector<int> e, d;
- int raiz[MAXN];
- long long int v[MAXN];
- int create()
- {
- sum.push_back(0LL);
- e.push_back(0);
- d.push_back(0);
- lz.push_back(0LL);
- return sum.size()-1;
- }
- void copy(int pos, int novo)
- {
- sum[novo] = sum[pos];
- e[novo] = e[pos];
- d[novo] = d[pos];
- lz[novo] = lz[pos];
- }
- void refresh(int pos, int ini, int fim)
- {
- //cerr << "Entrou no refresh, ini: " << ini << ", fim: " << fim << '\n';
- if (lz[pos] == 0) return;
- //cerr << "sum Antes: " << sum[pos] << '\n';
- sum[pos] += lz[pos] * (fim - ini + 1);
- //cerr << "sum Depois: " << sum[pos] << '\n';
- if (ini != fim)
- {
- int novoE = create();
- copy(e[pos], novoE);
- e[pos] = novoE;
- lz[e[pos]] += lz[pos];
- int novoD = create();
- copy(d[pos], novoD);
- d[pos] = novoD;
- lz[d[pos]] += lz[pos];
- }
- lz[pos] = 0;
- }
- int update(int pos, int ini, int fim, int p, int q, long long int val)
- {
- refresh(pos, ini, fim);
- int novo = create();
- copy(pos, novo);
- //cerr << "ini: " << ini << ", fim: " << fim << '\n';
- //cerr << sum[pos] << " " << sum[novo] << '\n';
- //if (pos == 0) return novo;
- if (q < ini || p > fim) return novo;
- if (p <= ini && fim <= q)
- {
- lz[novo] += val;
- refresh(novo, ini, fim);
- return novo;
- }
- int m = (ini + fim) >> 1;
- int aux = update(e[novo], ini, m, p, q, val);
- e[novo] = aux;
- aux = update(d[novo], m+1, fim, p, q, val);
- d[novo] = aux;
- sum[novo] = sum[e[novo]] + sum[d[novo]];
- return novo;
- }
- long long int query(int pos, int ini, int fim, int p, int q)
- {
- refresh(pos, ini, fim);
- if (pos == 0) return 0;
- //cerr << "ini: " << ini << ", fim: " << fim << ", sum: " << sum[pos] <<'\n';
- if (q < ini || p > fim) return 0;
- if (p <= ini && fim <= q) return sum[pos];
- int m = (ini + fim) >> 1;
- return (query(e[pos], ini, m, p, q) + query(d[pos], m+1, fim, p, q));
- }
- void build(int pos, int ini, int fim)
- {
- if (ini == fim)
- {
- sum[pos] = v[ini];
- return;
- }
- int m = (ini + fim) >> 1;
- if (e[pos] == 0)
- {
- int aux = create();
- e[pos] = aux;
- }
- if (d[pos] == 0)
- {
- int aux = create();
- d[pos] = aux;
- }
- build(e[pos], ini, m );
- build(d[pos], m+1, fim);
- sum[pos] = sum[e[pos]] + sum[d[pos]];
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- create(); raiz[0] = create();
- int N, M;
- cin >> N >> M;
- for (int i = 1; i <= N; i++) cin >> v[i];
- build(raiz[0], 1, N);
- int time = 0;
- for (int m = 1; m <= M; m++)
- {
- char c;
- cin >> c;
- if (c == 'C')
- {
- int X, Y;
- long long int val;
- cin >> X >> Y >> val;
- time++;
- raiz[time] = update(raiz[time-1], 1, N, X, Y, val);
- }
- else if (c == 'Q')
- {
- int X, Y;
- cin >> X >> Y;
- cout << query(raiz[time], 1, N, X, Y) << '\n';
- }
- else if (c == 'H')
- {
- int X, Y, T;
- cin >> X >> Y >> T;
- cout << query(raiz[T], 1, N, X, Y) << '\n';
- }
- else if (c == 'B')
- {
- int T;
- cin >> T;
- time = T;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement