QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719210 | #9406. Triangle | forgotmyhandle | WA | 604ms | 423944kb | C++14 | 10.8kb | 2024-11-06 23:20:52 | 2024-11-06 23:20:55 |
Judging History
answer
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <string.h>
#include <cassert>
#include <random>
#include <time.h>
#include <map>
#define lowbit(x) ((x) & (-(x)))
#define int long long
using namespace std;
const int B = 2333;
const int P = 1000000007;
int tsa;
int n, m;
string str[3000005], s[3000005];
int sa[1000005], rk[1000005], ht[1000005];
pair<int, int> mn[20][1000005];
int lg2[1000005];
namespace SA {
int X[1000005], Y[1000005];
// int c[600005], x[600005], y[600005];
int c[1000005], *x = X, *y = Y;
void SA(string str, int n) {
// memset(x, 0, sizeof x);
// memset(y, 0, sizeof y);
int m = 50;
for (int i = 0; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[x[i] = str[i] - 'a' + 1]++;
for (int i = 1; i <= m; i++) c[i] += c[i - 1];
for (int i = 1; i <= n; i++) sa[c[x[i]]--] = i;
// for (int i = 1; i <= n; i++) cout << sa[i] << " ";
// cout << "\n";
// for (int i = 1; i <= n; i++) cout << x[i] << " ";
// cout << "\n";
for (int d = 1; d <= n; d <<= 1) {
int tmp = 0;
for (int i = n - d + 1; i <= n; i++) y[++tmp] = i;
for (int i = 1; i <= n; i++) {
if (sa[i] > d)
y[++tmp] = sa[i] - d;
}
// cout << "x : ";
// for (int i = 1; i <= n; i++) cout << x[i] << " ";
// cout << "\n";
// cout << "y : ";
// for (int i = 1; i <= n; i++) cout << y[i] << " ";
// cout << "\n";
// cout << "sa : ";
// for (int i = 1; i <= n; i++) cout << sa[i] << " ";
// cout << "\n";
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;
// int ttt = clock();
swap(x, y);
// tsa += clock() - ttt;
x[sa[1]] = tmp = 1;
for (int i = 2; i <= n; i++)
x[sa[i]] = (tmp += (y[sa[i]] != y[sa[i - 1]] || y[sa[i] + d] != y[sa[i - 1] + d]));
m = tmp;
if (tmp == n)
break;
}
// for (int i = 1; i <= n; i++) cout << sa[i] << " ";
// cout << "\n";
str += '!';
for (int i = 1; i <= n; i++) rk[sa[i]] = i;
// cout << str << "\n";
for (int i = 1, k = 0; i <= n; i++) {
k -= (k != 0);
while (str[i + k] == str[sa[rk[i] - 1] + k]) ++k;
ht[rk[i]] = k;
}
lg2[0] = -1;
// for (int i = 1; i <= n; i++) cout << ht[i] << " ";
// cout << "\n";
for (int i = 1; i <= n; i++) mn[0][i] = make_pair(ht[i], i), lg2[i] = lg2[i - 1] + ((i & (i - 1)) == 0);
for (int i = 1; (1 << i) <= n; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++)
mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
}
for (int i = 0; i <= n + 1; i++) x[i] = y[i] = sa[i] = ht[i] = 0;
// exit(0);
}
}
int bg[3000005], fdsa[3000005];
int len[3000005], o[3000005], cnt[3000005];
inline pair<int, int> Query(int l, int r) {
// assert(l <= r);
int k = lg2[r - l + 1];
return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
inline int lcp(int x, int y) { return Query(min(rk[x], rk[y]) + 1, max(rk[x], rk[y])).first; }
// lcp of str[x]'s p suffix and str[y]'s q suffix
inline int LCP(int x, int y, int p = 1, int q = 1) { return lcp(bg[x] + p - 1, bg[y] + q - 1); }
// return whether (str[x]'s p suffix) is lexicographically strictly smaller than (str[y]'s q suffix)
bool cmp(int x, int y, int p = 1, int q = 1) {
int a = min(min(len[x] - p + 1, len[y] - q + 1), LCP(x, y, p, q));
// cerr << x << " " << y << " " << a << " " << len[x] << " " << len[y] << "\n";
assert(p + a - 1 <= len[x] && q + a - 1 <= len[y]);
if (p + a > len[x] && q + a > len[y])
return 0;
if (p + a > len[x])
return 1;
if (q + a > len[y])
return 0;
return str[x][p + a] < str[y][q + a];
}
unordered_map<int, int> mp;
// map<int, int> mp;
int ans, acnt;
int app[3000005], pre[3000005];
struct qquery {
int x, l, r, v;
} qs[3000005];
int qcnt;
struct BIT {
int bit[3000005];
inline void add(int x, int y) { for (; x <= 500000; x += lowbit(x)) bit[x] += y; }
inline void add(int l, int r, int v) { add(l, v), add(r + 1, -v); }
int query(int x) {
int ret = 0;
for (; x; x -= lowbit(x)) ret += bit[x];
return ret;
}
} bit;
random_device rd;
mt19937 mtrand(rd());
string gen[300005], bas[300005];
int bcnt;
string rstr(int x) {
if (x != 1 && bcnt && mtrand() % 6 != 0) {
int s = mtrand() % bcnt + 1, l = mtrand() % 10 + 1;
string ret = bas[s];
for (int i = 0; i < l; i++) ret += mtrand() % 2 + 'a';
if (mtrand() % 5 == 0)
bas[++bcnt] = ret;
return ret;
} else {
int s = mtrand() % 10 + 2;
string ret;
for (int i = 0; i < s; i++) ret += mtrand() % 2 + 'a';
return bas[++bcnt] = ret;
}
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// int tttt = clock();
int tc;
cin >> tc;
while (tc--) {
// while (1) {
bcnt = 0;
mp.clear();
string S = " ";
// n = 20;
// for (int i = 1; i <= n; i++) str[o[i] = i] = rstr(i), fdsa[i] = bg[i] = S.size(), S += str[i], S += '{', len[i] = str[i].size();
// cout << n << "\n";
// for (int i = 1; i <= n; i++) cout << str[i] << "\n";
cin >> n;
for (int i = 1; i <= n; i++) cin >> str[o[i] = i], fdsa[i] = bg[i] = S.size(), S += str[i], S += '{', len[i] = str[i].size();
int Ans = 0;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j < i; j++) {
// for (int k = 1; k < j; k++) {
// if ((str[i] + str[j] > str[k] || str[j] + str[i] > str[k]) && (str[i] + str[k] > str[j] || str[k] + str[i] > str[j]) && (str[j] + str[k] > str[i] || str[k] + str[j] > str[i])) {
// ++Ans;
// cout << i << " " << j << " " << k << "\n";
// }
// }
// }
// }
// cout << Ans << "\n";
// cout << S << "\n";
// for (int i = 0; i < (int)S.size(); i++) cout << i << " " << S[i] << "\n";
// for (int i = 1; i <= n; i++) cout << bg[i] << " ";
// cout << "\n";
// int ttt = clock();
SA::SA(S, (int)S.size() - 1);
// tsa += clock() - ttt;
// cerr << LCP(3, 2) << "\n";
for (int i = 1; i <= n; i++) s[i] = str[i] = ' ' + str[i];
sort(o + 1, o + n + 1, [](int a, int b) { return cmp(a, b); });
// cout << cmp(2, 1) << " asdf\n";
// return 0;
m = n, n = ans = 0;
for (int i = 1; i <= m; i++) {
if (i == 1 || s[o[i]] != s[o[i - 1]]) {
cnt[++n] = 1;
bg[n] = fdsa[o[i]], str[n] = s[o[i]];
} else
++cnt[n];
}
for (int i = 1; i <= n; i++) len[i] = (int)str[i].size() - 1, pre[i] = pre[i - 1] + cnt[i];
// cout << n << "\n";
// for (int i = 1; i <= n; i++) cout << str[i] << " " << bg[i] << " " << len[i] << " " << cnt[i] << "\n";
// 3 sames
for (int i = 1; i <= n; i++) ans += cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
// 2 sames
for (int i = 1; i <= n; i++) ans += pre[i - 1] * cnt[i] * (cnt[i] - 1) / 2;
// no sames
for (int i = 1, h, tmp; i <= n; i++) {
for (int j = 1 + (tmp = h = acnt = qcnt = 0); j <= len[i]; j++) {
h = (h * B + str[i][j] - 'a' + 1) % P;
if (mp.count(h)) {
app[++acnt] = mp[h];
if (cmp(i, app[acnt], len[app[acnt]] + 1))
tmp += cnt[app[acnt]] * (cnt[app[acnt]] - 1) / 2;
}
}
mp[h] = i;
// cout << i << " " << tmp << " contrib\n";
for (int j = 1; j <= acnt; j++) {
// cout << app[j] << " is pre of " << i << "\n";
int l = 1, r = app[j] - 1, mid, asdf = app[j];
while (l <= r) {
mid = (l + r) >> 1;
if (cmp(i, mid, len[app[j]] + 1))
asdf = mid, r = mid - 1;
else
l = mid + 1;
}
l = asdf, r = app[j] - 1;
// cout << l << " " << r << "\n";
if (l <= r) {
tmp += (pre[r] - pre[l - 1]) * cnt[app[j]];
qs[++qcnt] = (qquery) { app[j], l, r, cnt[app[j]] };
}
int val = i; l = app[j] + 1, r = i - 1;
while (l <= r) {
mid = (l + r) >> 1;
if (cmp(i, mid, len[app[j]] + 1))
val = mid, r = mid - 1;
else
l = mid + 1;
}
// cout << val << "\n";
qs[++qcnt] = (qquery) { val, app[j], -1, cnt[app[j]] };
tmp += (pre[i - 1] - pre[val - 1]) * cnt[app[j]];
}
// cout << i << " " << tmp << " contrib\n";
sort(qs + 1, qs + qcnt + 1, [](qquery a, qquery b) { return (a.x == b.x) ? (a.r < b.r) : (a.x < b.x); });
for (int j = qcnt; j; j--) {
if (qs[j].r != -1)
bit.add(qs[j].l, qs[j].r, qs[j].v);
else
tmp -= qs[j].v * bit.query(qs[j].l);
}
for (int j = 1; j <= qcnt; j++) qs[j].r != -1 ? bit.add(qs[j].l, qs[j].r, -qs[j].v) : void();
ans += tmp * cnt[i];
// cout << i << " " << tmp << " contrib\n";
}
cout << ans << "\n";
// if (ans != Ans) {
// cout << ans << " " << Ans << "\n";
// cout << n << "\n";
// for (int i = 1; i <= n; i++) cout << str[i] << "\n";
// cout << m << "\n";
// for (int i = 1; i <= m; i++) cout << s[i] << "\n";
// assert(0);
// }
for (int i = 0; i <= n * 2; i++) rk[i] = 0;
// if (ans == 2414849253880)
}
// cout << tsa * 1.0 / CLOCKS_PER_SEC << "\n";
// cout << (clock() * 1.0 - tttt) / CLOCKS_PER_SEC << "\n";
return 0;
}
/*
2
10
bbabb
aabba
babba
babbb
a
babaa
bba
aabba
aba
ab
10
b
ba
a
bbb
aaaa
ba
a
aa
bbbba
bba
*/
详细
Test #1:
score: 100
Accepted
time: 31ms
memory: 209872kb
input:
3 6 cbaa cb cb cbaa ba ba 3 sdcpc sd cpc 1 ccpc
output:
16 0 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 23ms
memory: 210344kb
input:
14 1 lfpbavjsm 2 pdtlkfwn mbd 3 dvqksg dvqksg uhbhpyhj 4 ombwb ombwb ombwb ombwb 5 oztclz oztclz oztclz oztclz kul 6 vco vco vco dtktsqtinm vco vco 7 tb tb kowbsu ygkfphcij tb uvei tb 8 vxxtxssht abnsxbf bydaae bydaae udalyvmcef bydaae bydaae bydaae 9 aaze zvyonw qjfv mmhkef qjfv qjfv qjfv mmhkef qj...
output:
0 0 0 4 10 20 10 20 41 14 63 74 18 11081
result:
ok 14 lines
Test #3:
score: 0
Accepted
time: 33ms
memory: 210072kb
input:
11 10 bppzfsncq bppzfsncq vcqxgcehdx bppzfsncq bppzfsncq muwrcvt w aanwhqmync aanwhqmync bppzfsncq 10 t jkky t z t t z z z t 10 qidkyca uhqubvbo kosyvh gsj gsj gsj duo jrro gsj jrro 10 lhktb lhktb lhktb uohl lhktb r lhktb lhktb wruim lhktb 10 e gqvdmpvxb gqvdmpvxb gqvdmpvxb sttirbhz gqvdmpvxb zdfpm ...
output:
30 60 15 35 20 20 23 12 38 44 8047
result:
ok 11 lines
Test #4:
score: 0
Accepted
time: 23ms
memory: 211612kb
input:
11 100 kalgqjh mdszzwe qxn kalgqjh hy kalgqjh suplvp r kkeoxmx tcoise suplvp suplvp y kalgqjh vrwniyici jmnyrradyq kalgqjh kalgqjh suplvp rkg xzevyk zc suplvp hcupv kalgqjh qakyahjaoi mum pbg u ip kalgqjh kalgqjh jngc ylr suplvp qxn kalgqjh bzwodm e kalgqjh kalgqjh evmm kbymvbccs kalgqjh suplvp kalg...
output:
12478 6722 9220 6668 4934 11233 7950 5470 4525 5743 1586066
result:
ok 11 lines
Test #5:
score: 0
Accepted
time: 32ms
memory: 211816kb
input:
2 1000 t lhijhkxzzx nhfiksblww h xg z dcbmbvyz ois ynwjgfp oqzv qtoinl gr teu kmza hs t mwhewk kjmuneon bekku qheweh szhagft fcwjp bobwnap y oqpole oqzv xeaiyhfeg rjkdidea wmeslege vyyi teomn yvmcnw vnvum tgnl swqqruuvc xxllevp bov dse e b rtbhogkx nzs e bs pppyndgrrv n tzbwqdusn e xeaiyhfeg i agnet...
output:
2430570 1904282
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 94ms
memory: 241940kb
input:
503 16 yh yh yhc yhc yhcowdfqlwfidnx yhc yhc yh yhcowdfqlwfidn yhcowdfqlwfidnx yh h yh yhcowdfqlwfidnx yhcowdfqlwfidnx yhc 19 nb nbg vpfkllgv nmzqfsuafqtayjjjcidpygz nb nb gutq n omyuvm fgxtfbhuglxyiumi nbghjuti nbg nb fgxt nbghjuti n nb nbg n 7 rtjiwfidoahckhvgoxvvrncqvgerqiuaruiftakvugsgnsw wllcan...
output:
531 485 6 12 4 118 6 3 1635 18 373 20 954 6208 45 12 1124 79 267 2 5778 22 13 1 1 16 630 0 7 16315 0 2155 2308 26 936 109 103 5 0 2492 7 2 114 144 11 158 0 0 101 455 0 12234 78 631 5402 94 66 84 161 4412 5 3 81 22 20 13 52 632 6 137 56 2 3 64521 122 330 0 0 7 0 113 249 8 301 335 1825 110 4 108 50 10...
result:
ok 503 lines
Test #7:
score: 0
Accepted
time: 74ms
memory: 229844kb
input:
503 23 rjyyivdg n n n n n n n nmr n nmrk nm rjyyivdguyiffnvunoxconw n n n o lixclcmwthwkrsi mqluhyypgfkmdvgpzju n nmrk rjy n 15 jotwxwhaqdxmazhslyouztprzlirisvwvduojb jot jotwxw j jotwx jotwx gohg j gdgneodagmdhvvapjh jotwxw xs vurk vurk j xs 7 xrczucnkbemaymvabkkwnn xrczucnkbemaymvabkkwnn xrczucnkb...
output:
855 58 35 0 1 56 2 112 1 8465 242 56 110 23 544 0 3 17 29 11 764 20 9 0 4 77 812 35 4 10 32 437 9 2364 3 2 11 2 421 50 4 107 1 62 1120 3 1 16 3970 1147 1026 8 4 85 9 31 61 16 205 2 2 84 238 1 1 51 4 0 16 61 331 4 16 7 0 7 148 10 13 2 1 37 1 67 0 296 1 0 644 32 2 10 0 5 126 3490 4 0 10 331 1216 7921 ...
result:
ok 503 lines
Test #8:
score: 0
Accepted
time: 80ms
memory: 229872kb
input:
503 5 ljtolmgjndlwoyjjttak mihjdhkyfnafwrpeuiuiurusvsnu ljtolmgjndlwoyjjttak mihjd ljtolmgjndlwoyjjttak 25 lhx lh lhx lh k lh kninp l lhx lhx izeqohkpfuovopebttqaufmmlivd lhx lhx qid lhx lh lhx lhx oklb l lhx lhx lhx lhx l 9 mxeonfwpujrilfigjoiyjkzdmi fezhyrcyqy mx fezh f dmvfbklnkxmnetib dmvfbkln m...
output:
4 1476 27 26 117970 2 105 30 4 737 4 2 19 48 34 434 6 78331 22 23 0 228 56 4 3 305 9 84 132 199 20 3 4057 0 0 20 35 34 48 4 266 14 17 4788 545 28989 0 10 535 84 1 1775 322 11 57 16 15 1331 5 0 10 5 183 8 2 237 10 0 60 20 42 7 10 297 14 210 6254 7 3 0 13 2744 119 47 0 1 68114 17 1 2 1 7 1 2 113 26 0 ...
result:
ok 503 lines
Test #9:
score: 0
Accepted
time: 76ms
memory: 229452kb
input:
503 11 wkeoqqqpvmgdv w w w wkeoqqqpvmgdv sgrwmsfwclpamgq wkeoqqqpvm qkmbyvcxjsh wkeoqqqpvm wke wkeoqqqpvmgdv 7 otd qelodfwrqeprgyvzbcjljx qe qelodfwrqeprgyvzbcjlj qelodfwrqeprgyvzbcjlj qelodfwrqeprgyvzbcjlj c 15 rce rce fwq fwqqfcjrhqot rceft jkdrcehfwhqkupe fwq r jkdr fwq rceft rce fwqqfcjrhqot fwq...
output:
156 17 213 12 20 1 374 4 0 26 26 3 122 30 4005 24 1385 50 84 44 0 112 42 36 19 887 99 5 9 13 2 5029 52 14 84 116 2 10 4 8 141 9287 822 37 5 13 25 1030 0 2 3 35 81 1 0 1 138 0 578 7 30 636 63 22 2118 863 5377 33 34 10 156 336 1 7 7 4 1793 2 124 13 4 2015 7 23 1 4516 3 17 6 35 13336 9 61 3093 0 1 7 22...
result:
ok 503 lines
Test #10:
score: 0
Accepted
time: 604ms
memory: 423944kb
input:
1003 3 mpfowyd mpfowydrivrkjiarwcxwbfqvnktlzcfolbbsgelvcnzeqy hytzojmfeiwtpquxhneeznbdjjlsptedaorwfsxi 3 nyfcq nyfcqgrmshiwmgcbukozvetdggebkkychamof nyfcqgrmshiwmgcbukozvetdggebkkychamofadozdympuejvhdnpi 8 yoeqyfcjsywowdrlzzybjvtycqvizzomc zci yoeqyfc zcinc yoeqyfcjsywowdrlzzybjvtycqvizzomc y zcinc ...
output:
0 1 26 10 66 403 1 265 1025 16 329 4 1219 1 10 70 30 182 60 5 71 1 20 5343 22328 40667 90 6983 66 10 35 20 250 307 913 98 44 5393 56 280 270 3 3 2229 77 17 774 50 5 21 0 208 8 14 185 35 20 11 465 132 176 10 0 10 1704 13 44 141 0 0 5 10 79 17 213 10 108 0 0 289 10 255 27 493 4 1 24 379 30 9 284 173 2...
result:
ok 1003 lines
Test #11:
score: -100
Wrong Answer
time: 498ms
memory: 346260kb
input:
1003 6 exssl exsslhsuwyemcafatpinzvdeypwjqsnvxlkvmpywgx f exss exs exsslhsuwyemcafatpinzvdeypwjqsnvxlkvmpywgx 7 hzzev hzzevmltbehnvjfhsz hzzevmltbe hzzevmltbehnvjfhszqzobn hzzevmltbehnvjf hm hzzevmltbehnvjfhszqzobn 9 rdx rdxnxdfcyrdpgwzwtqgtu rdx rdxnxdfcyrdpgwzwtqgtu f kpotnxntufvd kpotnxntufvdlmij...
output:
3 19 41 134 107 2 372 0 466 456 20 13 25 339 64 170 1 5 27295 3 1 221 116 11 29 19 1006 16827 16 19863 4 6 5784 3 20 21130 66 1275 100 731 83 3 84 0 32 3 615 207 8 44 245 48 165 18050 128 11 864 21 3 1221 120 51 21 8 247 302 0 1098 0 57 42 20 0 845 1 84 16 4 0 2 836 482 4 12 150 654 1035 142 291 34 ...
result:
wrong answer 1002nd lines differ - expected: '4964466166218', found: '4964466229804'