Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- mt19937 mrand(306);
- struct Node
- {
- int x, val, y, l, r, sz;
- Node() : x(0), val(0), y(mrand()), l(0), r(0), sz(0) {};
- Node(int x) : x(x), val(x), y(mrand()), l(0), r(0), sz(1) {};
- };
- const int SZ = 10e6;
- Node t[SZ];
- void recalc(int v)
- {
- if (!v)
- return;
- t[v].sz = t[t[v].l].sz + t[t[v].r].sz + 1;
- t[v].val = (t[v].x | t[t[v].l].val | t[t[v].r].val);
- }
- pii split(int v, int x)
- {
- if (!v)
- return mk(0, 0);
- if (t[t[v].l].sz < x)
- {
- pii cur = split(t[v].r, x - t[t[v].l].sz - 1);
- t[v].r = cur.X;
- recalc(v);
- return mk(v, cur.Y);
- }
- else
- {
- pii cur = split(t[v].l, x);
- t[v].l = cur.Y;
- recalc(v);
- return mk(cur.X, v);
- }
- }
- int merge(int l, int r)
- {
- if (l * r == 0)
- {
- if (l)
- return l;
- return r;
- }
- if (t[l].y > t[r].y)
- {
- t[l].r = merge(t[l].r, r);
- recalc(l);
- return l;
- }
- else
- {
- t[r].l = merge(l, t[r].l);
- recalc(r);
- return r;
- }
- }
- void print(int v)
- {
- if (!v)
- return;
- recalc(v);
- print(t[v].l);
- printf("%d ", t[v].x);
- print(t[v].r);
- }
- int solve()
- {
- int n;
- scanf("%d", &n);
- int fr = 1;
- int root = 1;
- while (n--)
- {
- char ct;
- scanf(" %c", &ct);
- if (ct == '+')
- {
- int pos, cnt;
- char c;
- scanf("%d %d %c", &pos, &cnt, &c);
- --pos;
- int x = (1 << (c - 'a'));
- int croot = fr;
- t[croot] = Node(x);
- ++fr;
- for (int i = 0; i < cnt - 1; ++i)
- {
- t[fr] = Node(x);
- croot = merge(croot, fr);
- ++fr;
- }
- if (croot == root)
- {
- root = croot;
- }
- else
- {
- pii cur = split(root, pos);
- root = merge(cur.X, croot);
- root = merge(root, cur.Y);
- }
- }
- if (ct == '-')
- {
- int pos, cnt;
- scanf("%d %d", &pos, &cnt);
- --pos;
- pii cur = split(root, pos);
- pii ccur = split(cur.Y, cnt);
- root = merge(cur.X, ccur.Y);
- }
- if (ct == '?')
- {
- int l, r;
- scanf("%d %d", &l, &r);
- --l;
- pii cur = split(root, l);
- pii ccur = split(cur.Y, r - l);
- recalc(ccur.X);
- printf("%d\n", __builtin_popcount(t[ccur.X].val));
- root = merge(cur.X, ccur.X);
- root = merge(root, ccur.Y);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement