QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#698883 | #7901. Basic Substring Structure | Deltax | WA | 23ms | 118604kb | C++14 | 4.5kb | 2024-11-01 22:54:06 | 2024-11-01 22:54:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;
typedef long long LL;
inline int read() {
int x = 0, f = 0;
char c = getchar();
while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f? -x : x;
}
const int MAXN = 2e5;
namespace ST {
const int MAXST = MAXN*2;
template <class T1>
struct ST {
T1 mn[21][MAXST];
void build(T1 *a, int n) {
for (int i = 1; i <= n; ++i) mn[0][i] = a[i - 1];
for (int j = 1; j <= 20; ++j)
for (int i = 1; i + (1 << j - 1) <= n; ++i)
mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << j - 1)]);
}
T1 query(int l, int r) {
int k = 31 - __builtin_clz(r - l + 1);
return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
};
}
namespace SAM {
const int MAXS = MAXN*2;
struct SAM {
vector <int> G[MAXS];
// int ch[MAXS][28];
map <int, int> ch[MAXS];
int len[MAXS], siz[MAXS], fa[MAXS], last, tot;
int extend(int c) {
int np = ++tot, p = last; last = np;
len[np] = len[p] + 1; siz[np] = 1;
for (; p && ch[p].find(c) == ch[p].end(); p = fa[p]) ch[p][c] = np;
if (ch[p].find(c) == ch[p].end()) {
ch[p][c] = np;
fa[np] = p;
return np;
}
int q = ch[p][c];
if (len[q] > len[p] + 1) {
int nq = ++tot; len[nq] = len[p] + 1; fa[nq] = fa[q];
//for (int i = 0; i < 26; ++i) ch[nq][i] = ch[q][i];
ch[nq] = ch[q];
fa[np] = fa[q] = nq;
for (; ch[p].find(c) != ch[p].end() && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
}
else fa[np] = q;
return np;
}
ST :: ST<pii> st;
int dfn[MAXS], tt;
void dfs(int x, int dep) {
dfn[x] = ++tt;
for (auto v : G[x]) {
dfs(v, dep + 1);
siz[x] += siz[v];
}
}
pii a_[MAXS];
void build() {
for (int i = 1; i <= tot; ++i)
G[fa[i]].pb(i);
dfs(0, 0);
for (int i = 0; i <= tot; ++i) a_[dfn[i]] = mkp(dfn[fa[i]], fa[i]);
st.build(a_ + 1, tot + 1);
}
void clear() {
// st.clear();
for (int i = 0; i <= tot + 1; ++i) {
//memset(ch[i], 0, sizeof(ch[i]));
ch[i].clear();
len[i] = siz[i] = fa[i] = 0;
G[i].clear();
}
tt = last = tot = 0;
}
int LCA(int x, int y) {
if (x == y) return x;
if (dfn[x] > dfn[y]) swap(x, y);
return st.query(dfn[x] + 1, dfn[y]).se;
}
inline int LCP(int x, int y) {return len[LCA(x, y)];} //front
};
}
SAM :: SAM s1;
int pos[MAXN + 10], s[MAXN + 10], len[MAXN + 10];
unordered_map <int, int> mp;
map <int, LL> exc[MAXN + 10];
vector <int> vec[MAXN + 10];
LL c1[MAXN + 10], v1[MAXN + 10], res[MAXN + 10], ans[MAXN + 10];
int main() {
int T = read();
while (T--) {
int n = read();
for (int i = 1; i <= n; ++i) s[i] = read();
for (int i = n; i >= 1; --i) {
pos[i] = s1.extend(s[i]);
}
s1.build();
LL ans = 0, sum = 0, cnt = 0;
for (int i = 2; i <= n; ++i) {
len[i] = s1.LCP(pos[1], pos[i]);
ans += len[i];
c1[1]++;
c1[min(len[i] + 1, i)]--;
res[1] -= len[i];
res[min(len[i] + 1, i)] += len[i];
c1[i]++;
c1[i + len[i]]--;
v1[i] -= i - 1;
v1[i + len[i]] += i - 1;
res[i] -= len[i];
res[len[i] + i] += len[i];
//vec[i + len[i]].pb(i);
int l1 = s1.LCP(pos[i + len[i] + 1], pos[1 + len[i] + 1]) + 1;
// cerr << l1 << " ";
if (1 + len[i] < i)
exc[1 + len[i]][s[i + len[i]]] += l1;
if (l1 + len[i] >= i + len[i]) {
//l1 + len[i] -> i + len[i];
l1 = i - 1;
}
else {
int tmp = s[i + len[i]]; s[i + len[i]] = s[1 + len[i]];
if (l1 + len[i] == i + len[i] - 1 && s[1 + l1 + len[i]] == s[i + len[i] + l1]) {
l1 += 1 + s1.LCP(pos[l1 + len[i] + 2], pos[i + len[i] + l1 + 1]);
}
s[i + len[i]] = tmp;
}
// cerr << l1 << endl;
exc[i + len[i]][s[1 + len[i]]] += l1;
/*
if (i + len[i] == 5) {
cerr << "sss";
}*/
/*
if (i + len[i] == 4 && s[1 + len[i]] == 1) {
cout << i << " " << l1 << endl;
}*/
}
// cerr << ans << endl;
LL rnm = 0; ans += n;
for (int i = 1; i <= n; ++i) {
sum += res[i];
cnt += c1[i];
sum += v1[i];
LL mx = 0;
for (auto v : exc[i])
mx = max(mx, v.se);
::ans[i] = mx + ans + sum + cnt * (i - 1);
// cerr << ::ans[i] << " ";
rnm += ::ans[i] ^ i;
}
// cerr << endl;
// cerr << endl;
printf("%lld\n", rnm);
for (int i = 1; i <= n + 1; ++i) {
exc[i].clear();
c1[i] = v1[i] = res[i] = 0;
}
s1.clear();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 118340kb
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: 23ms
memory: 118604kb
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 354 3 209 9 262 359 278 21 93 112 58 348 233 3 335 364 377 316 3 19 132 64 13 94 36 261 10 77 34 91 85 101 254 191 21 48 303 64 100 20 24 68 316 362 294 313 353 281 328 281 231 312 3 334 59 326 6 73 32 147 334 40 345 105 242 3 165 346 245 20 177 3 404 393 392 82 273 360 20 59 21 273 6 18 351 ...
result:
wrong answer 3rd lines differ - expected: '347', found: '354'