QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#382388 | #7901. Basic Substring Structure | EBeason | WA | 38ms | 84088kb | C++20 | 7.4kb | 2024-04-08 13:23:57 | 2024-04-08 13:23:58 |
Judging History
answer
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
// #define int ll
#define ls p << 1
#define rs p << 1 | 1
#define lowbit(x) ((x) & (-x))
#define endl '\n'
#define ld long double
#define MULTI_CASES
const int MaxN = 1e6 + 100;
const int INF = 1e9;
int T, N, M, K;
int ans[MaxN];
vector<int> a;
struct SA {
int sa[MaxN], rk[MaxN], oldrk[MaxN << 1], id[MaxN], key1[MaxN], cnt[MaxN], height[MaxN];
int st[MaxN][25], logn[MaxN];
int n;
vector<int> s;
void init(int _n) {
n = _n;
for (int i = 0; i <= n + 1; i++) {
sa[i] = 0;
rk[i] = 0;
oldrk[i] = 0;
cnt[i] = 0;
key1[i] = 0;
id[i] = 0;
height[i] = 0;
}
getsa();
getheight();
}
bool cmp(int x, int y, int w) {
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
inline void getsa() {
int i, m = n + 1, p, w;
// sa[i]表示后缀排序第i小的编号
// rk[i]表示后缀i的排名
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;
for (w = 1;; w <<= 1, m = p) { // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;
memset(cnt, 0, m * sizeof(int));
for (i = 1; i <= n; ++i) ++cnt[key1[i] = rk[id[i]]];
// 注意这里px[i] != i,因为rk没有更新,是上一轮的排名数组
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[key1[i]]--] = id[i];
memcpy(oldrk + 1, rk + 1, n * sizeof(int));
for (p = 0, i = 1; i <= n; ++i) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
if (p == n) break;
}
}
inline void getheight(){
// height[i]=lcp(sa[i],sa[i-1])
int i, k;
for (i = 1, k = 0; i <= n; ++i) {
if (rk[i] == 0) continue;
if (k) --k;
while (i + k <= n && s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
height[rk[i]] = k;
}
}
inline void pre() {
logn[0] = -1;
int LogN = log2(n) + 1;
for (int i = 1; i <= n; i++) logn[i] = logn[i / 2] + 1;
for (int i = 1; i <= n; i++) st[i][0] = height[i];
for (int j = 1; j <= LogN; j++) {
int pj = 1 << (j - 1);
for (int i = 1; i <= n; i++) {
if (i + pj <= n)
st[i][j] = min(st[i][j - 1], st[i + pj][j - 1]);
else
st[i][j] = st[i][j - 1];
}
}
}
inline int lcp(int l, int r) {
if (l == r) return n - l + 1;
l = rk[l];
r = rk[r];
if (l > r) swap(l, r);
l++;
int lp = r - l + 1;
int n = 1 << logn[lp];
return min(st[l][logn[lp]], st[r - n + 1][logn[lp]]);
}
} SA;
struct TT {
int a[MaxN];
struct Point {
ll sum, lan;
} tree[MaxN << 2], ts;
void js(int p, int x, int y, int z) {
tree[p].sum += (y - x + 1) * z;
tree[p].lan += z;
}
void pushdown(int p,int l, int r) {
if (tree[p].lan) {
int mid = (l + r) >> 1;
js(ls, l, mid, tree[p].lan);
js(rs, mid + 1, r, tree[p].lan);
}
}
inline Point pushup(Point L, Point R) {
Point now = Point();
now.sum = L.sum + R.sum;
return now;
}
void build(int p, int l, int r) {
if (l == r) {
tree[p].sum = a[l];
tree[p].lan = 0;
return;
}
pushdown(p, l, r);
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
tree[p] = pushup(tree[ls], tree[rs]);
}
void change(int p, int l, int r, int x, int y, int z) {
if (x > y || l > N) return;
if (l >= x && r <= y) {
js(p, l, r, z);
return;
}
pushdown(p, l, r);
int mid = (l + r) >> 1;
if (mid >= x) change(ls, l, mid, x, y, z);
if (mid < y) change(rs, mid + 1, r ,x ,y, z);
tree[p] = pushup(tree[ls], tree[rs]);
}
Point query(int p, int l, int r, int x, int y) {
if (l >= x && r <= y) {
return tree[p];
}
pushdown(p, l, r);
int mid = (l + r) >> 1;
if (mid >= x && mid < y) {
return pushup(query(ls, l, mid, x, y), query(rs, mid + 1, r, x, y));
}
if (mid >= x) return query(ls, l, mid, x, y);
if (mid < y) return query(rs, mid + 1, r, x, y);
return Point();
}
} TT;
ll g[MaxN], b[MaxN];
void updata(int l, int r, int k, int d) {
// cerr << l << ' ';
// cerr << r << ' ';
// cerr << k << ' ';
// cerr << d << endl;
if (l > r) return;
TT.change(1, 1, N, l + 1, r, 1);
TT.change(1, 1, N, l, l, k);
TT.change(1, 1, N, r + 1, r + 1, -k - d * (r - l));
}
struct my_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map<int ,ll, my_hash> mp[MaxN];
int js(int x, int y) {
// if (a[x] == a[1]) return 0;
int t = SA.lcp(x + 1, y + 1) + 1;
if (x + t >= y) {
int len = y - x;
t = len;
if (x <= N && y + len <= N && a[x] == a[y + len]) {
t += SA.lcp(x + len + 1, y + len + 1) + 1;
}
return t;
} else {
return t;
}
}
inline void Solve() {
cin >> N;
a.assign(N + 1, 0);
for (int i = 1; i <= N; i++) {
cin >> a[i];
mp[i].clear();
}
SA.s = a;
SA.init(N);
SA.pre();
for (int i = 1; i <= N; i++) {
g[i] = SA.lcp(1, i);
// cerr << g[i] << ' ';
}
int sum = 0;
for (int i = 1; i <= N; i++) {
sum += g[i];
TT.a[i] = 0;
}
TT.a[1] = sum;
TT.build(1, 1, N);
for (int i = 1; i <= N; i++) {
int l = 1, r = g[i];
int x = i, y = x + g[i] - 1;
if (i == 1) continue;
if (r < x) {
updata(l, r, -g[i], 1);
updata(x, y, -g[i], 1);
} else if (x <= r) {
updata(l, x - 1, -g[i], 1);
updata(x, y, -g[i], 1);
}
// for (int i = 1; i <= N; i++) {
// b[i] = b[i - 1];
// b[i] += TT.query(1, 1, N, i, i).sum;
// cerr << b[i] << ' ';
// } cerr << endl;
}
// updata(1, 2, -2, 1);
for (int i = 1; i <= N; i++) {
b[i] = b[i - 1];
b[i] += TT.query(1, 1, N, i, i).sum;
// cerr << b[i] << ' ';
}
// cerr << endl;
for (int i = 1; i <= N; i++) {
int x = g[i] + 1, y = i + g[i];
if (y <= N && x <= N) {
if (x >= i) {
} else {
mp[x][a[y]] += SA.lcp(x + 1, y + 1) + 1;
}
mp[y][a[x]] += js(x, y);
// cerr << x << ' ';
// cerr << a[y] << ' ';
// cerr << y << ' ';
// cerr << a[x] << endl;
}
}
ll jg = 0;
for (int i = 1; i <= N; i++) {
ans[i] = b[i];
// int id = 0;
for (auto it : mp[i]) {
int ts = b[i] + it.second;
if (it.first == a[i]) continue;
if (ts > ans[i]) {
ans[i] = ts;
// id = it.first;
}
ans[i] = max(ans[i], ts);
// cerr << i << ' ';
// cerr << it.first << ' ';
// cerr << it.second << endl;
}
jg += (1ll * ans[i]) ^ i;
// cerr << id << ' ';
}
// cerr << endl;
// for (int i = 1; i <= N; i++) {
// cerr << b[i] << ' ';
// } cerr << endl;
// for (int i = 1; i <= N; i++) {
// cerr << ans[i] << ' ';
// }
// cerr << endl;
cout << jg << endl;
}
signed main() {
// ld be, ed;
// be = clock();
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
srand(time(NULL));
#ifdef MULTI_CASES
int T;
cin >> T;
while (T--)
#endif
Solve();
// ed = clock();
// cerr << (ed - be) / CLOCKS_PER_SEC << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 8ms
memory: 83540kb
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: 38ms
memory: 84088kb
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 560 4 218 12 294 313 269 18 98 148 77 388 202 3 484 392 350 463 8 19 125 77 22 103 59 268 11 63 50 161 81 116 289 207 29 64 367 74 126 21 24 68 343 470 406 465 337 309 530 472 237 321 3 369 55 299 3 61 49 147 385 49 465 127 312 4 165 549 247 20 171 6 503 602 390 104 266 352 20 57 21 432 3 28 ...
result:
wrong answer 3rd lines differ - expected: '347', found: '560'