QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#339565 | #7901. Basic Substring Structure | goodier | WA | 17ms | 25320kb | C++14 | 4.6kb | 2024-02-27 15:54:27 | 2024-02-27 15:54:28 |
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++)
{
s1[i] = s2[i] = s3[i] = s4[i] = y[i] = 0, mp1[i].clear();
sa[i] = x[i] = rk[i] = height[i] = 0;
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 24948kb
input:
2 4 2 1 1 2 12 1 1 4 5 1 4 1 9 1 9 8 10
output:
15 217
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 17ms
memory: 25320kb
input:
10000 8 2 1 2 1 1 1 2 2 9 2 2 1 2 1 2 1 2 1 15 2 1 2 1 1 1 1 2 2 1 2 1 2 2 1 2 1 1 10 2 1 1 1 2 2 1 1 2 2 3 2 1 2 11 1 2 2 1 1 2 1 2 2 1 1 14 2 1 1 1 1 2 1 1 1 2 2 1 2 1 12 2 2 2 1 2 2 2 1 1 2 1 2 4 2 1 1 2 8 1 2 2 2 1 2 1 1 8 1 1 2 1 2 1 1 1 6 2 1 1 1 2 2 14 2 2 1 1 1 1 2 2 2 1 2 2 1 1 10 1 2 2 1 1...
output:
94 128 347 3 211 9 265 363 278 15 95 114 58 348 225 3 335 364 377 316 3 19 122 65 15 83 36 261 11 64 28 90 85 104 252 191 21 48 303 63 102 20 24 68 316 362 266 309 354 281 326 281 231 312 3 330 54 328 3 69 32 147 322 39 338 89 242 3 165 346 245 20 155 3 404 393 392 81 269 360 20 54 21 279 3 17 351 3...
result:
wrong answer 24th lines differ - expected: '66', found: '65'