fork download
copy 
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. #define all(x) x.begin(), x.end()
  6.  
  7. #ifdef debug_local
  8. #include "debug.h"
  9. #else
  10. #define pr(...) 42
  11. #define prs(...) 42
  12. #endif
  13.  
  14. static char buf[400 << 20];
  15. void *operator new(size_t s) {
  16.   static size_t i = sizeof buf;
  17.   assert(s < i);
  18.   return (void *)&buf[i -= s];
  19. }
  20. void operator delete(void *) {}
  21.  
  22. struct Value {
  23.   int sum;
  24.   Value(int x) : sum(x) {};
  25.   Value() : sum(0) {};
  26.  
  27.   Value operator+(const Value &right) const {
  28.     Value left = *this;
  29.     Value ret = Value();
  30.     ret.sum = left.sum + right.sum;
  31.     return ret;
  32.   }
  33. };
  34.  
  35. const Value vid = Value();
  36.  
  37. struct Node {
  38.   Value val;
  39.   Node *l;
  40.   Node *r;
  41.   Node(Value x) : val(x), l(nullptr), r(nullptr) {}
  42.   Node(Node *ll, Node *rr) {
  43.     l = ll, r = rr;
  44.     val = (l ? l->val : vid) + (r ? r->val : vid);
  45.   }
  46.   Node(Node *cpy) : val(cpy->val), l(cpy->l), r(cpy->r) {}
  47. };
  48.  
  49. Node *build(int l, int r, vector<Value> &a) {
  50.   if (l + 1 == r) {
  51.     return new Node(a[l]);
  52.   }
  53.   int m = (l + r) / 2;
  54.   return new Node(build(l, m, a), build(m, r, a));
  55. }
  56.  
  57. Node *update(Node *node, Value val, int pos, int l, int r) {
  58.   if (l + 1 == r) {
  59.     return new Node(val);
  60.   }
  61.   int m = (l + r) / 2;
  62.   if (m > pos) {
  63.     return new Node(update(node->l, val, pos, l, m), node->r);
  64.   } else {
  65.     return new Node(node->l, update(node->r, val, pos, m, r));
  66.   }
  67. }
  68. Value query(Node *node, int l, int r, int ql, int qr) {
  69.   if (l >= qr || ql >= r) {
  70.     return vid;
  71.   }
  72.   if (ql <= l && r <= qr) {
  73.     return node->val;
  74.   }
  75.   int m = (l + r) / 2;
  76.   return query(node->l, l, m, ql, qr) + query(node->r, m, r, ql, qr);
  77. }
  78.  
  79. template <int sigma = 29, char mch = 'a'> struct eertree {
  80.   eertree(size_t q) {
  81.     q += 2;
  82.     s = string(q, -1);
  83.     len = vector<int>(q, 0);
  84.     to.resize(q);
  85.     link.resize(q, 0);
  86.     pos.resize(q, -1);
  87.     link[0] = 1;
  88.     link[1] = 1;
  89.     len[1] = -1;
  90.   }
  91.  
  92.   pair<int, int> add_letter(char c, int id) {
  93.     c -= 'a';
  94.     s[n++] = c;
  95.     while (c != s[n - len[last] - 2])
  96.       last = link[last];
  97.  
  98.     if (!to[last][c]) {
  99.       int cur = sz++;
  100.       len[cur] = len[last] + 2;
  101.       pos[cur] = -1;
  102.       if (len[cur] == 1) {
  103.         link[cur] = 0;
  104.       } else {
  105.         int p = link[last];
  106.         while (c != s[n - len[p] - 2])
  107.           p = link[p];
  108.         link[cur] = to[p][c];
  109.       }
  110.       to[last][c] = cur;
  111.     }
  112.  
  113.     last = to[last][c];
  114.     int x = pos[last];
  115.     pos[last] = id + 1 - len[last];
  116.     int y = pos[last];
  117.     return {x, y};
  118.   }
  119.  
  120. private:
  121.   vector<array<int, sigma>> to;
  122.   vector<int> link;
  123.   vector<int> len, pos;
  124.   string s;
  125.   int n = 1, sz = 2, last = 0;
  126. };
  127.  
  128. const int N = (int)1e5 + 1;
  129.  
  130. void solve(int tc = 1) {
  131.   int n;
  132.   cin >> n;
  133.   int q;
  134.   cin >> q;
  135.   string u;
  136.   array<int, N> l, r;
  137.   for (int i = 0; i < n; i++) {
  138.     string s;
  139.     cin >> s;
  140.     l[i] = u.size();
  141.     u += s;
  142.     u += 'a' + 27;
  143.     u += 'a' + 28;
  144.     r[i] = u.size() - 1;
  145.   }
  146.   pr(u, l, r);
  147.   n = u.size();
  148.   vector<Node *> seg(n);
  149.   vector<Value> v(n, 0);
  150.   auto paltree = eertree(n + 5);
  151.   auto now = build(0, n, v);
  152.   for (int i = 0; i < n; ++i) {
  153.     auto [x, y] = paltree.add_letter(u[i], i);
  154.     if (x != -1) {
  155.       int val = query(now, 0, n, x, x + 1).sum;
  156.       now = update(now, val - 1, x, 0, n);
  157.     }
  158.     int val = query(now, 0, n, y, y + 1).sum;
  159.     now = update(now, val + 1, y, 0, n);
  160.     seg[i] = now;
  161.   }
  162.   for (int i = 0; i < q; i++) {
  163.     int x, y;
  164.     cin >> x >> y;
  165.     --x;
  166.     --y;
  167.     int lq = l[x];
  168.     int rq = r[y];
  169.     cout << query(seg[rq], 0, n, lq, rq + 1).sum - 2 << '\n';
  170.     cout.flush();
  171.   }
  172.  
  173.   return;
  174. }
  175.  
  176. signed main() {
  177.   cin.tie(0)->sync_with_stdio(0);
  178.  
  179.   cout << setprecision(16) << fixed;
  180.   cerr << setprecision(4) << fixed;
  181.  
  182.   int tc = 1;
  183.   // cin >> tc;
  184.   for (int t = 1; t <= tc; t++) {
  185.     solve(t);
  186.   }
  187. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘void solve(int)’:
prog.cpp:150:25: error: missing template arguments before ‘(’ token
   auto paltree = eertree(n + 5);
                         ^
prog.cpp:153:10: warning: structured bindings only available with -std=c++17 or -std=gnu++17
     auto [x, y] = paltree.add_letter(u[i], i);
          ^
stdout
copy 
Standard output is empty
https://ideone.com/PPMTi6
language:
C++14 (gcc 8.3)
created:
176 days 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!