#2390. 字符串

    ID: 2390 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest472来源:qoj.ac数据:公开样例字符串哈希

字符串

字符串

题目描述

1 字符串 1.1 题目描述 Bob 喜欢字符串。 Bob 觉得,重复两遍的字符串是优美的,例如,aa,sese,abcabc,baabaa,abababab 是优 美的串,而ab,aadead,sesese,abba 不是。更具体地说,如果一个字符串S 能够被写成两个 相同的字符串前后拼接的形式,即存在字符串P 使得S = PP,那么S 就是优美的。 Bob 有一个长度为n 的字符串T = T1T2 · · · Tn。现在他想知道,给定T 的一个子串 Q = T[l · · · r],这个子串Q 内一共包含多少种本质不同的优美的串作为子串。如果两个串相同, 但是出现的位置不同,那么这两个串不是本质不同。 Bob 一共有q 组不同的询问,你需要快速计算出答案。 1.2 输入格式 第一行输入两个整数n, q。第二行输入一个只包含小写字母a 和b 的字符串T。 接下来q 行,每行输入两个整数l, r,表示一组询问。 1.3 输出格式 输出q 行,每行一个整数表示答案。 1.4 样例输入1 11 5 aabaabaaaab 1 11 1 6 7 10 5 5 3 8 1.5 样例输出1 5 2 2 0 2 2

1.6 样例解释1 |T| 有aa,aaaa,abaaba,aabaab,baabaa 这些本质不同的优美的串。 1.7 样例输入输出2 见下发文件 1.8 数据范围与约定 对于前10% 的数据,n ≤100。 对于前20% 的数据,n ≤500。 对于前40% 的数据,n ≤5000。 对于另外20% 的数据,保证T 中所有的优美的串的个数不超过106,这里位置不同的串被 视为不同的。 对于另外20% 的数据,q = 1。 对于100% 的数据,1 ≤n, q ≤200000,1 ≤l ≤r ≤n,T 只包含小写字母a 和b。 3

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

11 5
aabaabaaaab
1 11
1 6
7 10
5 5
3 8
5
2
2
0
2

样例 2

1000 1000
babbaabbbbbbaabababababbabababbaaababbbbbbbaaababbbbbabaabbabbaababbababbbbbbbaabbbabaababbabaabbbbbababbababaababbabaaaabaaaabbaaaaabababaaababbabbbabaabbaaababbaabaabaabaaaabaababbbbbbaaabbbbaabbbabaaaabbabaabaabababbabbabbaabbaaaaaaababbabaaaaaaaabbabababaaaabbbbababbbbabbabbbbaaaabaaaababbbbabaaaababbaabbaabbaaababbabababbaababbbabbbabaabbbaaaaababaaaaaababbabbbbaabbabbaaaabababbababbabbabbaaaabaabbaaabbbaabaaaabbaaabbbaaabbbbbabababbababbbbbbaaaaabaabaabaabaaabbaabbababbabbabbbbabaaabaabaabbabbaabbaabbbabbbaababbbbabaaabbaabbaaabbbbabbaaabbaaabababaaaaabbabbabaaababbababaabbbbbbbaaababbabbaaabababaabbbabbbaaaaababaabababaababaabaaaabababbababaabbbababbbbabbababababbbabbabaaabbbaaaaababbaaabbbbabbbbabaaaaaaaaaababaaaababaabbbbaabbbabaababaabbbaaabbbbabbbbaabbbaaaaaabbbaabbabbbaaababbbaabaaabbaababbabbbbaaaaaabbababbaabaabbbbaaabaabbabaabbbbaabbabaaaaabaaaabbbbabbaabaabaaaabaabbbababbaabbbbbaabbaaabbaabaabbaababababbabaabaabbaaaaabbaabbbbaabababbaabbaaaababaababbbbaaababaabbaaaaabba
475 772
335 541
181 957
229 901
4 984
21 831
209 263
369 896
136 409
244 256
40 869
330 959
102 697
422 918
627 779
148 824
98 759
213 582
234 272
586 604
386 452
395 842
325 528
114 931
355 558
229 338
626 836
287 605
507 971
651 753
370 723
17 999
56 680
721 868
53 510
610 647
435 579
34 719
347 778
303 986
7 967
276 374
684 939
495 992
358 671
278 446
14 830
50 862
127 991
302 941
322 481
282 432
738 985
632 741
32 969
246 794
494 834
276 569
534 735
302 793
265 332
3 970
117 967
119 947
881 903
39 153
89 956
72 629
246 908
506 532
146 501
56 167
83 259
192 246
335 792
158 299
54 917
459 854
335 840
131 521
24 962
121 852
574 937
89 980
300 442
416 484
947 979
162 359
161 914
207 787
83 836
928 973
176 740
17 695
475 838
11 981
9 992
312 954
675 962
177 454
446 601
92 894
286 939
27 874
214 978
101 222
166 168
489 978
188 904
313 780
671 843
250 934
53 994
172 491
568 979
359 989
90 200
51 1000
304 796
234 401
331 785
240 984
70 724
187 828
29 837
64 670
361 653
47 530
140 463
41 847
321 714
20 496
498 671
2 297
173 608
13 964
83 607
4 746
435 964
116 906
63 871
8 947
33 994
705 957
95 717
214 586
57 869
70 705
31 931
408 645
139 878
183 570
64 923
33 821
98 965
202 533
209 530
251 566
851 867
165 725
194 1000
150 958
116 963
127 974
14 765
270 962
924 949
141 917
447 661
349 933
828 939
93 616
45 941
407 593
328 968
592 729
23 915
100 703
164 647
170 619
377 887
336 356
101 954
178 303
1 897
453 934
52 543
418 701
188 207
130 939
258 472
184 927
16 1000
328 813
822 850
527 867
8 990
416 952
271 846
14 975
20 980
436 952
60 778
771 778
20 907
3 990
74 933
223 662
430 453
15 998
344 789
389 432
659 686
156 808
78 255
218 477
200 823
328 329
217 487
233 883
47 935
74 717
190 974
217 941
49 960
90 297
263 728
237 314
56 927
48 815
661 818
112 363
199 736
434 751
557 980
468 738
94 999
334 820
386 521
101 889
127 641
325 762
35 936
342 783
10 970
229 779
302 377
286 597
211 650
38 503
343 368
270 435
663 751
210 744
607 936
235 454
12 992
192 902
280 313
65 969
119 830
533 951
114 201
458 830
397 736
362 950
33 837
148 942
656 831
25 928
540 737
523 526
152 782
676 1000
17 996
28 975
32 986
553 770
175 756
524 968
172 857
320 804
22 337
1 971
168 754
241 367
478 710
299 878
121 652
632 915
316 587
321 969
694 715
215 849
125 817
169 299
54 374
326 977
154 916
17 996
31 845
199 533
425 784
168 496
361 985
92 881
124 855
894 919
26 896
225 799
400 925
48 258
547 604
583 617
230 946
2 753
705 932
2 854
15 146
14 402
298 838
292 739
246 964
317 909
48 965
385 793
561 828
344 887
717 762
512 898
9 827
78 603
99 612
453 539
316 991
648 856
146 582
193 272
164 797
662 715
387 990
205 690
222 472
161 413
692 836
8 638
34 988
13 444
377 846
543 839
500 1000
1 979
157 982
562 989
12 340
457 739
10 903
704 729
111 280
524 990
275 963
334 629
324 873
9 799
852 882
82 376
752 892
337 701
314 522
214 968
78 977
87 655
203 945
321 830
613 884
47 993
652 931
189 831
66 997
699 821
485 839
185 888
125 721
256 707
199 949
884 952
503 969
1 919
628 887
344 826
54 740
90 536
292 675
12 969
720 744
46 814
674 721
68 864
295 768
164 253
716 982
655 916
394 996
73 534
292 832
56 698
92 924
278 499
309 682
231 684
101 966
821 857
390 723
57 968
140 591
418 781
21 842
123 285
538 680
24 980
285 301
309 509
581 781
767 923
260 684
23 996
87 627
55 949
254 956
98 793
190 829
430 511
842 914
543 613
564 945
285 488
63 186
93 744
174 914
394 993
532 842
38 915
509 615
219 539
120 459
489 766
166 580
901 969
395 977
28 963
519 698
679 881
27 970
166 967
501 781
30 881
436 798
599 995
612 851
289 339
523 795
78 942
320 787
376 982
519 582
272 380
112 616
6 889
29 785
24 524
8 578
13 823
839 942
350 560
13 441
243 617
45 427
529 771
250 981
487 591
244 938
415 595
160 775
130 889
191 802
360 735
155 431
6 888
159 265
80 953
222 910
218 385
3 714
219 727
536 741
99 980
153 708
343 638
84 972
99 919
51 987
10 993
294 965
384 902
364 378
374 879
165 952
192 420
6 128
209 984
422 678
167 805
219 834
10 964
457 602
2 737
36 815
172 976
2 851
9 470
175 706
145 709
514 891
76 709
186 581
42 728
43 861
122 887
417 966
81 250
357 983
283 593
206 864
82 898
42 832
148 456
9 970
16 759
94 974
145 484
146 240
399 963
93 292
135 275
279 752
345 629
75 871
138 385
322 966
173 953
25 944
319 587
883 893
70 608
57 942
12 910
680 757
238 624
163 825
66 569
226 927
18 787
129 679
237 625
554 995
766 915
196 646
136 794
701 971
303 494
35 867
394 829
482 748
162 971
524 878
131 362
286 781
890 905
152 963
442 756
4 937
202 956
1 1000
965 988
469 991
760 951
256 261
198 907
192 968
224 844
8 972
424 900
16 958
251 602
553 722
320 753
96 330
593 809
120 836
423 841
360 864
54 676
796 999
336 901
62 924
243 414
32 288
249 755
32 46
277 925
8 918
292 492
330 873
754 871
489 932
25 895
288 366
77 782
297 305
15 825
1 981
485 531
81 527
325 333
404 416
139 147
72 623
103 410
20 739
10 909
281 735
125 752
748 808
136 972
316 523
21 393
63 885
41 775
306 977
52 969
507 986
14 948
12 936
91 681
114 938
883 962
234 914
174 460
147 582
122 855
310 780
229 887
454 625
434 584
191 394
196 968
430 835
631 706
135 766
549 796
447 956
707 788
17 765
565 578
184 744
161 494
378 531
195 481
195 551
343 831
44 754
140 324
21 671
328 934
164 601
497 676
410 592
122 626
322 380
597 970
148 705
41 960
488 534
430 648
34 826
307 462
3 243
100 867
110 635
253 920
208 720
122 633
427 581
341 655
124 734
615 968
338 828
120 308
124 916
737 892
257 975
136 546
319 657
52 920
241 438
250 959
770 873
54 516
67 858
557 951
442 864
129 685
371 920
394 668
388 864
744 980
221 434
41 766
353 961
5 1000
586 596
237 809
658 732
151 537
100 538
69 497
128 615
390 514
30 997
165 181
25 975
154 637
99 827
669 987
58 844
87 803
519 903
139 642
5 987
192 463
12 726
64 573
562 888
74 422
793 926
33 956
154 833
543 906
34 458
297 795
22 193
215 689
13 373
327 971
355 737
505 668
581 600
134 945
542 651
295 806
83 953
824 970
331 851
65 877
157 977
129 577
2 1000
339 948
456 900
107 502
185 915
109 222
292 724
200 594
359 585
304 957
482 510
2 998
25 916
46 751
515 872
353 724
595 942
688 937
373 826
23 177
550 955
41 556
694 710
319 987
44 905
515 564
84 694
433 793
114 275
30 870
105 813
429 648
466 967
37 967
105 961
17 662
360 408
556 932
301 953
249 452
185 478
372 677
139 437
199 875
307 760
360 609
335 879
144 833
463 956
640 945
62 714
246 917
175 267
55 602
391 729
205 940
614 980
209 986
368 896
60 88
727 902
80 574
365 791
159 540
191 381
71 518
267 705
215 763
22 907
95 645
204 318
395 453
156 955
83 269
117 269
64 912
236 513
114 977
160 380
70 935
149 888
259 661
6 881
556 960
807 921
26 838
1 938
417 582
156 953
445 656
237 946
6 992
69 787
407 542
278 892
108 862
108 583
58 123
104 820
141 442
386 862
72 850
260 674
345 968
3 996
10 997
360 472
17 790
200 913
558 766
572 732
403 535
245 842
236 714
35 311
125 682
77 747
140 546
253 596
145 404
54 989
511 967
227 542
234 456
273 949
134 260
83 979
311 998
167 994
52 850
48 953
131 166
28 923
165 723
428 530
32 721
550 931
365 655
381 692
18 925
259 721
142 975
2 705
589 611
53 919
64 749
18 243
53 367
301 802
295 990
217 412
220 951
5 982
827 891
490 715
43 706
40 770
535 939
253 961
363 822
65 383
111 969
177 202
158 995
483 769
74 378
73 723
622 850
12 56
235 811
7 997
104 910
597 867
20 953
44 998
250 270
190 402
334 525
246 814
138 326
63 250
382 902
427 512
281 970
165 923
232 444
447 972
302 542
124 850
92 150
42 319
16 758
412 956
135 698
2 707
101 867
130 834
155 970
34 953
498 862
44 995
67 962
362 806
70 973
445 884
301 606
241 671
101 556
260 798
52 951
365 745
5 996
296 605
194 702
168 999
376 932
121 748
711 858
104 948
25 996
395 872
9 394
788 933
50 895
106 815
601 868
33 940
298 356
291 971
398 399
465 925
57 398
180 918
67 747
46
32
68
65
74
66
15
61
34
6
66
65
55
58
29
63
64
43
10
8
18
56
34
69
35
21
31
37
53
22
51
74
56
22
43
18
29
59
57
65
74
20
36
53
43
31
69
66
68
65
31
29
32
25
70
62
46
40
38
58
16
74
68
68
9
18
70
46
65
7
41
19
26
14
57
24
68
49
57
41
71
63
49
70
28
25
10
30
65
62
65
13
60
60
47
74
74
65
38
36
27
67
65
68
68
18
1
54
65
58
27
68
70
39
51
64
20
70
58
28
58
68
60
62
66
55
43
43
38
65
51
44
31
34
43
74
46
68
59
66
66
74
70
37
59
43
66
56
70
42
65
43
68
65
70
40
40
42
5
58
68
68
69
68
68
67
10
66
37
64
22
46
70
33
65
32
68
55
53
43
60
5
69
22
71
58
43
44
5
68
37
68
74
58
7
46
74
63
61
74
71
59
65
3
68
74
70
52
9
74
57
11
9
63
25
39
62
0
39
64
70
59
68
68
70
28
56
20
70
65
27
31
60
51
51
46
70
58
30
66
52
57
70
57
74
62
18
37
52
43
8
31
22
60
48
35
74
65
12
70
63
51
18
48
54
64
65
68
27
71
39
1
63
40
74
71
70
37
61
53
63
58
32
74
62
24
36
61
53
35
37
65
8
62
63
23
34
65
65
74
65
40
52
41
64
67
64
8
68
62
61
26
10
9
68
68
36
70
23
41
58
56
68
62
70
56
38
60
15
49
69
46
46
23
65
29
44
17
63
14
63
53
39
34
23
56
70
45
57
42
53
74
68
51
39
47
71
11
25
53
67
36
61
69
8
33
20
47
34
68
70
55
68
58
39
70
38
62
70
23
47
64
57
52
68
17
53
72
34
57
63
43
46
74
9
65
13
66
57
18
37
33
63
43
58
56
68
37
48
53
69
9
50
70
44
55
66
22
29
71
6
33
38
21
52
71
46
70
68
65
62
24
15
13
49
33
21
63
65
63
42
67
18
40
38
46
44
19
63
71
33
28
71
68
45
68
52
50
37
13
44
70
58
64
15
21
45
71
66
44
51
69
22
35
45
43
37
43
68
23
68
33
62
65
62
54
36
71
20
70
65
24
63
57
39
70
54
40
70
68
70
74
65
60
5
60
68
31
23
68
41
63
62
74
25
67
65
68
69
47
53
54
48
56
43
60
66
65
63
25
64
38
63
67
65
38
74
68
70
40
18
63
28
22
60
35
66
30
65
68
71
37
4
46
70
71
20
43
63
46
68
68
54
43
51
19
52
63
38
33
66
56
46
68
48
30
58
4
68
50
74
68
74
8
55
27
2
65
68
62
74
56
74
42
32
57
30
37
63
52
58
55
27
61
68
29
28
61
5
65
72
33
61
15
54
68
16
65
3
69
74
17
43
3
2
4
46
35
64
71
58
62
12
68
34
37
67
64
65
70
53
74
74
56
69
19
65
36
44
64
58
64
27
29
31
68
52
17
62
38
58
19
68
6
60
40
31
39
40
57
64
27
56
65
44
31
33
44
14
50
54
70
17
38
65
29
31
65
47
66
56
46
29
44
59
48
57
25
65
22
68
41
46
68
34
68
14
43
66
49
52
54
62
42
57
32
34
64
64
74
4
62
17
41
42
43
44
28
71
7
71
48
65
41
65
65
49
53
74
36
64
46
42
36
22
70
63
46
40
58
23
53
39
65
55
30
6
68
26
58
70
24
58
67
68
44
74
64
54
42
65
18
53
43
34
65
12
74
68
64
47
52
48
36
57
22
50
46
4
65
67
13
56
52
25
67
64
38
55
70
69
59
14
49
65
34
39
44
38
64
57
34
60
63
55
39
59
66
18
46
51
68
48
68
61
8
23
46
57
41
27
43
51
61
68
55
23
16
68
26
23
67
40
69
30
70
65
50
71
50
20
66
74
33
68
37
68
74
65
30
64
65
45
13
64
38
57
65
50
64
74
74
24
69
65
37
33
30
62
56
29
54
64
41
41
34
70
53
40
35
67
21
70
65
68
65
70
7
69
57
26
59
49
43
46
71
55
68
60
7
68
64
28
34
58
65
29
68
74
13
38
56
64
51
68
57
33
69
6
68
46
33
59
36
14
62
74
66
39
71
70
7
31
33
62
27
26
61
24
67
66
34
58
34
63
14
31
68
63
54
60
65
63
68
70
47
70
70
57
70
54
37
52
45
62
70
56
74
37
53
68
64
62
24
69
71
58
41
24
67
64
39
70
14
65
1
53
36
66
64