fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. typedef tree<
  8. int,
  9. null_type,
  10. less<int>,
  11. rb_tree_tag,
  12. tree_order_statistics_node_update> ordered_set;
  13.  
  14. const int maxn = 2e5 + 42;
  15.  
  16. int len[maxn], link[maxn];
  17. int state[maxn];
  18. map<char, int> to[maxn];
  19. int last, sz;
  20.  
  21. void add_letter(char c)
  22. {
  23.     int p = last;
  24.     last = sz++;
  25.     len[last] = len[p] + 1;
  26.     state[len[last]] = last;
  27.     for(; to[p][c] == 0; p = link[p])
  28.         to[p][c] = last;
  29.     if(to[p][c] == last)
  30.         return;
  31.     int q = to[p][c];
  32.     if(len[q] == len[p] + 1)
  33.     {
  34.         link[last] = q;
  35.         return;
  36.     }
  37.     int cl = sz++;
  38.     to[cl] = to[q];
  39.     link[cl] = link[q];
  40.     len[cl] = len[p] + 1;
  41.     link[last] = link[q] = cl;
  42.     for(; to[p][c] == q; p = link[p])
  43.         to[p][c] = cl;
  44. }
  45.  
  46. const int logn = 18;
  47. vector<int> g[maxn];
  48. int in[maxn], out[maxn];
  49. int up[maxn][logn];
  50. int t;
  51.  
  52. void dfs(int v = 0)
  53. {
  54.     in[v] = ++t;
  55.     for(auto u: g[v])
  56.     {
  57.         up[u][0] = v;
  58.         for(int i = 1; i < logn; i++)
  59.             up[u][i] = up[up[u][i - 1]][i - 1];
  60.         dfs(u);
  61.     }
  62.     out[v] = t + 1;
  63. }
  64.  
  65. multiset<int> lens[4 * maxn];
  66.  
  67. void add(int t, int p, int c, int v = 1, int l = 0, int r = maxn)
  68. {
  69.     if(t == 1)
  70.         lens[v].insert(c);
  71.     if(t == -1)
  72.         lens[v].erase(lens[v].find(c));
  73.     if(r - l == 1)
  74.         return;
  75.     int m = (l + r) / 2;
  76.     if(p < m)
  77.         add(t, p, c, 2 * v, l, m);
  78.     else
  79.         add(t, p, c, 2 * v + 1, m, r);
  80. }
  81.  
  82. vector<int> ans;
  83.  
  84. void get(int a, int b, int k, int v = 1, int l = 0, int r = maxn)
  85. {
  86.     if(a <= l && r <= b)
  87.     {
  88.         auto it = lens[v].begin();
  89.         for(int i = 0; i <= k && it != lens[v].end(); i++, it++)
  90.             ans.push_back(*it);
  91.         return;
  92.     }
  93.     if(r <= a || b <= l)
  94.         return;
  95.     int m = (l + r) / 2;
  96.     get(a, b, k, 2 * v, l, m);
  97.     get(a, b, k, 2 * v + 1, m, r);
  98. }
  99.  
  100. int get(int ln, int pos)
  101. {
  102.     int v = state[pos];
  103.     for(int i = logn - 1; i >= 0; i--)
  104.         if(len[link[up[v][i]]] >= ln)
  105.             v = up[v][i];
  106.     if(len[link[v]] >= ln)
  107.         v = up[v][0];
  108.     return v;
  109. }
  110.  
  111. ordered_set lns[maxn];
  112.  
  113. void init()
  114. {
  115.     for(int i = 0; i < sz; i++)
  116.     {
  117.         memset(up[i], 0, sizeof(up[i]));
  118.         to[i].clear();
  119.         g[i].clear();
  120.         in[i] = out[i] = 0;
  121.         len[i] = link[i] = 0;
  122.         state[i] = 0;
  123.         lns[i].clear();
  124.     }
  125.     sz = 1;
  126.     last = 0;
  127.     t = 0;
  128. }
  129.  
  130. signed main(int argc, char** argv)
  131. {
  132.     ios::sync_with_stdio(0);
  133.     cin.tie(0);
  134.     int t = 1;
  135.     while(t--)
  136.     {
  137.         init();
  138.         string s;
  139.         cin >> s;
  140.         for(auto c: s)
  141.             add_letter(c);
  142.         for(int i = 1; i < sz; i++)
  143.             g[link[i]].push_back(i);
  144.         dfs();
  145.         int q;
  146.         cin >> q;
  147.         while(q--)
  148.         {
  149.             int t, x, p;
  150.             cin >> t >> x >> p;
  151.             p++;
  152.             int v = get(x, p);
  153.             if(t == 1)
  154.             {
  155.                 if(lns[v].find(x) != lns[v].end())
  156.                     continue;
  157.                 add(1, in[v], x);
  158.                 lns[v].insert(x);
  159.             }
  160.             if(t == 2)
  161.             {
  162.                 if(lns[v].find(x) == lns[v].end())
  163.                     continue;
  164.                 add(-1, in[v], x);
  165.                 lns[v].erase(x);
  166.             }
  167.             if(t == 3)
  168.             {
  169.                 int k;
  170.                 cin >> k;
  171.                 if(lns[v].size() - lns[v].order_of_key(x) >= k)
  172.                 {
  173.                     cout << *lns[v].find_by_order(lns[v].order_of_key(x) + k - 1) << "\n";
  174.                     continue;
  175.                 }
  176.                 else
  177.                 {
  178.                     k -= lns[v].size() - lns[v].order_of_key(x);
  179.                 }
  180.                 get(in[v] + 1, out[v], k + 1);
  181.                 sort(ans.begin(), ans.end());
  182.                 if(k > ans.size())
  183.                     cout << -1 << "\n";
  184.                 else
  185.                     cout << ans[k - 1] << "\n";
  186.                 ans.clear();
  187.  
  188.             }
  189.         }
  190.     }
  191.     return 0;
  192. }
Runtime error #stdin #stdout 0.11s 56696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1zLpMn
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!