QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #381873 | #7901. Basic Substring Structure | KULIANLEN | WA | 709ms | 88768kb | C++17 | 7.1kb | 2024-04-07 21:05:57 | 2024-04-07 21:05:59 |
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;
void init(vector<int> s1, int _n) {
n = _n;
for (int i = 0; i <= max(n + 1, 127); i++) {
sa[i] = 0;
rk[i] = 0;
oldrk[i] = 0;
cnt[i] = 0;
key1[i] = 0;
id[i] = 0;
height[i] = 0;
}
getsa(s1);
getheight(s1);
}
bool cmp(int x, int y, int w) {
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
inline void getsa(vector<int> s) {
int i, m = 127, p, w;
// sa[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, sizeof(cnt));
for (i = 1; i <= n; ++i) ++cnt[key1[i] = rk[id[i]]];
// 娉ㄦ剰杩欓噷px[i] != i锛屽洜涓簉k娌℃湁鏇存柊锛屾槸涓婁竴杞殑鎺掑悕鏁扮粍
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(vector<int> s){
// 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;
for (int i = 1; i < MaxN; i++) logn[i] = logn[i / 2] + 1;
for (int i = 1; i <= n; i++) st[i][0] = height[i];
for (int j = 1; j <= 20; 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> mp[MaxN];
int js(int x, int y) {
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.init(a, 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) mp[x][a[y]] += SA.lcp(x + 1, y + 1) + 1;
if (x <= N && y <= N) 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];
for (auto it : mp[i]) {
int ts = b[i] + it.second;
if (ts > ans[i]) {
ans[i] = ts;
}
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() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
srand(time(NULL));
#ifdef MULTI_CASES
int T;
cin >> T;
T= min(T,900);
while (T--)
#endif
Solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 88768kb
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: 709ms
memory: 87476kb
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:
100 133 352 3 212 16 263 312 282 17 97 124 85 308 228 3 362 391 362 312 14 17 127 76 13 150 43 244 16 82 40 116 130 98 236 223 27 47 379 73 124 20 24 65 311 356 264 311 363 278 328 290 236 333 3 331 71 328 3 70 35 146 410 56 384 91 245 4 162 356 246 20 172 4 421 392 386 77 267 357 20 57 20 279 3 17 ...
result:
wrong answer 1st lines differ - expected: '94', found: '100'