QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#339569 | #7901. Basic Substring Structure | goodier | WA | 3ms | 14336kb | C++14 | 4.6kb | 2024-02-27 15:55:27 | 2024-02-27 15:55:27 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
#define mp make_pair
using namespace std;
const int N = 2e5 + 10, INF = 1e8;
typedef long long ll;
typedef pair<int,ll> PIL;
ll s1[N], s2[N], ans;
int s[N], slen[N], s3[N], s4[N], c[N], x[N], y[N], sa[N], rk[N], height[N], f[N][19], len[N], n;
map <int, ll> mp1[N];
void get_sa()
{
int m = n;
for(int i = 1; i <= m; i++) c[i] = 0;
for(int i = 1; i <= n; i++) c[x[i] = s[i]]++;
for(int i = 1; i <= m; i++) c[i] += c[i - 1];;
for(int i = n; i; i--) sa[c[x[i]]--] = i;
for(int k = 1; k <= n; k <<= 1)
{
int num = 0;
for(int i = n - k + 1; i <= n; i++) y[++num] = i;
for(int i = 1; i <= n; i++)
{
if(sa[i] > k)
{
y[++num] = sa[i] - k;
}
}
for(int i = 1; i <= m; i++) c[i] = 0;
for(int i = 1; i <= n; i++) c[x[i]]++;
for(int i = 1; i <= m; i++) c[i] += c[i - 1];
for(int i = n; i; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
for(int i = 1; i <= n; i++) swap(x[i], y[i]); m = 0;
for(int i = 1; i <= n; i++)
{
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? m : ++m;
}
if(m == n) break;
}
}
void get_height()
{
for(int i = 1; i <= n; i++) rk[sa[i]] = i;
for(int i = 1, k = 0; i <= n; i++)
{
if(rk[i] == 1) continue;
if(k) k--;
int j = sa[rk[i] - 1];
while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
height[rk[i]] = k;
}
}
void init()
{
for(int i = 2; i <= n; i++) len[i] = len[i >> 1] + 1;
for(int i = 1; i <= n; i++) f[i][0] = height[i];
for(int j = 1; j <= len[n]; j++)
{
for(int i = 1; i + (1 << j) - 1 <= n; i++)
{
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
}
int querymn(int l, int r)
{
if(l > r) return INF;
int t = len[r - l + 1];
return min(f[l][t], f[r - (1 << t) + 1][t]);
}
int lcp(int i, int j)
{
if(i == j) return n - i + 1;
if(i > n || j > n) return 0;
if(rk[i] > rk[j]) swap(i, j);
return querymn(rk[i] + 1, rk[j]);
}
int getlcp(int i, int j, int x, int y)
{
if(i > n || j > n) return 0;
if(i == j) return n - i + 1;
int len = lcp(i, j);
if(i + len - 1 >= x - 1)
{
len = x - i;
if(y == s[j + len])
{
len++;
len += lcp(i + len, j + len);
}
}
return len;
}
void add(int x, int y)
{
x++;
for(; x <= n + 1; x += x & -x) c[x] += y;
}
int ask(int x)
{
x++;
int res = 0;
for(; x; x -= x & -x) res += c[x];
return res;
}
int main()
{
freopen("data.in", "r", stdin);
int T;
scanf("%d", &T);
for(int TT = 1; TT <= T; TT++)
{
scanf("%d", &n);
ans = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d", &s[i]);
}
get_sa(), get_height(), init();
for(int i = 0; i <= n + 1; i++) c[i] = 0;
for(int j = 2; j <= n; j++)
{
slen[j] = lcp(1, j);
int l1 = 1, r1 = slen[j], l2 = j, r2 = j + slen[j] - 1;
s2[l2] += j, s2[r2 + 1] -= j; s3[l2]++, s3[r2 + 1]--;
if(r1 >= l2)
{
s1[r2 + 1] += slen[j];
}
else
{
s1[r1 + 1] += slen[j], s1[l2] -= slen[j], s1[r2 + 1] += slen[j];
}
add(slen[j], 1);
if(r2 < n)
{
if(r1 + 1 < l2) mp1[r1 + 1][s[r2 + 1]] = mp1[r1 + 1][s[r2 + 1]] + 1 + lcp(r1 + 2, r2 + 2);
mp1[r2 + 1][s[r1 + 1]] = mp1[r2 + 1][s[r1 + 1]] + 1 + getlcp(r1 + 2, r2 + 2, r2 + 1, s[r1 + 1]);
}
}
ll sum1 = 0, sum3 = 0; int sum2 = 0;
for(int i = 1; i <= n; i++)
{
add(slen[i], -1);
sum1 += s2[i], sum2 += s3[i], sum3 += s1[i];
ll ans1 = 0, ans2 = 0;
ans1 = (ll)(ask(n) - ask(i - 1)) * (i - 1) + (ll)i * sum2 - sum1 + n + sum3;
for(auto it = mp1[i].begin(); it != mp1[i].end(); it++)
{
ans2 = max(ans2, (*it).y);
}
//cout << ans1 + ans2 << " ";
ans = ans + ((ans1 + ans2) ^ i);
}
//cout << endl;
printf("%lld\n", ans);
for(int i = 1; i <= n + 1; i++)
{
slen[i] = 0;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 14336kb
input:
2 4 2 1 1 2 12 1 1 4 5 1 4 1 9 1 9 8 10
output:
result:
wrong answer 1st lines differ - expected: '15', found: ''