[Toph] Unique Substrings Query

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Unique Substrings Query
Source            : Toph.co
Category          : Data Structure, String
Algorithm         : Suffix Automaton, Binary Indexed Tree, Persistent Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll            long long int
#define endl          '\n'
 
static const int maxn = 2e3 + 5;
static const ll mod = 1e9 + 7;
static const int Max = 6e6 + 7;
 
int N = 1000 + 2;
ll Bit[maxn];
 
ll add(ll a, ll b)
{
      a = (a + b);
      return a;
}
 
void bitUpdate(int pos, ll val)
{
      while (pos <= N)
      {
            Bit[pos] = add(Bit[pos], val);
            pos += (pos & -pos);
      }
}
 
void rangeUpdate(int l, int r, ll val)
{
      bitUpdate(l, val);
      bitUpdate(r + 1, -val);
}
 
ll read(int pos)
{
      ll sum = 0;
      while (pos > 0)
      {
            sum = add(sum, Bit[pos]);
            pos -= (pos & -pos);
      }
      return sum;
}
 
struct state
{
      int len, link;
      map <char, int> next;
} st[maxn * 2];
 
int sz, last;
 
void init()
{
      sz = last = 0;
      st[0].len = 0;
      st[0].link = -1;
      st[0].next.clear();
      for (int i = 1; i < maxn * 2; i++)
      {
            st[i].len = 0;
            st[i].link = 0;
            st[i].next.clear();
      }
      ++sz;
}
 
void szExtend(char c)
{
      int l, r;
      int cur = sz++;
      st[cur].len = st[last].len + 1;
      int p;
      for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link)
      {
            st[p].next[c] = cur;
      }
      if (p == -1)
      {
            st[cur].link = 0;
      }
      else
      {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len)
            {
                  st[cur].link = q;
            }
            else
            {
                  int clone = sz++;
                  st[clone].len = st[p].len + 1;
                  st[clone].next = st[q].next;
                  st[clone].link = st[q].link;
                  for ( ; p != -1 && st[p].next[c] == q; p = st[p].link)
                  {
                        st[p].next[c] = clone;
                  }
                  l = st[ st[q].link ].len;
                  r = st[q].len;
                  assert(l+1 <= r);
                  rangeUpdate(l+1, r, -1);
                  st[q].link = st[cur].link = clone;
                  l = st[ st[q].link ].len;
                  r = st[q].len;
                  assert(l+1 <= r);
                  rangeUpdate(l+1, r, 1);
                  l = st[ st[clone].link ].len;
                  r = st[clone].len;
                  assert(l+1 <= r);
                  rangeUpdate(l+1, r, 1);
            }
      }
      l = st[ st[cur].link ].len;
      r = st[cur].len;
      assert(l+1 <= r);
      rangeUpdate(l+1, r, 1);
      last = cur;
}
 
 
struct Node
{
      ll st;
      int lft, rgt;
      Node(ll st = 0, int lft = 0, int rgt = 0) : st(st), lft(lft), rgt(rgt) {}
} Tree[Max];
 
int version[maxn];
int NODES;
//int N = 1000;
 
int update(int root, int a, int b, int pos, ll val)
{
      int newNode = ++NODES;
      Tree[newNode] = Tree[root];
      if (a == b)
      {
            Tree[newNode].st += val;
            return newNode;
      }
      int mid = (a + b) >> 1;
      if (pos <= mid) Tree[newNode].lft = update(Tree[newNode].lft, a, mid, pos, val);
      else Tree[newNode].rgt = update(Tree[newNode].rgt, mid + 1, b, pos, val);
      Tree[newNode].st = Tree[ Tree[newNode].lft ].st + Tree[ Tree[newNode].rgt ].st;
      return newNode;
}
 
ll query(int proot, int root, int a, int b, int i, int j)
{
      if (a > b or a > j or b < i) return 0;
      if (a >= i && b <= j)
      {
            return Tree[root].st - Tree[proot].st;
      }
      int mid = a + b >> 1;
      ll p = query(Tree[proot].lft, Tree[root].lft, a, mid, i, j);
      ll q = query(Tree[proot].rgt, Tree[root].rgt, mid + 1, b, i, j);
      return p + q;
}
 
int originalVersion[maxn];
 
signed main()
{
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
      cout << fixed << setprecision(8);
 
      #ifndef ONLINE_JUDGE
            freopen("in.txt", "r", stdin);
      #endif // ONLINE_JUDGE
 
      int n, m;
      cin >> n >> m;
      string s;
      cin >> s;
      s = "#" + s;
 
      NODES = 0;
      version[0] = 0;
      for (int i = 0; i < maxn; i++) Tree[i] = Node();
 
      int ptr = 0;
      originalVersion[n + 1] = 0;
      init();
      int len = 0;
      for (int i = n; i >= 1; i--)
      {
            szExtend(s[i]);
            ++len;
            ++ptr;
            originalVersion[i] = ptr;
            bool isCreated = 0;
            for (int j = 1; j <= len; j++)
            {
                  ll val = read(j);
                  if (isCreated == 0)
                  {
                        version[ptr] = update(version[ptr - 1], 1, N, j, val);
                        isCreated = 1;
                  }
                  else
                  {
                        version[ptr] = update(version[ptr], 1, N, j, val);
                  }
            }
      }
      while (m--)
      {
            int L, R, P, Q;
            cin >> L >> R >> P >> Q;
            ll ans = query(version[ originalVersion[R + 1] ], version[ originalVersion[L] ], 1, N, P, Q);
            cout << ans << '\n';
      }
}