[Light OJ] 1314 - Names for Babies

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1314 - Names for Babies
Source            : Light Online Judge
Category          : String, Data Structure
Algorithm         : Suffix Automata, Segment Tree, Lazy Propagation
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll            long long int
 
static const int maxn = 1e4 + 5;
 
int N;
 
struct segmentTree
{
      ll val, lazyval;
      bool lazy;
      segmentTree(ll val = 0, ll lazyval = 0, bool lazy = 0) :
            val(val), lazyval(lazyval), lazy(lazy) {}
} Tree[maxn << 2];
 
inline void updateLazy(int node, int a, int b, ll lazyval)
{
      Tree[node].val += (b - a + 1) * lazyval;
      Tree[node].lazyval += lazyval;
      Tree[node].lazy = 1;
}
 
inline void updateNode(int node, int a, int b)
{
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) / 2;
      Tree[lft].val += (mid - a + 1) * Tree[node].lazyval;
      Tree[lft].lazyval += Tree[node].lazyval;
      Tree[lft].lazy = 1;
 
      Tree[rgt].val += (b - mid) * Tree[node].lazyval;
      Tree[rgt].lazyval += Tree[node].lazyval;
      Tree[rgt].lazy = 1;
 
      Tree[node].lazyval = 0;
      Tree[node].lazy = 0;
}
 
inline void update(int node, int a, int b, int i, int j, ll lazyval)
{
      if (a == i && b == j)
      {
            updateLazy(node, a, b, lazyval);
            return;
      }
      if (Tree[node].lazy)
      {
            updateNode(node, a, b);
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      if (j <= mid)
      {
            update(lft, a, mid, i, j, lazyval);
      }
      else if (i > mid)
      {
            update(rgt, mid+1, b, i, j, lazyval);
      }
      else
      {
            update(lft, a, mid, i, mid, lazyval);
            update(rgt, mid+1, b, mid+1, j, lazyval);
      }
      Tree[node].val = Tree[lft].val + Tree[rgt].val;
}
 
inline ll query(int node, int a, int b, int i, int j)
{
      if (a == i && b == j) return Tree[node].val;
      if (Tree[node].lazy) updateNode(node, a, b);
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      ll res = 0;
      if (j <= mid) res += query(lft, a, mid, i, j);
      else if (i > mid) res += query(rgt, mid+1, b, i, j);
      else res += query(lft, a, mid, i, mid) + query(rgt, mid+1, b, mid+1, j);
      return res;
}
 
struct state
{
      int len, link;
      map <char, int> next;
} st[maxn << 1];
 
int sz, last;
 
inline void init()
{
      sz = last = 0;
      st[0].len = 0;
      st[0].link = -1;
      st[0].next.clear();
      for (int i = 1; i < (maxn << 1); i++)
      {
            st[i].len = 0;
            st[i].link = 0;
            st[i].next.clear();
      }
      ++sz;
}
 
inline ll sz_extend(char c)
{
      ll sum = 0;
      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;
                  }
                  sum = sum - (st[q].len - st[ st[q].link ].len);
                  l = st[ st[q].link ].len;
                  r = st[q].len;
                  assert(l+1 <= r);
                  update(1, 1, N, l+1, r, -1);
 
                  st[q].link = st[cur].link = clone;
 
                  sum = sum + st[q].len - st[ st[q].link ].len;
                  l = st[ st[q].link ].len;
                  r = st[q].len;
                  assert(l+1 <= r);
                  update(1, 1, N, l+1, r, 1);
 
                  sum = sum + st[clone].len - st[ st[clone].link ].len;
                  l = st[ st[clone].link ].len;
                  r = st[clone].len;
                  assert(l+1 <= r);
                  update(1, 1, N, l+1, r, 1);
            }
      }
      sum = sum + st[cur].len - st[ st[cur].link ].len;
      l = st[ st[cur].link ].len;
      r = st[cur].len;
      assert(l+1 <= r);
      update(1, 1, N, l+1, r, 1);
      last = cur;
      return sum;
}
 
char s[maxn];
 
int main()
{
      //freopen("in.txt", "r", stdin);
      int tc;
      scanf("%d", &tc);
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            scanf("%s", s);
            int p, q;
            scanf("%d %d", &p, &q);
            int len = strlen(s);
            init();
            ll tsubstr = 0;
            N = len;
            for (int i = 0; i < len; i++) tsubstr += sz_extend(s[i]);
            ll ans = query(1, 1, N, p, q);
            printf("Case %d: %lld\n", tcase, ans);
            for (int i = 1; i < (maxn << 2); i++) Tree[i] = segmentTree();
      }
}