QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#4521#425. 字符串Qingyu100 ✓1553ms95728kbC++116.9kb2020-06-27 17:31:122021-12-19 05:21:43

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-12-19 05:21:43]
  • Judged
  • Verdict: 100
  • Time: 1553ms
  • Memory: 95728kb
Show
  • [2020-06-27 17:31:12]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int N = 2e5 + 5;
int lo[N];
int n, q, l, r, i, j, ans[N];
char c[N];
struct SA {
    char c[N];
    int sa[N], rk[N], h[N], f[20][N];
    inline void build() {
        static int buc[N], a[N], b[N], rk1[N], rk2[N];
        int p, d, i, j;
        for (i = 1; i <= n; ++i) rk[i] = c[i] == 'a' ? 1 : 2;
        p = 2;
        for (d = 0; 1 << d <= n; ++d) {
            for (i = 1; i <= n; ++i) rk1[i] = rk[i], rk2[i] = i + (1 << d) <= n ? rk[i + (1 << d)] : 0;
            memset(buc, 0, p + 1 << 2);
            for (i = 1; i <= n; ++i) ++buc[rk2[i]];
            for (i = 1; i <= p; ++i) buc[i] += buc[i - 1];
            for (i = 1; i <= n; ++i) a[buc[rk2[i]]--] = i;
            memset(buc, 0, p + 1 << 2);
            for (i = 1; i <= n; ++i) ++buc[rk1[i]];
            for (i = 1; i <= p; ++i) buc[i] += buc[i - 1];
            for (i = n; i; --i) b[buc[rk1[a[i]]]--] = a[i];
            p = 0;
            for (i = 1; i <= n; ++i) rk[b[i]] = p += rk1[b[i]] > rk1[b[i - 1]] || rk2[b[i]] > rk2[b[i - 1]];
        }
        for (i = 1; i <= n; ++i) sa[rk[i]] = i;
        for (i = 1, j = 0; i <= n; ++i) {
            if (rk[i] == n) {
                j = 0;
                continue;
            }
            for (j ? --j : 0; i + j <= n && c[i + j] == c[sa[rk[i] + 1] + j]; ++j)
                ;
            h[rk[i]] = j;
        }
        memcpy(f[0] + 1, h + 1, n << 2);
        for (i = 1; 1 << i <= n; ++i)
            for (j = 1; j + (1 << i) - 1 <= n; ++j) f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
    }
    inline int lcp(int x, int y) {  // x!=y
        if (x == y)
            return n - x + 1;
        x = rk[x];
        y = rk[y];
        if (x > y)
            swap(x, y);
        int l = lo[y - x];
        return min(f[l][x], f[l][y - (1 << l)]);
    }
} A, B;
struct atom {
    int u, d, la, l;
};
inline bool cmp(const atom& a, const atom& b) { return a.l < b.l; }
vector<atom> ve1[N], ve2[N];
set<int> se[N];
struct str {
    int l, r;
    inline bool operator<(const str& rhs) const {
        int a = A.lcp(l, rhs.l), l1 = r - l + 1, l2 = rhs.r - rhs.l + 1;
        return a < min(l1, l2) ? c[l + a] < c[rhs.l + a] : l1 < l2;
    }
};
map<str, int> mp;
int scnt;
namespace Q1 {
inline void tryins(int l, int r) {
    if (c[l] != c[r])
        return;
    int x = B.lcp(n - l + 1, n - r + 1), y = A.lcp(l, r), d = r - l, i;
    l -= x - 1;
    r += y - 1;
    if (r - l + 1 < d * 2 || se[l].count(r))
        return;
    se[l].insert(r);
    int lm = min(d, r - l + 1 - d * 2 + 1);
    for (int i = 0; i < lm; ++i) {
        int& u = mp[(str){ l + i, l + i + d - 1 }];
        u = max(u, (r - (l + i) + 1) / d);
    }
}
inline void work(int o) {
    static int st[N];
    int w = 0;
    for (i = n; i; --i) {
        for (; w && (A.rk[i] < A.rk[st[w]]) == o; --w)
            ;
        if (w)
            tryins(i, st[w]);
        st[++w] = i;
    }
}
inline void main() {
    cin >> l >> r;
    memmove(c + 1, c + l, r - l + 1);
    n = r - l + 1;
    c[n + 1] = 0;
    memcpy(A.c + 1, c + 1, n);
    A.build();
    reverse(c + 1, c + n + 1);
    memcpy(B.c + 1, c + 1, n);
    B.build();
    reverse(c + 1, c + n + 1);
    work(0);
    work(1);
    int ans = 0;
    for (map<str, int>::iterator it = mp.begin(); it != mp.end(); ++it) ans += it->second >> 1;
    cout << ans << endl;
}
}  // namespace Q1
inline void tryins(int l, int r) {
    if (c[l] != c[r])
        return;
    int x = B.lcp(n - l + 1, n - r + 1), y = A.lcp(l, r), d = r - l, i;
    l -= x - 1;
    r += y - 1;
    if (r - l + 1 < d * 2 || se[l].count(r))
        return;
    se[l].insert(r);
    static int a[N];
    int lm = min(d, r - l + 1 - d * 2 + 1);
    for (i = 0; i < lm; ++i) {
        str u = (str){ l + i, l + i + d - 1 };
        if (!mp.count(u))
            mp[u] = ++scnt;
        a[i] = mp[u];
    }
    for (i = d * 2; i <= r - l + 1; ++i) ve1[l + i - 1].push_back((atom){ a[i % d], d, i / d, i / d * d });
    for (i = 0; i < lm; ++i) {
        str u = (str){ r - i - d + 1, r - i };
        if (!mp.count(u))
            mp[u] = ++scnt;
        a[i] = mp[u];
    }
    for (i = d * 2; i <= r - l + 1; ++i) ve2[r - i + 1].push_back((atom){ a[i % d], d, i / d, i / d * d });
}
inline void work(int o) {
    static int st[N];
    int w = 0;
    for (i = n; i; --i) {
        for (; w && (A.rk[i] < A.rk[st[w]]) == o; --w)
            ;
        if (w)
            tryins(i, st[w]);
        st[++w] = i;
    }
}
namespace DS {
const int U = 3e6;
int a[U], bel[N], B, j, k, l, st1[N], st2[N], ow, w, oass, ass, ql[N];
vector<P> qu[N];
inline void ins(int l, int r, int rr) {
    ow = w;
    oass = ass;
    for (int j = r; j >= l; --j)
        for (int k = 0; k < ve2[j].size() && j + ve2[j][k].d * 2 - 1 <= rr; ++k) {
            st1[++w] = ve2[j][k].u;
            st2[w] = a[st1[w]];
            ass -= a[st1[w]] >> 1;
            a[st1[w]] = max(a[st1[w]], min((rr - j + 1) / ve2[j][k].d, ve2[j][k].la));
            ass += a[st1[w]] >> 1;
        }
}
inline void goback() {
    for (; w > ow;) a[st1[w]] = st2[w], --w;
    ass = oass;
}
inline void main() {
    B = sqrt(n * 0.7);
    B = min(max(B, 1), n);
    for (i = 1; i <= n; ++i) bel[i] = (i - 1) / B + 1;
    for (i = 1; i <= q; ++i) {
        scanf("%d%d", &l, &r);
        ql[i] = l;
        if (bel[l] == bel[r]) {
            ins(l, r, r);
            ans[i] = ass;
            goback();
        } else
            qu[bel[l]].push_back(P(r, i));
    }
    for (i = 1; i < bel[n]; ++i) {
        sort(qu[i].begin(), qu[i].end());
        ass = 0;
        memset(a + 1, 0, scnt << 2);
        int L = i * B;
        for (j = 0, k = L; j < qu[i].size(); ++j) {
            for (; k < qu[i][j].first;) {
                ++k;
                for (l = 0; l < ve1[k].size() && k - ve1[k][l].d * 2 + 1 > L; ++l) {
                    ass -= a[ve1[k][l].u] >> 1;
                    a[ve1[k][l].u] = max(a[ve1[k][l].u], min((k - L + 1) / ve1[k][l].d, ve1[k][l].la));
                    ass += a[ve1[k][l].u] >> 1;
                }
            }
            ins(ql[qu[i][j].second], L, qu[i][j].first);
            ans[qu[i][j].second] = ass;
            goback();
        }
    }
    for (i = 1; i <= q; ++i) printf("%d\n", ans[i]);
}
}  // namespace DS
int main() {
    for (i = 2; i < N; ++i) lo[i] = lo[i >> 1] + 1;
    scanf("%d%d%s", &n, &q, c + 1);
    if (q == 1) {
        Q1::main();
        return 0;
    }
    memcpy(A.c + 1, c + 1, n);
    A.build();
    reverse(c + 1, c + n + 1);
    memcpy(B.c + 1, c + 1, n);
    B.build();
    reverse(c + 1, c + n + 1);
    work(0);
    work(1);
    for (i = 1; i <= n; ++i) {
        sort(ve1[i].begin(), ve1[i].end(), cmp);
        sort(ve2[i].begin(), ve2[i].end(), cmp);
    }
    DS::main();
}
源文件, 语言: C++11

詳細信息

Test #1:

score: 10
Accepted
time: 59ms
memory: 35344kb

input:

100 200000
bbababbaaabaaabbbabbabbabbabbaabbbabbabbabbabbaabbbabbabbabbabbaabbbabbabbabbabbaabbbabbabbabbabbbab
1 100
31 92
11 60
30 41
41 57
15 88
12 91
65 86
13 38
35 38
7 86
2 96
8 57
41 43
24 38
2 6
79 84
3 71
15 53
69 69
32 44
67 99
52 66
21 80
17 25
72 72
25 72
60 64
6 15
21 70
14 15
50 71
14 71
47 58
64 93
46 84
55 89
4 96
73 91
14 39
31 92
53 64
7 22
10 26
22 98
61 83
3 22
37 67
16 74
15 90
37 70
21 68
78 88
17 19
82 91
73 91
43 96
53 55
14 89
27 44
45 69
51 52
93 100
66 96
31 90
19 61
3...

output:

47
25
23
5
5
32
37
8
8
1
34
46
21
1
4
2
2
28
14
0
5
8
7
25
4
0
23
1
4
25
0
8
25
5
8
14
10
44
5
8
25
5
6
5
34
8
7
8
25
34
9
23
2
0
4
5
25
1
34
6
8
0
2
8
25
18
25
2
3
8
25
1
2
6
21
3
1
27
10
3
22
23
12
27
8
7
25
15
25
8
37
3
8
27
4
8
5
25
3
25
25
5
25
17
9
8
7
44
30
1
19
25
3
3
37
28
5
25
8
1
15
5
8
13
9
16
31
14
8
8
17
25
3
41
0
34
2
8
1
15
25
5
8
6
0
7
1
18
22
2
29
5
32
8
1
8
8
25
8
9
8
0
22
21
20
4
5
4
7
8
4
9
5
6
20
25
8
10
8
40
25
25
8
12
13
25
12
9
6
16
25
4
25
20
8
1
27
2
1
4
3
5
5
25
10
4
...

result:

ok 200000 numbers

Test #2:

score: 10
Accepted
time: 73ms
memory: 35780kb

input:

500 200000
abaabaaaabaabaaaabaabaaaabaabaaaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabbaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabababababaaaabababababaaaabababababaaaabababababaaaabababababaaaababababa...

output:

267
228
46
31
74
26
38
92
30
15
135
108
10
195
86
129
128
181
41
1
61
31
196
43
217
60
66
52
134
189
113
14
129
101
140
44
65
89
0
148
93
23
99
177
253
27
60
106
227
123
63
36
96
49
57
17
210
148
167
37
203
177
165
208
193
241
76
3
28
35
163
228
9
6
208
73
21
184
97
33
98
10
190
109
4
42
229
31
87
186
108
70
30
135
136
134
85
112
41
2
154
163
66
89
36
45
109
73
94
45
101
5
2
3
37
55
31
47
33
0
161
219
84
125
188
110
82
109
14
105
204
60
19
17
179
130
68
126
19
160
169
2
58
190
120
4
40
0
221
250...

result:

ok 200000 numbers

Test #3:

score: 10
Accepted
time: 130ms
memory: 37808kb

input:

5000 200000
babbbabaaabbaaabababbabaaabbaaabababbabaaabbaaabababbabaaabbaaabababbabaaabbaaabababbabaaabbaaababaababbabaaabbaaababaababbabaaabbaaababaababbabaaabbaaababaababbabaaabbaaababaabbabaaabbaaabababbabaaabbaaabababbabaaabbaaabababbabaaabbaaabababbabaaabbaaababaababbabaaabbaaababaababbabaaabbaaababaababbabaaabbaaababaababbabaaabbaaababaababbabaaabbaaababaababbabaaabbaaababaabbabaaabbaaabababbabaaabbaaababaaaabbababababababababababababaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaaaaaa...

output:

1579
690
292
449
478
532
547
582
1274
1002
458
680
344
1439
1220
602
319
268
1421
1230
1367
1325
798
490
757
361
440
719
572
727
628
221
645
228
418
1390
311
802
662
1003
712
388
954
1022
157
99
44
607
825
583
279
4
227
1285
347
983
514
418
1526
533
499
334
1049
976
1260
79
1071
139
739
940
482
117
136
22
512
917
229
27
320
688
312
816
959
941
834
156
347
694
1070
576
293
418
287
123
552
521
659
767
178
264
120
790
715
613
357
487
24
1047
270
1116
702
442
345
421
860
815
115
446
180
845
939
394
...

result:

ok 200000 numbers

Test #4:

score: 10
Accepted
time: 120ms
memory: 37656kb

input:

5000 200000
babbbaaabaaababbbbbaaaababbababbababaaaabbbbbaaababaaababbbbbaaaababbababbababaaaabbbbbaaababaaababbbbbaaaababbababbababaaaabbbbbaaababaaababbbbbaaaababbababababbababaaaabbbbbaaababaaababbbbbaaaababbababababbababaaaabbbbbaaababaaababbbbbaaaababbababababbababaaaabbbbbaaababaaababbbbbaaaababbababababbababaaaabbbbbaaababaaababbbbbaaaababbababababbababaaaabbbbbaaababaaababbbbbaaaababbababababbababaaaabbbbbaaababaaababbbbbaaaababbababababbababaaaabbbbbaaababaaababbbbbaaaababbababababbabab...

output:

2259
9
2113
60
603
1764
1553
270
1645
1302
893
673
49
1197
684
1855
149
229
703
572
566
121
426
1989
1511
1177
1595
450
422
698
2080
106
1104
780
102
1294
121
141
377
551
351
233
337
1295
382
1343
290
494
429
312
534
270
807
965
474
796
698
1083
1477
597
547
44
189
754
290
1314
290
2022
657
2094
326
718
380
1055
700
1574
1526
421
153
9
594
755
1218
817
678
205
198
610
1054
728
11
1163
1182
541
290
2209
1144
262
290
417
272
1996
136
767
684
428
1020
987
1170
879
1184
846
127
619
525
1209
1664
121...

result:

ok 200000 numbers

Test #5:

score: 10
Accepted
time: 1519ms
memory: 92828kb

input:

200000 200000
baababbbbbbbbbbabaaababbaabbabaaaabbaabbbbabaaaabbabbbababaaaabbaabbabaaaabbaabbbbabaaaabbabbbababaaaabbaabbabaaaabbaabbbbabaaaabbabbbababaaaabbaabbabaaaabbaabbbbabaaaabbabbbababaaaabbaabbabaaaabbaabbaabbabbbababaaaabbaabbabaaaabbaabbbbabaaaabbabbbababaaaabbaabbabaaaabbaabbaabbabbbababaaaabbaabbabaaaabbaabbbbabaaaabbabbbababaaaabbaabbabaaaabbaabbaabbabbbababaaaabbaabbabaaaabbaabbbbabaaaabbabbbababaaaabbaabbabaaaabbaabbaabbabbbababaaaabbaabbabaaaabbaabbbbabaaaabbabbbababaaaabbaabbab...

output:

68438
45123
38818
46365
13546
7147
10377
8922
3951
44132
6410
1388
20906
690
50086
4631
18933
18822
22669
44608
28391
11295
31315
6168
31068
20692
6147
18695
1300
27271
13267
21249
5588
9160
3260
42369
37012
31726
10824
34540
3201
5039
17901
8422
9614
1648
19325
17163
11452
16870
43045
12248
36786
49719
21489
66085
26936
1573
3376
1286
44102
24497
34590
14596
42452
1334
46936
10160
6724
350
1728
16920
48003
28168
24622
42457
6982
28078
28265
24944
3774
3665
11036
11231
7959
46503
40457
32429
650...

result:

ok 200000 numbers

Test #6:

score: 10
Accepted
time: 1553ms
memory: 94988kb

input:

200000 200000
baababaaabbaabbbababaaaaabaababbaabaabaaaaabbabbabbbaaabbaaabbbaabbbaabaabbbbbaabbbaababbbbaababababbbbabbbaababaaaabaabbaabbbaaabababbbbaabbabbbbaabbaaabbaaaaaabbaaaaabababbbabbbbbabbbbbaaabbaaaaaabbaaaaabababbbabbbbbabbbbbaaabbaaaaaabbaaaaabababbbabbbbbabbbbbaaabbaaaaaabbaaaaabababbbabbbbbabbbbbaaabbaaaaaabbaaaaabababbbabbbbbabbbbbaaabbaaaaaabbaaaaabababbbabbbbbabbbbbaaabbaaaaaabbaaaaabababbbabbbbbabbbbbaaabbaaaaaabbaaaaabababbbabbbbbabbbbbaaabbaaaaaabbaaaaabababbbabbbbbaabbbabbb...

output:

70193
7004
8538
42161
1855
28580
24923
890
39782
19352
17348
3974
14491
24655
44433
22996
24218
41097
12977
32753
6653
34188
6674
1767
8825
65609
85
42728
25542
22940
27115
109
3784
24492
6973
53193
23009
56985
3448
11437
5675
26682
35093
22606
39244
19566
4696
30120
17531
6286
16215
24996
2099
19129
9284
3984
20803
35404
48259
16595
5896
45442
13742
42738
41686
8171
7333
22829
5618
57101
52069
1136
60945
5380
36815
22908
31309
16329
32502
864
29965
31178
25360
42376
4108
15080
6842
542
7152
293...

result:

ok 200000 numbers

Test #7:

score: 10
Accepted
time: 124ms
memory: 71828kb

input:

200000 1
abbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabbabbbabba...

output:

65357

result:

ok 1 number(s): "65357"

Test #8:

score: 10
Accepted
time: 126ms
memory: 70700kb

input:

200000 1
bbbbabaaaaaaababaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbabbbbaaababbbabbababbabbababbabaaabbab...

output:

88892

result:

ok 1 number(s): "88892"

Test #9:

score: 10
Accepted
time: 1542ms
memory: 95728kb

input:

200000 200000
baaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaabaabaaaab...

output:

73785
32397
41165
57
1621
4203
37482
23378
32545
3939
35181
62614
45311
10259
11291
51918
22732
3668
14909
60680
7115
34968
38922
32616
5418
35960
753
5140
23344
31347
51370
20038
27617
30578
18007
63194
5988
59129
8938
41905
14063
60795
40109
37902
46923
60291
22587
37489
56793
29063
42704
14139
8295
58220
29148
27381
12925
18236
1682
12842
36194
16990
10531
13246
19544
4705
57981
31265
520
11051
57725
10602
57361
22722
1734
8939
7943
39282
29941
26495
45647
60281
43777
38306
17456
56793
25420
...

result:

ok 200000 numbers

Test #10:

score: 10
Accepted
time: 1349ms
memory: 95016kb

input:

200000 200000
aabaabbbbabbbabbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbabbaabbababbbabaaaaaabbbab...

output:

90104
36717
44578
16853
6315
27987
42287
63321
15030
76239
29268
67038
24748
326
1693
12333
19290
1950
15891
85493
12053
40517
9213
3333
54430
36751
6448
15811
62510
25453
20811
24477
27918
42397
23486
36671
45747
13253
2573
5007
10519
21013
21557
1373
16766
39902
4386
22371
38472
21513
45747
71823
10558
7253
24647
71626
46267
22824
34716
5232
32488
51476
4230
1293
71356
23085
58830
39753
58798
38483
12212
45669
72116
75550
8865
45479
5890
15530
32413
86438
44015
5413
24771
3293
4950
14110
25605...

result:

ok 200000 numbers
English 繁體中文 简体中文

伺服器時間: 2025-02-08 16:27:48 | 開源專案