fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. const int MAXN = 300005;
  6. struct TrieInfo
  7. {
  8.     int To[26], Fa[4][32], ref, l;
  9. };
  10. struct Match
  11. {
  12.     int l, r, len;
  13.     Match(void) {}
  14.     Match(int a, int b, int c) : l(a), r(b), len(c) {}
  15. } Info[MAXN], Map[26];
  16.  
  17. int Sa[MAXN], Rank[MAXN], Ti[MAXN], Cnt;
  18. int Final[MAXN], Next[MAXN], total, Ans[MAXN];
  19.  
  20. namespace Trie
  21. {
  22.     const int MAXN = 100005;
  23.     TrieInfo T[MAXN];
  24.     int Trans[MAXN], A[MAXN], cnt;
  25.     void First()
  26.     {
  27.         cnt = 1;
  28.         Trans[1] = -1;
  29.     }
  30.     int Insert(int cur, char c)
  31.     {
  32.         c = c - 'a';
  33.         if (T[cur].To[c])
  34.             return T[cur].To[c];
  35.         T[++cnt].Fa[0][1] = cur;
  36.         T[cnt].l = T[cur].l + 1;
  37.         Trans[cnt] = c;
  38.         return (T[cur].To[c] = cnt);
  39.     }
  40.     int Getfa(int u, int dep)
  41.     {
  42.         int cur = u;
  43.         for (int i = 0; i < 4; i++, dep >>= 5)
  44.         {
  45.             int p = (dep & 31);
  46.             if (!p)
  47.             {
  48.                 continue;
  49.             }
  50.             cur = T[cur].Fa[i][p];
  51.         }
  52.         return cur;
  53.     }
  54.  
  55.     void Work()
  56.     {
  57.         for (int i = 2; i < 32; i++)
  58.             for (int j = 1; j <= cnt; j++)
  59.                 T[j].Fa[0][i] = T[T[j].Fa[0][i - 1]].Fa[0][1];
  60.         for (int i = 1; i < 4; i++)
  61.             for (int j = 1; j < 32; j++)
  62.                 for (int k = 1; k <= cnt; k++)
  63.                 {
  64.                     if (j == 1)
  65.                         T[k].Fa[i][j] = T[T[k].Fa[i - 1][31]].Fa[i - 1][1];
  66.                     else
  67.                         T[k].Fa[i][j] = T[T[k].Fa[i][j - 1]].Fa[i][1];
  68.                 }
  69.     }
  70.  
  71.     void Add(int p, int v)
  72.     {
  73.         for (; p <= Cnt; p += p & -p)
  74.         {
  75.             A[p] += v;
  76.         }
  77.     }
  78.  
  79.     int Sum(int p)
  80.     {
  81.         if (p < 0)
  82.             return 0;
  83.         int tmp = 0;
  84.         for (; p; p -= p & -p)
  85.             tmp += A[p];
  86.         return tmp;
  87.     }
  88.     int Sum(int l, int r)
  89.     {
  90.         if (l > r)
  91.             return 0;
  92.         return Sum(r) - Sum(l - 1);
  93.     }
  94.     void Dfs(int Now)
  95.     {
  96.         Add(Rank[Now], 1);
  97.         for (int j = Final[Now]; j; j = Next[j])
  98.         {
  99.             Ans[j] = Sum(Info[Ti[j]].l, Info[Ti[j]].r);
  100.             if (!Info[Ti[j]].len)
  101.                 Ans[j] = 0;
  102.         }
  103.         for (int i = 0; i < 26; i++)
  104.             if (T[Now].To[i])
  105.                 Dfs(T[Now].To[i]);
  106.         Add(Rank[Now], -1);
  107.     }
  108.     void GetAns()
  109.     {
  110.         Dfs(1);
  111.     }
  112. }
  113.  
  114. namespace SAM
  115. {
  116.     struct Node
  117.     {
  118.         int To[26], fail, len, down, ref;
  119.     } T[MAXN];
  120.     int Go[MAXN][26];
  121.     int Q[MAXN], Ord[MAXN], S, cnt;
  122.     bool cmp(int a, int b)
  123.     {
  124.         return T[a].len < T[b].len;
  125.     }
  126.     int Add(int Lst, int c, int l, int cur)
  127.     {
  128.         int Nt = ++cnt, p = Lst;
  129.         T[Nt].len = l;
  130.         for (; p && !T[p].To[c]; p = T[p].fail)
  131.             T[p].To[c] = Nt;
  132.         if (!p)
  133.             T[Nt].fail = S;
  134.         else if (T[T[p].To[c]].len == T[p].len + 1)
  135.             T[Nt].fail = T[p].To[c];
  136.         else
  137.         {
  138.             int q = ++cnt, qt = T[p].To[c];
  139.             T[q] = T[qt];
  140.             T[qt].fail = T[Nt].fail = q;
  141.             for (; p && T[p].To[c] == qt; p = T[p].fail)
  142.                 T[p].To[c] = q;
  143.         }
  144.         return Nt;
  145.     }
  146.  
  147.     void Dfs(int Now)
  148.     {
  149.         if (T[Now].ref)
  150.             Sa[++Cnt] = T[Now].ref, Rank[T[Now].ref] = Cnt;
  151.         for (int i = 0; i < 26; i++)
  152.             if (Go[Now][i])
  153.                 Dfs(Go[Now][i]);
  154.     }
  155.  
  156.     void Mark(int tnod, int snod)
  157.     {
  158.         T[snod].down = T[snod].ref = tnod;
  159.         for (int i = 0; i < 26; i++)
  160.             if (Trie::T[tnod].To[i])
  161.                 Mark(Trie::T[tnod].To[i], T[snod].To[i]);
  162.     }
  163.  
  164.     void Build()
  165.     {
  166.         int fi = 0, en = 1;
  167.         Q[1] = 1;
  168.         S = cnt = 1;
  169.         Trie::T[1].ref = 1;
  170.         T[1].ref = 1;
  171.         while (fi < en)
  172.         {
  173.             int u = Q[++fi];
  174.             TrieInfo &c = Trie::T[u];
  175.             for (int i = 0; i < 26; i++)
  176.                 if (c.To[i])
  177.                 {
  178.                     TrieInfo &cur = Trie::T[c.To[i]];
  179.                     Trie::T[c.To[i]];
  180.                     cur.ref = Add(c.ref, i, cur.l, c.To[i]);
  181.                     Q[++en] = c.To[i];
  182.                 }
  183.         }
  184.         Mark(1, 1);
  185.         for (int i = 1; i <= cnt; i++)
  186.             Ord[i] = i;
  187.         sort(Ord + 1, Ord + cnt + 1, cmp);
  188.         for (; cnt > 1; cnt--)
  189.         {
  190.             int v = Ord[cnt], u = T[v].fail;
  191.             T[u].down = T[v].down;
  192.             TrieInfo &cur = Trie::T[T[v].down];
  193.             int k = Trie::Getfa(T[u].down, cur.l - (T[cur.ref].len - T[u].len));
  194.             Go[u][Trie::Trans[k]] = v;
  195.         }
  196.         Dfs(1);
  197.     }
  198. }
  199.  
  200. struct Quer
  201. {
  202.     int type, s, t;
  203.     char c;
  204. } Q[MAXN];
  205.  
  206. int Refer[MAXN], Len[MAXN], N, M, Tc;
  207. inline bool Small(int suf, const Match &a)
  208. {
  209.     return Rank[suf] < a.l;
  210. }
  211. inline bool Large(int suf, const Match &a)
  212. {
  213.     return Rank[suf] > a.r;
  214. }
  215. Match Merge(const Match &a, const Match &b)
  216. {
  217.     if (a.l > a.r)
  218.         return Match(0, -1, a.len + b.len);
  219.     int l = a.l, r = a.r, l1 = a.l - 1, r1 = a.r + 1, mid;
  220.     for (; l <= r;)
  221.     {
  222.         mid = (l + r) >> 1;
  223.         if (Small(Trie::Getfa(Sa[mid], a.len), b))
  224.             l1 = mid, l = mid + 1;
  225.         else
  226.             r = mid - 1;
  227.     }
  228.  
  229.     for (l = a.l, r = a.r; l <= r;)
  230.     {
  231.         mid = (l + r) >> 1;
  232.         if (Large(Trie::Getfa(Sa[mid], a.len), b))
  233.             r1 = mid, r = mid - 1;
  234.         else
  235.             l = mid + 1;
  236.     }
  237.     return Match(l1 + 1, r1 - 1, a.len + b.len);
  238. }
  239. int main()
  240. {
  241.     Trie::First();
  242.     N = 1;
  243.     Refer[1] = 1;
  244.     scanf("%d", &M);
  245.     for (int i = 1; i <= M; i++)
  246.     {
  247.         int type, s, t;
  248.         char c;
  249.         scanf("%d %d", &type, &s);
  250.         if (type == 1)
  251.         {
  252.             scanf("%c", &c);
  253.             s = Refer[s];
  254.             Refer[++N] = Trie::Insert(s, c);
  255.         }
  256.         if (type == 2)
  257.         {
  258.             scanf("%d %c", &t, &c);
  259.             Q[i].type = s + 1;
  260.             Q[i].s = t;
  261.             Q[i].c = c;
  262.         }
  263.         if (type == 3 || type == 4)
  264.         {
  265.             scanf("%d", &t), Q[i].type = type, Q[i].s = s, Q[i].t = t;
  266.         }
  267.     }
  268.     Trie::Work();
  269.     SAM::Build();
  270.     Tc = 1;
  271.     Info[1].l = 1, Info[1].r = Cnt;
  272.     for (int i = 0; i < 26; i++)
  273.     {
  274.         int l = 1, r = Cnt, mid;
  275.         Map[i].r = Cnt + 1;
  276.         for (; l <= r;)
  277.         {
  278.             mid = (l + r) >> 1;
  279.             if (Trie::Trans[Sa[mid]] < i)
  280.                 Map[i].l = mid, l = mid + 1;
  281.             else
  282.                 r = mid - 1;
  283.         }
  284.         for (l = 1, r = Cnt; l <= r;)
  285.         {
  286.             mid = (l + r) >> 1;
  287.             if (Trie::Trans[Sa[mid]] > i)
  288.                 Map[i].r = mid, r = mid - 1;
  289.             else
  290.                 l = mid + 1;
  291.         }
  292.         Map[i].l++, Map[i].r--;
  293.         Map[i].len = 1;
  294.     }
  295.     for (int i = 1; i <= M; i++)
  296.     {
  297.         Quer &c = Q[i];
  298.         if (!c.type)
  299.             continue;
  300.         if (c.type != 4)
  301.             ++Tc;
  302.         if (c.type == 4)
  303.         {
  304.             ++total;
  305.             c.t = Refer[c.t];
  306.             Next[total] = Final[c.t], Final[c.t] = total;
  307.             Ti[total] = c.s;
  308.         }
  309.         else
  310.         {
  311.             if (c.type == 1)
  312.                 Info[Tc] = Merge(Info[c.s], Map[c.c - 'a']);
  313.             if (c.type == 2)
  314.                 Info[Tc] = Merge(Map[c.c - 'a'], Info[c.s]);
  315.             if (c.type == 3)
  316.                 Info[Tc] = Merge(Info[c.t], Info[c.s]);
  317.         }
  318.     }
  319.  
  320.     Trie::GetAns();
  321.     for (int i = 1; i <= total; i++)
  322.         printf("%d\n", Ans[i]);
  323.     return 0;
  324. }
  325.  
Success #stdin #stdout 0.01s 11736KB
comments (?)
stdin
copy 
18
1 1 a
1 2 a
1 3 b
1 2 b
1 5 a
1 5 b
2 1 1 a
3 2 2
2 0 3 b
2 1 2 b
3 2 5
3 5 2
4 7 6
4 5 6
4 3 4
4 2 4
4 2 7
4 2 6
stdout
copy 
Standard output is empty
https://ideone.com/HnkEtq
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!