Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef _DEBUG
- #define _GLIBCXX_DEBUG
- #endif
- #define _CRT_SECURE_NO_WARNINGS
- #include <ext/pb_ds/assoc_container.hpp>
- #include <bits/stdc++.h>
- /// НАБИРАЕМ БАЛЛЫ
- /// ░░░░░░▄▀▀▀▄░РАБОТЯГИ░░
- /// ▄███▀░◐░░░▌░░░░░░░
- /// ░░░░▌░░░░░▐░░░░░░░
- /// ░░░░▐░░░░░▐░░░░░░░
- /// ░░░░▌░░░░░▐▄▄░░░░░
- /// ░░░░▌░░░░▄▀▒▒▀▀▀▀▄
- /// ░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
- /// ░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
- /// ░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
- /// ░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
- /// ░░░░░░░░░░░▌▌░▌▌░░░░░
- /// ░░░░░░░░░░░▌▌░▌▌░░░░░
- /// ░░░░░░░░░▄▄▌▌▄▌▌░░░░░
- using namespace __gnu_pbds;
- using namespace std;
- typedef long long ll;
- typedef vector<ll> vll;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- typedef long double ld;
- typedef tree<pair<ll, int>, null_type, less<pair<ll, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
- #define mk make_pair
- #define inb push_back
- #define enb emplace_back
- #define X first
- #define Y second
- #define all(v) v.begin(), v.end()
- #define sqr(x) (x) * (x)
- #define TIME 1.0 * clock() / CLOCKS_PER_SEC
- #define y1 AYDARBOG
- //continue break pop_back return
- int solve();
- int main()
- {
- //ios_base::sync_with_stdio(0);
- //cin.tie(0);
- #define TASK "log"
- #ifndef _DEBUG
- freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
- #endif
- solve();
- #ifdef _DEBUG
- fprintf(stderr, "\nTIME: %.3f\n", TIME);
- #endif
- }
- const int INF = 2e9 + 7;
- const int BUFSZ = (int)1e6 + 7;
- char buf[BUFSZ];
- string get_str()
- {
- scanf(" %s", buf);
- return string(buf);
- }
- 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