QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#718561#9406. TriangleforgotmyhandleTL 991ms115864kbC++148.7kb2024-11-06 20:51:302024-11-06 20:51:37

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 20:51:37]
  • 评测
  • 测评结果:TL
  • 用时:991ms
  • 内存:115864kb
  • [2024-11-06 20:51:30]
  • 提交

answer

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <string.h>
#include <cassert>
#include <random>
#include <map>
#define lowbit(x) ((x) & (-(x)))
#define int long long
using namespace std;
const int B = 13331;
const int P = 1000000007;
int n, m;
string str[300005], s[300005];
int sa[600005], rk[600005], ht[600005];
pair<int, int> mn[20][600005];
int lg2[600005];
namespace SA {
    int c[600005], x[600005], y[600005];
    int t[600005];
    void SA(string str, int n, int m) {
        for (int i = 0; i <= m; i++) c[i] = 0;
        for (int i = 1, sep = 255; i <= n; i++) c[x[i] = t[i] = (str[i] == '/' ? ++sep : str[i])]++;
        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 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;
            }
            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;
            swap(x, y);
            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;
        }
        t[n + 1] = -1;
        for (int i = 1; i <= n; i++) rk[sa[i]] = i;
        for (int i = 1, k = 0; i <= n; i++) {
            k -= (k != 0);
            while (t[i + k] == t[sa[rk[i] - 1] + k]) ++k;
            ht[rk[i]] = k;
        }
        lg2[0] = -1;
        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))]);
        }
    }
}
int bg[300005], fdsa[300005];
int len[300005], o[300005], cnt[300005];
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 = 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[300005], pre[300005];
int val[300005];
struct qquery {
    int x, l, r, v;
} qs[300005];
int qcnt;
struct BIT {
    int bit[300005];
    inline void add(int x, int y) { for (; x <= 300000; 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 rstr() {
    int s = 2;
    string ret;
    for (int i = 0; i < s; i++) ret += mtrand() % 26 + 'a';
    return ret;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tc;
    cin >> tc;
    while (tc--) {
        mp.clear();
        string S = " ";
        // n = 150000;
        // for (int i = 1; i <= n; i++) str[o[i] = i] = rstr(), 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 = i + 1; j <= n; j++) {
        //         for (int k = j + 1; k <= n; 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";
        SA::SA(S, (int)S.size() - 1, n + 300);
        // 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); });
        // 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++) {
                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]] };
                }

                val[j] = i, l = app[j] + 1, r = i - 1;
                while (l <= r) {
                    mid = (l + r) >> 1;
                    if (cmp(i, mid, len[app[j]] + 1)) 
                        val[j] = mid, r = mid - 1;
                    else 
                        l = mid + 1;
                }
                // cout << val[j] << "\n";
                qs[++qcnt] = (qquery) { val[j], app[j], -1, cnt[app[j]] };
                tmp += (pre[i - 1] - pre[val[j] - 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";
        //     assert(0);
        // }
    }
    return 0;
}
/*
2
10
a
a
bbabbba
bbabb
babaaba
bb
babbaaa
bab
b
aaaba

9
a
bbabbba
bbabb
babaaba
bb
babbaaa
bab
b
aaaba
*/

詳細信息

Test #1:

score: 100
Accepted
time: 7ms
memory: 72916kb

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: 21ms
memory: 78944kb

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: 19ms
memory: 81280kb

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: 89704kb

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: 12ms
memory: 92004kb

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: 991ms
memory: 115864kb

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: 983ms
memory: 108160kb

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: 957ms
memory: 106804kb

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: 963ms
memory: 109892kb

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: -100
Time Limit Exceeded

input:

1003
3
mpfowyd
mpfowydrivrkjiarwcxwbfqvnktlzcfolbbsgelvcnzeqy
hytzojmfeiwtpquxhneeznbdjjlsptedaorwfsxi
3
nyfcq
nyfcqgrmshiwmgcbukozvetdggebkkychamof
nyfcqgrmshiwmgcbukozvetdggebkkychamofadozdympuejvhdnpi
8
yoeqyfcjsywowdrlzzybjvtycqvizzomc
zci
yoeqyfc
zcinc
yoeqyfcjsywowdrlzzybjvtycqvizzomc
y
zcinc
...

output:


result: