Submission #22804

#TimeUsernameProblemLanguageResultExecution timeMemory
22804AcornCkiGs14004Team (#40)New Ocurrences (KRIII5_NO)C++11
0 / 7
596 ms48980 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pi; typedef long long lint; const int MAXN = 100005; int n; struct bit{ lint tree[MAXN]; void add(int x, lint v){ x++; while(x <= n){ tree[x] += v; x += x & -x; } } lint query(int x){ x++; lint ret = 0; while(x){ ret += tree[x]; x -= x & -x; } return ret; } }bl, br; struct sfxarray{ int ord[MAXN], nord[MAXN], cnt[MAXN], aux[MAXN]; void solve(int n, char *str, int *sfx, int *rev, int *lcp){ int p = 1; memset(ord, 0, sizeof(ord)); for(int i=0; i<n; i++){ sfx[i] = i; ord[i] = str[i]; } int pnt = 1; while(1){ memset(cnt, 0, sizeof(cnt)); for(int i=0; i<n; i++){ cnt[ord[min(i+p, n)]]++; } for(int i=1; i<=n || i<=255; i++){ cnt[i] += cnt[i-1]; } for(int i=n-1; i>=0; i--){ aux[--cnt[ord[min(i+p, n)]]] = i; } memset(cnt, 0, sizeof(cnt)); for(int i=0; i<n; i++){ cnt[ord[i]]++; } for(int i=1; i<=n || i<=255; i++){ cnt[i] += cnt[i-1]; } for(int i=n-1; i>=0; i--){ sfx[--cnt[ord[aux[i]]]] = aux[i]; } if(pnt == n) break; pnt = 1; nord[sfx[0]] = 1; for(int i=1; i<n; i++){ if(ord[sfx[i-1]] != ord[sfx[i]] || ord[sfx[i-1] + p] != ord[sfx[i] + p]){ pnt++; } nord[sfx[i]] = pnt; } memcpy(ord, nord, sizeof(int) * n); p *= 2; } for(int i=0; i<n; i++){ rev[sfx[i]] = i; } int h = 0; for(int i=0; i<n; i++){ if(rev[i]){ int prv = sfx[rev[i] - 1]; while(str[prv + h] == str[i + h]) h++; lcp[rev[i]] = h; } h = max(h-1, 0); } } }sfxarray; char str[100005]; int sfx[100005], rev[100005], lcp[100005]; lint ans[100005]; vector<pi> q[100005]; void solve(int s, int e){ if(s == e) return; int m = (s+e)/2; solve(s, m); solve(m+1, e); int l = lcp[m+1]; int pl = m, pr = m+1; ans[min(sfx[m], sfx[m+1])] += l; bl.add(sfx[m], 1); br.add(sfx[m+1], 1); while(pl > s || pr < e){ if((pr < e && min(l, lcp[pl]) < min(l, lcp[pr+1])) || pl == s){ l = min(l, lcp[pr+1]); int cnt = bl.query(n) - bl.query(sfx[pr+1]); q[pl].push_back(pi(sfx[pr+1], l)); q[m+1].push_back(pi(sfx[pr+1], -l)); ans[sfx[pr+1]] += 1ll * cnt * l; br.add(sfx[pr+1], 1); pr++; } else{ l = min(l, lcp[pl]); int cnt = br.query(n) - br.query(sfx[pl-1]); q[m+1].push_back(pi(sfx[pl-1], l)); q[pr+1].push_back(pi(sfx[pl-1], -l)); ans[sfx[pl-1]] += 1ll * cnt * l; bl.add(sfx[pl-1], 1); pl--; } } for(int i=s; i<=m; i++) bl.add(sfx[i], -1); for(int i=m+1; i<=e; i++) br.add(sfx[i], -1); } int main(){ cin >> str; n = strlen(str); reverse(str, str + n); sfxarray.solve(n, str, sfx, rev, lcp); solve(0, n-1); for(int i=0; i<n; i++){ for(auto &j : q[i]){ bl.add(j.first, j.second); } ans[sfx[i]] += bl.query(n) - bl.query(sfx[i]); } for(int i=0; i<n; i++) ans[i] *= 2; for(int i=n-1; i>=0; i--){ ans[i] += ans[i+1] + (n - i); cout << ans[i] << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...