HackerEarth Joseph and String problem solution

1. v l r : you need to find max(i-l,r)F(v,i).
2. Lets say, t is a concatenation Sl*Sl+1 … Sr, then F(l,r – l + 1) = occur(t,S) * |t|, where occur(t,S) is the number of occurrences of string t in S.

#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define mp make_pair
#define sz(a) int((a).size())
#ifdef _WIN32
#  define I64 "%I64d"
#else
#  define I64 "%lld"
#endif
#define fname "."
#define pi pair < int, int >
#define pp pop_back

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int MAX_N = (int)1e5 + 123;
const double eps = 1e-6;
const int inf = (int)1e9 + 123;

using namespace std;

int p[MAX_N], cnt[MAX_N], c[MAX_N];
int pn[MAX_N], cn[MAX_N], lcp[MAX_N];
vector < int > h[MAX_N];
vector < pair < int, pi > > g[MAX_N];

ll ans[MAX_N];

string s;
int n;

void build() {
  s += '#';
  n = sz(s);
  for (int i = 0; i < n; i++) 
    cnt[s[i]]++;
  for (int i = 1; i <= 'z'; i++)
    cnt[i] += cnt[i - 1];
  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;
        }
        for (int i = 0; i < classes; i++)
            cnt[i] = 0;
        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 = n - 1; i >= 0; 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;
        }
        for (int i = 0; i < n; i++)
            c[i] = cn[i];
    }
    for (int i = 0, len = 0; i < n; i++) {
        int id = c[i];
        if (id == n - 1) {
            lcp[id] = len = 0;
            continue;
        }
        int j = p[id + 1];
        while(i + len < n && j + len < n && s[j + len] == s[i + len])
            len++;
        lcp[id] = len;
        len = max(len - 1, 0);
    }   
    for (int i = 0; i < n; i++)
        h[lcp[i]].pb(i);
}

vector < pi > t[4 * MAX_N];

void update(int l, int r, int len, int size, int v = 1, int tl = 0, int tr = n - 1) {
    if (l > r || tl > r || l > tr)
        return;
    if (tl >= l && tr <= r) {
        t[v].pb(mp(len, size));
        return;
    }
    int tm = (tl + tr) / 2;
    update(l, r, len, size, v * 2, tl, tm);
    update(l, r, len, size, v * 2 + 1, tm + 1, tr);
}

vector < pair < int, pair < ll, int > > > st[4 * MAX_N];
ll maxi[4 * MAX_N];
int max_len[4 * MAX_N];

void upd(int id, int x, int val, int v = 1, int tl = 0, int tr = n) {
    st[id].pb(mp(v, mp(maxi[v], max_len[v])));
    if (tl == tr) {
        maxi[v] = max(maxi[v], val * 1ll * x);
        max_len[v] = max(max_len[v], val);
        return;
    }
    int tm = (tl + tr) / 2;
    if (x <= tm)
        upd(id, x, val, v * 2, tl, tm);
    else
        upd(id, x, val, v * 2 + 1, tm + 1, tr);
    maxi[v] = max(maxi[v * 2], maxi[v * 2 + 1]);
    max_len[v] = max(max_len[v * 2], max_len[v * 2 + 1]);
}

ll get_maxi(int l, int r, int v = 1, int tl = 0, int tr = n) {
    if (l > r || tl > r || l > tr)
        return 0;
    if (tl >= l && tr <= r)
        return maxi[v];
    int tm = (tl + tr) / 2;
    return max(get_maxi(l, r, v * 2, tl, tm), get_maxi(l, r, v * 2 + 1, tm + 1, tr));
}

int gget(int l, int r, int v = 1, int tl = 0, int tr = n) {
    if (l > r || tl > r || l > tr)
        return 0;
    if (tl >= l && tr <= r)
        return max_len[v];
    int tm = (tl + tr) / 2;
    return max(gget(l, r, v * 2, tl, tm), gget(l, r, v * 2 + 1, tm + 1, tr));
}

void dfs(int v = 1, int tl = 0, int tr = n - 1) {
    for (auto i : t[v])
        upd(v, i.f, i.s);
    if (tl == tr) {
        for (auto i : g[p[tl]])
            ans[i.f] = max(i.s.s * 1ll * gget(i.s.s, n), get_maxi(i.s.f, i.s.s));
    }
    else {
        int tm = (tl + tr) / 2;
        dfs(v * 2, tl, tm), dfs(v * 2 + 1, tm + 1, tr);
    }
    while(!st[v].empty()) {
        maxi[st[v].back().f] = st[v].back().s.f;
        max_len[st[v].back().f] = st[v].back().s.s;
        st[v].pp();
    }
}

int pr[MAX_N], L[MAX_N], R[MAX_N], height[MAX_N];

int Parent(int v) {
    if (v == pr[v])
        return v;
    return pr[v] = Parent(pr[v]);
}

void Union(int a, int b) {
    a = Parent(a), b = Parent(b);
    assert(a != b);
    if (height[a] < height[b])
        swap(a, b);
    pr[b] = a;
    height[a] += (height[a] == height[b]);
    L[a] = min(L[a], L[b]);
    R[a] = max(R[a], R[b]);
}

void calc() {
    for (int i = 0; i < n; i++)
        pr[i] = L[i] = R[i] = i, height[i] = 0;
    for (int i = n; i > 0; i--) {
        for (auto j : h[i]) {
            Union(j, j + 1);
            int id = Parent(j);
            update(L[id], R[id], i, R[id] - L[id] + 1);
        }
    }
    for (int i = 0; i < n; i++)
        update(i, i, n - p[i] - 1, 1);
    dfs();
}

int Q;

int main() {
    #ifdef Nick
    freopen("check.in", "r", stdin);
    freopen("fast.out", "w", stdout);
    #endif
    ios_base :: sync_with_stdio(NULL), cin.tie(NULL);
    int waste;
    cin >> waste;
    cin >> s;
    cin >> Q;
    for (int i = 0, v, l, r; i < Q; i++) {
        cin >> v >> l >> r;
        v--;
        g[v].pb(mp(i, mp(l, r)));
    }
    build();
    calc();
    for (int i = 0; i < Q; i++)
        cout << ans[i] << 'n';
    return 0;
}