Advertisement
K_Y_M_bl_C

Untitled

Jan 20th, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.95 KB | None | 0 0
  1. #ifdef _DEBUG
  2. #define _GLIBCXX_DEBUG
  3. #endif
  4. #define _CRT_SECURE_NO_WARNINGS
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <bits/stdc++.h>
  7.  
  8. ///  НАБИРАЕМ БАЛЛЫ
  9. /// ░░░░░░▄▀▀▀▄░РАБОТЯГИ░░
  10. /// ▄███▀░◐░░░▌░░░░░░░
  11. /// ░░░░▌░░░░░▐░░░░░░░
  12. /// ░░░░▐░░░░░▐░░░░░░░
  13. /// ░░░░▌░░░░░▐▄▄░░░░░  
  14. /// ░░░░▌░░░░▄▀▒▒▀▀▀▀▄  
  15. /// ░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄  
  16. /// ░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
  17. /// ░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
  18. /// ░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
  19. /// ░░░░░░░░░░░▌▌░▌▌░░░░░  
  20. /// ░░░░░░░░░░░▌▌░▌▌░░░░░
  21. /// ░░░░░░░░░▄▄▌▌▄▌▌░░░░░
  22.  
  23. using namespace __gnu_pbds;
  24. using namespace std;
  25.      
  26. typedef long long ll;
  27. typedef vector<ll> vll;
  28. typedef pair<int, int> pii;
  29. typedef vector<int> vi;
  30. typedef long double ld;
  31. typedef tree<pair<ll, int>, null_type, less<pair<ll, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  32.      
  33. #define mk make_pair
  34. #define inb push_back
  35. #define enb emplace_back
  36. #define X first
  37. #define Y second
  38. #define all(v) v.begin(), v.end()
  39. #define sqr(x) (x) * (x)
  40. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  41. #define y1 AYDARBOG
  42. //continue break pop_back return
  43.      
  44. int solve();
  45.      
  46. int main()
  47. {
  48.     //ios_base::sync_with_stdio(0);
  49.     //cin.tie(0);  
  50. #define TASK "log"
  51. #ifndef _DEBUG
  52.     freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  53. #endif
  54.     solve();
  55. #ifdef _DEBUG
  56.     fprintf(stderr, "\nTIME: %.3f\n", TIME);
  57. #endif
  58. }
  59.  
  60. const int INF = 2e9 + 7;
  61.  
  62. const int BUFSZ = (int)1e6 + 7;
  63. char buf[BUFSZ];
  64. string get_str()
  65. {
  66.     scanf(" %s", buf);
  67.     return string(buf);
  68. }
  69.  
  70. mt19937 mrand(306);
  71.  
  72. struct Node
  73. {
  74.     int x, val, y, l, r, sz;
  75.     Node() : x(0), val(0), y(mrand()), l(0), r(0), sz(0) {};
  76.     Node(int x) : x(x), val(x), y(mrand()), l(0), r(0), sz(1) {};
  77. };
  78.  
  79. const int SZ = 10e6;
  80.  
  81. Node t[SZ];
  82.  
  83. void recalc(int v)
  84. {
  85.     if (!v)
  86.         return;
  87.     t[v].sz = t[t[v].l].sz + t[t[v].r].sz + 1;
  88.     t[v].val = (t[v].x | t[t[v].l].val | t[t[v].r].val);
  89. }
  90.  
  91. pii split(int v, int x)
  92. {
  93.     if (!v)
  94.         return mk(0, 0);
  95.     if (t[t[v].l].sz < x)
  96.     {
  97.         pii cur = split(t[v].r, x - t[t[v].l].sz - 1);
  98.         t[v].r = cur.X;
  99.         recalc(v);
  100.         return mk(v, cur.Y);
  101.     }
  102.     else
  103.     {
  104.         pii cur = split(t[v].l, x);
  105.         t[v].l = cur.Y;
  106.         recalc(v);
  107.         return mk(cur.X, v);
  108.     }
  109. }
  110.  
  111. int merge(int l, int r)
  112. {
  113.     if (l * r == 0)
  114.     {
  115.         if (l)
  116.             return l;
  117.         return r;
  118.     }
  119.     if (t[l].y > t[r].y)
  120.     {
  121.         t[l].r = merge(t[l].r, r);
  122.         recalc(l);
  123.         return l;
  124.     }
  125.     else
  126.     {
  127.         t[r].l = merge(l, t[r].l);
  128.         recalc(r);
  129.         return r;
  130.     }
  131. }
  132.  
  133. void print(int v)
  134. {
  135.     if (!v)
  136.         return;
  137.     recalc(v);
  138.     print(t[v].l);
  139.     printf("%d ", t[v].x);
  140.     print(t[v].r);
  141. }
  142.  
  143. int solve()
  144. {
  145.     int n;
  146.     scanf("%d", &n);
  147.     int fr = 1;
  148.     int root = 1;
  149.     while (n--)
  150.     {
  151.         char ct;
  152.         scanf(" %c", &ct);
  153.         if (ct == '+')
  154.         {
  155.             int pos, cnt;
  156.             char c;
  157.             scanf("%d %d %c", &pos, &cnt, &c);
  158.             --pos;
  159.             int x = (1 << (c - 'a'));
  160.             int croot = fr;
  161.             t[croot] = Node(x);
  162.             ++fr;
  163.             for (int i = 0; i < cnt - 1; ++i)
  164.             {
  165.                 t[fr] = Node(x);
  166.                 croot = merge(croot, fr);
  167.                 ++fr;
  168.             }
  169.             if (croot == root)
  170.             {
  171.                 root = croot;
  172.             }
  173.             else
  174.             {
  175.                 pii cur = split(root, pos);
  176.                 root = merge(cur.X, croot);
  177.                 root = merge(root, cur.Y);
  178.             }
  179.         }
  180.         if (ct == '-')
  181.         {
  182.             int pos, cnt;
  183.             scanf("%d %d", &pos, &cnt);
  184.             --pos;
  185.             pii cur = split(root, pos);
  186.             pii ccur = split(cur.Y, cnt);
  187.             root = merge(cur.X, ccur.Y);
  188.         }
  189.         if (ct == '?')
  190.         {
  191.             int l, r;
  192.             scanf("%d %d", &l, &r);
  193.             --l;
  194.             pii cur = split(root, l);
  195.             pii ccur = split(cur.Y, r - l);
  196.             recalc(ccur.X);
  197.             printf("%d\n", __builtin_popcount(t[ccur.X].val));
  198.             root = merge(cur.X, ccur.X);
  199.             root = merge(root, ccur.Y);
  200.         }
  201.     }
  202.     return 0;
  203. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement