Sherlock and Unique Substrings

#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <sstream>
#include <map>
#include <set>
#include <numeric>
#include <memory.h>
#include <cstdio>
#include <assert.h>

using namespace std;

#define pb push_back
#define INF 1011111111
#define FOR(i, a, b) for (int _n(b), i(a); i < _n; i++)
#define rep(i, n) FOR(i, 0, n)
#define CL(a, v) memset((a), (v), sizeof(a))
#define mp make_pair
#define X first
#define Y second
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))

typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> pii;

/*** TEMPLATE CODE ENDS HERE */

const int maxn = 1e5 + 5;
const int BLOCK = 320;

int classes[maxn];
int sa[maxn];
int lcp[maxn];

void BuildSuffixArray2(char *S, int n) {
  static pair<pii, int> buff[2 * maxn + 10];

  rep(i, n) classes[i] = S[i];

  for (int k = 1; k <= n; k <<= 1) {
    rep(i, n) buff[i] = mp(mp(classes[i], classes[(i + k) % n]), i);

    sort(buff, buff + n);
    int C = 0;

    rep(i, n) {
      if (!i || buff[i].X != buff[i - 1].X) {
        C++;
      }
      classes[buff[i].Y] = C - 1;
      sa[i] = buff[i].Y;
    }
  }
}

const int kMaxAlphabet = 256;

int nsa[maxn];
int nclasses[maxn];
int p[maxn], cnt[maxn], c[maxn];
int pn[maxn], cn[maxn];

void BuildSuffixArray(char *s, int n) {
  memset(cnt, 0, kMaxAlphabet * sizeof(int));
  for (int i = 0; i < n; ++i) ++cnt[s[i]];
  for (int i = 1; i < kMaxAlphabet; ++i) cnt[i] += cnt[i - 1];
  for (int i = kMaxAlphabet - 1; i >= 0; --i) cnt[i] = i > 0 ? cnt[i - 1] : 0;
  for (int i = 0; i < n; ++i) p[cnt[s[i]]++] = i;
  c[p[0]] = 0;
  int classes = 1;
  for (int i = 1; i < n; ++i) {
    if (s[p[i]] != s[p[i - 1]]) ++classes;
    c[p[i]] = classes - 1;
  }

  for (int h = 0; (1 << h) < n; ++h) {
    for (int i = 0; i < n; ++i) {
      pn[i] = p[i] - (1 << h);
      if (pn[i] < 0) pn[i] += n;
    }
    memset(cnt, 0, classes * sizeof(int));
    for (int i = 0; i < n; ++i) ++cnt[c[pn[i]]];
    for (int i = 1; i < classes; ++i) cnt[i] += cnt[i - 1];
    for (int i = classes - 1; i >= 0; --i) cnt[i] = i > 0 ? cnt[i - 1] : 0;
    for (int i = 0; i < n; ++i) p[cnt[c[pn[i]]]++] = pn[i];
    cn[p[0]] = 0;
    classes = 1;
    for (int i = 1; i < n; ++i) {
      int mid1 = (p[i] + (1 << h)) % n, mid2 = (p[i - 1] + (1 << h)) % n;
      if (c[p[i]] != c[p[i - 1]] || c[mid1] != c[mid2]) ++classes;
      cn[p[i]] = classes - 1;
    }
    memcpy(c, cn, n * sizeof(int));
  }
  rep(i, n) sa[i] = p[i];
}

static int isa[maxn];

void BuildLcp(char *S, int n) {
  rep(i, n) isa[sa[i]] = i;

  int L = 0;
  rep(i, n) {
    L = max(0, L - 1);
    if (isa[i] + 1 < n) {
      int nxt = sa[isa[i] + 1];
      while (S[i + L] == S[nxt + L]) ++L;
    }
    lcp[isa[i]] = L;
  }
}

struct Query {
  int l, r, idx;
};

bool cmp(const Query &A, const Query &B) {
  if (A.l / BLOCK != B.l / BLOCK) return A.l / BLOCK < B.l / BLOCK;
  return A.r > B.r;
}

char s[maxn];

Query q[maxn];

ll ans[maxn];

ll tr1[maxn];
ll tr2[maxn];

int N;
void update(ll tr[], int i, ll by) {
  for (++i; i <= N; i += -i & i) tr[i] += by;
}

void update(int a, int b, int by) {
  update(tr1, a, by);
  update(tr1, b + 1, -by);
  update(tr2, a, by * (a - 1));
  update(tr2, b + 1, -by * b);
}

ll query(ll tr[], int i) {
  ll s = 0;
  for (++i; i > 0; i -= -i & i) s += tr[i];
  return s;
}

ll query(int x) { return query(tr1, x) * x - query(tr2, x); }

ll query(int a, int b) { return query(b) - query(a); }

void remove(int i) {
  int r = isa[i];
  int common = lcp[r];
  if (r > 0) common = max(common, lcp[r - 1]);
  int len = N - i;

  update(i + common, i + len - 1, -1);
}

void add(int i) {
  int r = isa[i];
  int common = lcp[r];
  if (r > 0) common = max(common, lcp[r - 1]);
  int len = N - i;

  // add 1 to range [i + common, i + len - 1]
  update(i + common, i + len - 1, 1);
}

int main() {
#ifdef LOCAL_HOST
  freopen("input.txt", "r", stdin);
// freopen("output.txt","w",stdout);
#endif

  scanf("%s", s);
  int Q = 0;
  scanf("%d", &Q);
  rep(i, Q) {
    scanf("%d %d", &q[i].l, &q[i].r);
    q[i].idx = i;
    q[i].l--;
    q[i].r--;
  }

  sort(q, q + Q, cmp);

  int n = (int)strlen(s);
  N = n;
  s[n++] = '#';

  BuildSuffixArray(s, n);
  BuildLcp(s, n);
  --n;

  //  FOR(i, 1, n + 1) {
  //    FOR(j, sa[i], n) cout << s[j];
  //    cout << " " << lcp[i];
  //    cout << endl;
  //  }

  //  printf("%s\n", s);
  //  rep(i, n) {
  //    int r = isa[i];
  //    int common = lcp[r];
  //    if (r > 0) common = max(common, lcp[r - 1]);
  //    printf("%d %d ", common, n - i);
  //    FOR(j, sa[r], n) cout << s[j];
  //    cout << endl;
  //  }

  int currentL = 0, currentR = 0;
  rep(i, Q) {
    int L = q[i].l, R = q[i].r;

    while (currentL < L) {
      remove(currentL);
      currentL++;
    }
    while (currentL > L) {
      add(currentL - 1);
      currentL--;
    }
    while (currentR <= R) {
      add(currentR);
      currentR++;
    }
    while (currentR > R + 1) {
      remove(currentR - 1);
      currentR--;
    }
    ans[q[i].idx] = query(currentL, currentR - 1);
  }

  rep(i, Q) cout << ans[i] << endl;

#ifdef LOCAL_HOST
  printf("TIME: %.3lf\n", double(clock()) / CLOCKS_PER_SEC);
#endif

  return 0;
}