Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- struct event
- {
- int type;
- ll l, r, k;
- string str;
- };
- const int M = 2e5 + 7;
- int go[M][26];
- typedef vector <short int> trans;
- typedef vector <ll> calc;
- typedef vector <bool> mask;
- mt19937_64 rnd(228);
- int m;
- struct treap
- {
- treap *l, *r;
- int symb;
- map <int, pair <int, ll> > ans;
- ll sz;
- treap(int c, treap *_l, treap *_r)
- {
- l = _l, r = _r;
- symb = c;
- ans.clear();
- sz = 1;
- }
- };
- void recalc(treap *t)
- {
- if (!t) return;
- if (t->l)
- {
- t->sz = t->l->sz + 1;
- }
- else
- {
- t->sz = 1;
- }
- if (t->r)
- {
- t->sz += t->r->sz;
- }
- t->ans.clear();
- }
- treap *merge(treap *a, treap *b)
- {
- if (!a) return b;
- if (!b) return a;
- if (rnd() % (a->sz + b->sz) < a->sz)
- {
- treap *go = new treap(a->symb, a->l, merge(a->r, b));
- recalc(go);
- return go;
- }
- else
- {
- treap *go = new treap(b->symb, merge(a, b->l), b->r);
- recalc(go);
- return go;
- }
- }
- ll sz(treap *t)
- {
- if (!t) return 0;
- else return t->sz;
- }
- pair <treap*, treap*> split(treap *t, ll k)
- {
- if (!t)
- {
- return {0, 0};
- }
- if (sz(t->l) >= k)
- {
- auto a = split(t->l, k);
- treap *go = new treap(t->symb, a.second, t->r);
- recalc(go);
- return {a.first, go};
- }
- else
- {
- auto a = split(t->r, k - 1 - sz(t->l));
- treap *go = new treap(t->symb, t->l, a.first);
- recalc(go);
- return {go, a.second};
- }
- }
- treap *pow(treap *t, ll k)
- {
- treap *cur = 0;
- while (k)
- {
- if (k % 2 == 0)
- {
- t = merge(t, t);
- k /= 2;
- }
- else
- {
- cur = merge(cur, t);
- k--;
- }
- }
- return cur;
- }
- treap *get_seg(treap *t, ll l, ll r)
- {
- auto a = split(t, r + 1);
- auto b = split(a.first, l);
- return b.second;
- }
- treap *build( string &s, int l, int r)
- {
- if (l >= r) return 0;
- if (r - l == 1)
- {
- return new treap(s[l], 0, 0);
- }
- else
- {
- int m = (l + r) / 2;
- treap *a = build(s, l, m);
- treap *b = build(s, m + 1, r);
- treap *ans = new treap(s[m], a, b);
- recalc(ans);
- return ans;
- }
- }
- pair <int, ll> ans(treap *t, int who)
- {
- if (t->ans.count(who)) return t->ans[who];
- pair <int, ll> me = make_pair(who, 0);
- if (t->l)
- {
- me = ans(t->l, who);
- }
- me.first = go[me.first][t->symb];
- if (me.first == m) me.second++;
- if (t->r)
- {
- auto go = ans(t->r, me.first);
- me.first = go.first;
- me.second += go.second;
- }
- return t->ans[who] = me;
- }
- int main() {
- // freopen("a.in", "r", stdin);
- ios::sync_with_stdio(0);
- cin.tie(0);
- int n;
- cin >> m >> n;
- string s;
- cin >> s;
- vector <int> p(m);
- int j = 0;
- for (int i = 1; i < m; i++)
- {
- while (j > 0 && s[i] != s[j])
- {
- j = p[j - 1];
- }
- j += (s[i] == s[j]);
- p[i] = j;
- }
- for (int i = 0; i <= m; i++)
- {
- for (int j = 0; j < 26; j++)
- {
- if (i != m && j == s[i] - 'a')
- {
- go[i][j] = i + 1;
- }
- else
- {
- if (i)
- go[i][j] = go[p[i - 1]][j];
- else
- go[i][j] = 0;
- }
- }
- }
- vector <event> e;
- ll cur_len = 0;
- for (int i = 0; i < n; i++)
- {
- int t;
- cin >> t;
- if (t == 1)
- {
- string w;
- cin >> w;
- for (auto &c : w) c -= 'a';
- e.push_back({1, -1, -1, 1, w});
- cur_len += (int) w.size();
- }
- else
- {
- ll pos, len;
- cin >> pos >> len;
- pos--;
- ll lim = cur_len - 1;
- ll suf_len = lim - pos + 1;
- if (len >= suf_len)
- e.push_back({2, pos, lim, len / suf_len, ""});
- if (len % suf_len)
- {
- e.push_back({2, pos, pos + len % suf_len - 1, 1, ""});
- }
- cur_len += len;
- }
- }
- treap *t = 0;
- for (auto c : e)
- {
- if (c.type == 1)
- {
- t = merge(t, build(c.str, 0, (int) c.str.size()));
- }
- else
- {
- t = merge(t, pow(get_seg(t, c.l, c.r), c.k));
- }
- }
- cout << ans(t, 0).second << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement