Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <time.h>
- #include <stdlib.h>
- #include <string>
- #include <algorithm>
- #include <queue>
- using namespace std;
- const long long INF = 1e17;
- #define mINF -10000000000
- #define pb push_back
- #define mp make_pair
- struct Treap {
- long long x, y, cnt, summ;
- pair<bool, int> usdd;
- Treap* leftp;
- Treap* rightp;
- }; // Treap* nw = new Treap({ value, rand(), 1, mINF, 0, value, NULL, NULL });
- long long cnt(Treap* Treap) {
- if (Treap == NULL)
- return 0;
- else
- return Treap->cnt;
- }
- long long summ(Treap* Treap) {
- if (Treap == NULL)
- return 0;
- else
- return Treap->summ;
- }
- void pushg2(Treap* root, pair<bool, int> sd)
- {
- if (!sd.first)
- {
- root->usdd.second += sd.second;
- }
- else
- {
- root->usdd.first = sd.first;
- root->usdd.second = sd.second;
- }
- }
- void pushg(Treap* root, pair<bool, int> sd)
- {
- if (!sd.first)
- {
- root->usdd.second += sd.second;
- root->summ += root->cnt * sd.second;
- }
- else
- {
- root->usdd.first = sd.first;
- root->usdd.second = sd.second;
- root->summ = root->cnt * sd.second;
- }
- }
- void push_summ(Treap* Treap) {
- if (Treap != NULL)
- {
- if (!Treap->usdd.first)
- {
- Treap->summ += Treap->cnt * Treap->usdd.second;
- Treap->x += Treap->usdd.second;
- }
- else
- {
- Treap->summ = Treap->cnt * Treap->usdd.second;
- Treap->x = Treap->usdd.second;
- }
- if (Treap->leftp != NULL)
- {
- pushg(Treap->leftp, Treap->usdd);
- }
- if (Treap->rightp != NULL)
- {
- pushg(Treap->rightp, Treap->usdd);
- }
- Treap->usdd = mp(0,0);
- }
- }
- void upd_cnt(Treap* Treap)
- {
- if (Treap != NULL) Treap->cnt = 1 + cnt(Treap->rightp) + cnt(Treap->leftp);
- }
- void upd_summ(Treap* Treap)
- {
- if (Treap != NULL) Treap->summ = summ(Treap->rightp) + summ(Treap->leftp) + Treap->x;
- }
- void recalc(Treap* Treap) {
- push_summ(Treap);
- upd_cnt(Treap);
- upd_summ(Treap);
- }
- pair<Treap*, Treap*> split(Treap *root, long long x, long long summ = 0)
- {
- recalc(root);
- if (root == NULL) {
- return{ NULL, NULL };
- }
- long long id = summ + cnt(root->leftp);
- if (id < x) {
- auto res = split(root->rightp, x, id + 1);
- root->rightp = res.first;
- recalc(root);
- return{ root, res.second };
- }
- else {
- auto res = split(root->leftp, x, summ);
- root->leftp = res.second;
- recalc(root);
- return{ res.first, root };
- }
- }
- Treap* Merge(Treap* l, Treap* r) {
- recalc(l);
- recalc(r);
- if (l == NULL) {
- return r;
- }
- if (r == NULL) {
- return l;
- }
- if (l->y > r->y) {
- l->rightp = Merge(l->rightp, r);
- recalc(l);
- return l;
- }
- else {
- r->leftp = Merge(l, r->leftp);
- recalc(r);
- return r;
- }
- }
- Treap* Insert(Treap* root, long long value, long long x) {
- auto spl = split(root, x);
- pair <bool, int> d;
- Treap* nw = new Treap({ value, rand(), 1, value, d, NULL, NULL });
- auto a = Merge(Merge(spl.first, nw), spl.second);
- recalc(a);
- return a;
- }
- Treap* del(Treap* root, long long l, long long r) {
- auto spl1 = split(root, l);
- auto spl2 = split(spl1.second, r - l);
- auto a = Merge(spl1.first, spl2.second);
- recalc(a);
- return a;
- }
- Treap* get_sumd(Treap* root, long long l, long long r, long long x) {
- auto spl1 = split(root, l);
- auto spl2 = split(spl1.second, r - l);
- pushg2(spl2.first, mp(0, x));
- auto a = Merge(spl1.first, Merge(spl2.first, spl2.second));
- push_summ(a);
- recalc(a);
- return a;
- }
- Treap* get_vd(Treap* root, long long l, long long r, long long x) {
- auto spl1 = split(root, l);
- auto spl2 = split(spl1.second, r - l);
- pushg2(spl2.first, mp(1, x));
- auto a = Merge(spl1.first, Merge(spl2.first, spl2.second));
- recalc(a);
- return a;
- }
- long long get_sum(Treap* root, long long l, long long r) {
- auto spl1 = split(root, l);
- auto spl2 = split(spl1.second, r - l);
- auto ans = summ(spl2.first);
- root = Merge(spl1.first, Merge(spl2.first, spl2.second));
- return ans;
- }
- Treap* sdv(Treap* root, long long l, long long r, long long q)
- {
- recalc(root);
- auto spl1 = split(root, l);
- auto spl2 = split(spl1.second, r - l);
- auto spl3 = split(spl2.first, r - l - q);
- auto a = Merge(spl1.first, Merge(Merge(spl3.second, spl3.first), spl2.second));
- recalc(a);
- return a;
- }
- void output(Treap* t) {
- if (!t) return;
- push_summ(t);
- output(t->leftp);
- cout << t->x << " ";
- output(t->rightp);
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- srand(time(NULL));
- long long n, h;
- char rt;
- cin >> n;
- Treap* root = NULL;
- long long l, r;
- for (int i = 0; i < n; i++)
- {
- cin >> rt;
- if (rt == '0')
- {
- cin >> l >> r >> h;
- l--;
- root = get_vd(root, l, r, h);
- //output(root);
- //cout << endl;
- }
- if (rt == '1')
- {
- cin >> l >> r >> h;
- l--;
- root = get_sumd(root, l, r, h);
- //output(root);
- //cout << endl;
- }
- if (rt == '2')
- {
- cin >> l >> h;
- l--;
- root = Insert(root, h, l);
- //output(root);
- //cout << endl;
- }
- if (rt == '3')
- {
- cin >> l >> r;
- l--;
- cout << get_sum(root, l, r) << "\n";
- //output(root);
- //cout << endl;
- }
- if (rt == 'X')
- {
- cin >> l >> r >> h;
- l--;
- root = sdv(root, l, r, h % abs(r - l));
- //output(root);
- //cout << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement