SHARE
TWEET

Untitled

a guest Apr 21st, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <ctime>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9. const ll MOD = 1e9;
  10.  
  11. struct node {
  12.     ll x, y;
  13.     node *l, *r;
  14.     ll cnt;
  15.     char letter;
  16.     ll ans;
  17.     explicit node(ll cnt, char letter): x(cnt), letter(letter), y(rand()), cnt(cnt), ans(1 << (letter - 'a')), l(nullptr), r(nullptr) {};
  18. };
  19.  
  20. void upd(node *&t) {
  21.     if (!t) {
  22.         return;
  23.     }
  24.     t->cnt = t->x;
  25.     t->ans = 1 << (t->letter - 'a');
  26.     if (t->l) {
  27.         t->ans |= t->l->ans;
  28.         t->cnt += t->l->cnt;
  29.     }
  30.     if (t->r) {
  31.         t->ans |= t->r->ans;
  32.         t->cnt += t->r->cnt;
  33.     }
  34. }
  35.  
  36. ll get_cnt(node *t) {
  37.     if (!t) {
  38.         return 0;
  39.     }
  40.     return t->cnt;
  41. }
  42.  
  43. ll get_ans(node *t) {
  44.     if (!t) {
  45.         return 0;
  46.     }
  47.     return t->ans;
  48. }
  49.  
  50. node* merge(node *l, node *r) {
  51.     if (!l) {
  52.         return r;
  53.     }
  54.     if (!r) {
  55.         return l;
  56.     }
  57.     if (l->y >= r->y) {
  58.         l->r = merge(l->r, r);
  59.         upd(l);
  60.         return l;
  61.     } else {
  62.         r->l = merge(l, r->l);
  63.         upd(r);
  64.         return r;
  65.     }
  66. }
  67.  
  68. void split(node* t, ll k, node *&l, node *&r) {
  69.     if (!t) {
  70.         l = r = nullptr;
  71.         return;
  72.     }
  73.  
  74.     ll cnt = get_cnt(t->l);
  75.  
  76.     if (cnt > k) {
  77.         split(t->l, k, l, t->l);
  78.         r = t;
  79.     } else {
  80.         if (cnt + t->x > k) {
  81.             l = merge(t->l, new node(k - cnt, t->letter));
  82.             r = merge(new node(t->x - (k - cnt), t->letter), t->r);
  83.             upd(l);
  84.             upd(r);
  85.             return;
  86.         } else {
  87.             split(t->r, k - cnt - 1, t->r, r);
  88.             l = t;
  89.         }
  90.     }
  91.     upd(t);
  92. }
  93.  
  94. void print(node *t) {
  95.     if (t->l) {
  96.         print(t->l);
  97.     }
  98.     for (int i = 0; i < t->x; i++) {
  99.         cout << t->letter << " ";
  100.     }
  101.     if (t->r) {
  102.         print(t->r);
  103.     }
  104. }
  105.  
  106. void insert(node *&t, int k, int cnt, char letter) {
  107.     node *l, *r;
  108.     split(t, k - 1, l, r);
  109.     t = merge(l, merge(new node(cnt, letter), r));
  110. }
  111.  
  112.  
  113. void remove(node *&t, int k, int cnt) {
  114.     node *l1, *r1;
  115.     node *l2, *r2;
  116.     int l = k;
  117.     int r = k + cnt - 1;
  118.     split(t, r, l1, r1);
  119.     split(l1, l - 1, l2, r2);
  120.     t = merge(l2, r1);
  121. }
  122.  
  123. ll query(node *&t, int l, int r) {
  124.     node *l1, *r1;
  125.     node *l2, *r2;
  126.  
  127.     split(t, r, l1, r1);
  128.     split(l1, l - 1, l2, r2);
  129.     ll ans = get_ans(r2);
  130.     t = merge(merge(l2, r2), r1);
  131.     int cnt = 0;
  132.     for (int i = 0; i < 27; i++) {
  133.         if (ans & (1 << i)) {
  134.             cnt++;
  135.         }
  136.     }
  137.     return cnt;
  138. }
  139. int main() {
  140.     freopen("input.txt", "r", stdin);
  141.     freopen("output.txt", "w", stdout);
  142.  
  143.     int n;
  144.     cin >> n;
  145.     srand(time(NULL));
  146.  
  147.     node *root = nullptr;
  148.     for (int i = 0; i < n; i++) {
  149.         char ch;
  150.         cin >> ch;
  151.         if (ch == '+') {
  152.             int ind, cnt;
  153.             char letter;
  154.             cin >> ind >> cnt >> letter;
  155.             insert(root, ind, cnt, letter);
  156.         }
  157.         if (ch == '-') {
  158.             int ind, cnt;
  159.             cin >> ind >> cnt;
  160.             remove(root, ind, cnt);
  161.         }
  162.             print(root);
  163.         cout << endl;
  164.         if (ch == '?') {
  165.             int ind1, ind2;
  166.             cin >> ind1 >> ind2;
  167.             cout << query(root, ind1, ind2) << endl;
  168.         }
  169.     }
  170.  
  171.     return 0;
  172. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top