SHARE
TWEET

Untitled

a guest Nov 19th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. struct event
  8. {
  9.     int type;
  10.     ll l, r, k;
  11.     string str;
  12. };
  13.  
  14. const int M = 2e5 + 7;
  15.  
  16. int go[M][26];
  17.  
  18. typedef vector <short int> trans;
  19. typedef vector <ll> calc;
  20. typedef vector <bool> mask;
  21.  
  22. mt19937_64 rnd(228);
  23.  
  24. int m;
  25.  
  26. struct treap
  27. {
  28.     treap *l, *r;
  29.     int symb;
  30.     map <int, pair <int, ll> > ans;
  31.     ll sz;
  32.     treap(int c, treap *_l, treap *_r)
  33.     {
  34.         l = _l, r = _r;
  35.         symb = c;
  36.         ans.clear();
  37.         sz = 1;
  38.     }
  39. };
  40.  
  41. void recalc(treap *t)
  42. {
  43.     if (!t) return;
  44.     if (t->l)
  45.     {
  46.         t->sz = t->l->sz + 1;
  47.     }
  48.     else
  49.     {
  50.         t->sz = 1;
  51.     }
  52.     if (t->r)
  53.     {
  54.         t->sz += t->r->sz;
  55.     }
  56.     t->ans.clear();
  57. }
  58.  
  59. treap *merge(treap *a, treap *b)
  60. {
  61.     if (!a) return b;
  62.     if (!b) return a;
  63.     if (rnd() % (a->sz + b->sz) < a->sz)
  64.     {
  65.         treap *go = new treap(a->symb, a->l, merge(a->r, b));
  66.         recalc(go);
  67.         return go;
  68.     }
  69.     else
  70.     {
  71.         treap *go = new treap(b->symb, merge(a, b->l), b->r);
  72.         recalc(go);
  73.         return go;
  74.     }
  75. }
  76.  
  77. ll sz(treap *t)
  78. {
  79.     if (!t) return 0;
  80.     else return t->sz;
  81. }
  82.  
  83. pair <treap*, treap*> split(treap *t, ll k)
  84. {
  85.     if (!t)
  86.     {
  87.         return {0, 0};
  88.     }
  89.     if (sz(t->l) >= k)
  90.     {
  91.         auto a = split(t->l, k);
  92.         treap *go = new treap(t->symb, a.second, t->r);
  93.         recalc(go);
  94.         return {a.first, go};
  95.     }
  96.     else
  97.     {
  98.         auto a = split(t->r, k - 1 - sz(t->l));
  99.         treap *go = new treap(t->symb, t->l, a.first);
  100.         recalc(go);
  101.         return {go, a.second};
  102.     }
  103. }
  104.  
  105. treap *pow(treap *t, ll k)
  106. {
  107.     treap *cur = 0;
  108.     while (k)
  109.     {
  110.         if (k % 2 == 0)
  111.         {
  112.             t = merge(t, t);
  113.             k /= 2;
  114.         }
  115.         else
  116.         {
  117.  
  118.             cur = merge(cur, t);
  119.             k--;
  120.         }
  121.     }
  122.     return cur;
  123. }
  124.  
  125. treap *get_seg(treap *t, ll l, ll r)
  126. {
  127.     auto a = split(t, r + 1);
  128.     auto b = split(a.first, l);
  129.     return b.second;
  130. }
  131.  
  132. treap *build( string &s, int l, int r)
  133. {
  134.     if (l >= r) return 0;
  135.     if (r - l == 1)
  136.     {
  137.         return new treap(s[l], 0, 0);
  138.     }
  139.     else
  140.     {
  141.         int m = (l + r) / 2;
  142.         treap *a = build(s, l, m);
  143.         treap *b = build(s, m + 1, r);
  144.         treap *ans = new treap(s[m], a, b);
  145.         recalc(ans);
  146.         return ans;
  147.     }
  148. }
  149.  
  150. pair <int, ll> ans(treap *t, int who)
  151. {
  152.     if (t->ans.count(who)) return t->ans[who];
  153.     pair <int, ll> me = make_pair(who, 0);
  154.     if (t->l)
  155.     {
  156.         me = ans(t->l, who);
  157.     }
  158.     me.first = go[me.first][t->symb];
  159.     if (me.first == m) me.second++;
  160.     if (t->r)
  161.     {
  162.         auto go = ans(t->r, me.first);
  163.         me.first = go.first;
  164.         me.second += go.second;
  165.     }
  166.     return t->ans[who] = me;
  167. }
  168.  
  169. int main() {
  170.  // freopen("a.in", "r", stdin);
  171.    ios::sync_with_stdio(0);
  172.    cin.tie(0);
  173.   int n;
  174.   cin >> m >> n;
  175.   string s;
  176.   cin >> s;
  177.   vector <int> p(m);
  178.   int j = 0;
  179.   for (int i = 1; i < m; i++)
  180.   {
  181.       while (j > 0 && s[i] != s[j])
  182.       {
  183.           j = p[j - 1];
  184.       }
  185.       j += (s[i] == s[j]);
  186.       p[i] = j;
  187.   }
  188.   for (int i = 0; i <= m; i++)
  189.   {
  190.       for (int j = 0; j < 26; j++)
  191.       {
  192.           if (i != m && j == s[i] - 'a')
  193.           {
  194.               go[i][j] = i + 1;
  195.           }
  196.           else
  197.           {
  198.               if (i)
  199.                   go[i][j] = go[p[i - 1]][j];
  200.               else
  201.                   go[i][j] = 0;
  202.           }
  203.       }
  204.   }
  205.   vector <event> e;
  206.   ll cur_len = 0;
  207.   for (int i = 0; i < n; i++)
  208.   {
  209.       int t;
  210.       cin >> t;
  211.       if (t == 1)
  212.       {
  213.           string w;
  214.           cin >> w;
  215.           for (auto &c : w) c -= 'a';
  216.           e.push_back({1, -1, -1, 1, w});
  217.           cur_len += (int) w.size();
  218.       }
  219.       else
  220.       {
  221.           ll pos, len;
  222.           cin >> pos >> len;
  223.           pos--;
  224.           ll lim = cur_len - 1;
  225.           ll suf_len = lim - pos + 1;
  226.           if (len >= suf_len)
  227.             e.push_back({2, pos, lim, len / suf_len, ""});
  228.           if (len % suf_len)
  229.           {
  230.               e.push_back({2, pos, pos + len % suf_len - 1, 1, ""});
  231.           }
  232.           cur_len += len;
  233.       }
  234.   }
  235.   treap *t = 0;
  236.   for (auto c : e)
  237.   {
  238.       if (c.type == 1)
  239.       {
  240.           t = merge(t, build(c.str, 0, (int) c.str.size()));
  241.       }
  242.       else
  243.       {
  244.           t = merge(t, pow(get_seg(t, c.l, c.r), c.k));
  245.       }
  246.   }
  247.   cout << ans(t, 0).second << '\n';
  248. }
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