#2060. 扑克比大小
扑克比大小
扑克比大小
题目描述
标题: 扑克比大小 - Problem - QOJ.ac
#3277. 扑克比大小
The problem was used in the following contests:
小 Z 和小 A 在玩扑克比大小。
他们玩的扑克比大小规则如下:
- 在游戏开始前,系统会给小 Z 和小 A 各发一堆手牌(两堆牌数量可能不相同),其中每张牌上写有一个小写字母。
- 在游戏的每一轮,小 Z 和小 A 同时翻开牌堆顶的第一张牌,若两人翻开的牌不同,则牌上对应小写字母更小的那一方获胜;若两人翻开的牌相同,则他们会将翻开的牌塞入牌堆底,继续游戏,直到某方获胜为止。
而系统实际上是从一个巨大的牌库里面发牌的,具体来说,假设牌库共有 n 张牌,分别是 a1,a2,⋯,an,则系统会随机选择第 l 张到第 r 张牌发给玩家,换言之,玩家从牌堆顶到牌堆底的牌分别是 al,al+1,⋯,ar。
现在小 Z 和小 A 一共要进行 q 轮游戏,并且小 Z 通过某种方式得知了系统在第 i 轮发给小 A 的牌为 ali,ali+1,⋯,ari,小 Z 想知道他一共有多少种可能的手牌能赢小 A。两堆手牌视为不同当且仅当两堆手牌数量不同,或存在一个位置 d 使得两堆手牌中距离堆顶为 d 的牌不同。
输入格式
从标准输入读入数据。
输入的第一行包含一个只包含小写字母的字符串 a 。
输入的第二行包含一个正整数 q 和一个整数 type,其中 type 表示数据类型。
接下来 q 行,第 i 行包含两个整数 li 和 ri。
输出格式
输出到标准输出。
输出 q 行,每行一个整数表示小 Z 有多少种可能的手牌能赢小 A。
样例数据
样例 1 输入
abbab
5 0
1 3
2 4
3 5
1 4
2 5
样例 1 输出
4
7
6
2
8
样例 2
见下发文件。
样例 3
见下发文件。
数据范围与提示
对于所有数据,满足 1≤li≤ri≤|a|≤5×105,1≤q≤5×105。
子任务 得分 n≤ q≤ type 1 3 102 102 0 2 3 500 2000 3 4 2000 4 5 2×104 5 13 105 105 3 6 17 0 7 15 5×105 5×105 1 8 15 2 9 25 0
数据类型 type 的含义为:
- type=0,数据无特殊限制。
- type=1,保证 ∃1≤l′≤r′≤|a|,ali,ri+ali,ri=al′,r′。
- type=2,保证 ∀r′−l′=ri−li+1,若 al′,r′−1=ali,ri,则必有 ar′≠ali。
- type=3,保证 ∑ri−li≤105。
其中 al,r 表示字符串 alal+1⋯ar;两个字符串 a+b 的结果为 a 和 b 按顺序拼接的字符串。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
abbab
5 0
1 3
2 4
3 5
1 4
2 5
4
7
6
2
8
样例 2
uocklowprkqducbugogbqxudlzblxjdpbkhgkdmwxrmlshenkelqsfiloiezgvjkehafnhkcoiyuuqmaggvzcosjtokoesxdtgdodmsvyowdwjlqmejomawynjwlrofmwbqrnxmprmlrqjlvbfltaiznjcgjfalhlsqquvcvkmvkfpkxnqjnkeogtrfquhedddchkgdrwvxygbdxgxernlaweoirhiqlazfzdfrihcxohcvbxnqpxycqvcwtqlfznwaylwbtiifpdlxtxulyzuzxtqfoottvekjiupgoqmnratkqndsjvvlziksmbtfusvsrpwfkwbtgrnajvaszpgidnlicjgdjadmcxbeqcaniwgrtxurpjaofqxpsiocuhnkwdnjwqctznxypcpqlnudgmmogqydlyasmhvknspfulsimojvzfzzukqayrpfgmcwapnsxygzquozpuotzcgtasldwqhldsarsachgpvpgmhqkpuoq
1000 0
227 339
161 349
41 167
110 121
35 110
80 365
402 500
104 140
247 283
412 483
201 489
82 157
110 265
113 342
333 437
279 414
124 236
156 308
6 432
103 253
110 139
97 244
111 490
343 485
225 265
16 235
83 322
317 440
94 365
15 469
259 375
44 248
185 198
437 480
220 322
31 69
318 371
12 317
228 257
27 337
29 359
35 225
297 485
132 180
204 230
67 86
131 373
78 283
399 478
297 405
218 410
377 422
173 372
200 479
160 265
48 246
130 160
155 309
304 328
171 216
446 480
305 500
334 414
76 355
225 341
282 433
163 455
6 287
65 388
90 256
344 382
94 323
203 216
58 114
92 351
27 367
457 491
234 384
134 437
247 455
211 463
304 356
99 126
1 422
369 444
78 277
36 254
87 417
304 383
437 488
217 221
26 482
358 452
175 289
254 354
164 479
83 153
16 152
266 372
168 190
79 157
90 476
187 434
274 277
3 181
193 194
64 156
114 338
296 495
175 415
228 269
19 306
261 352
365 383
97 248
58 373
336 436
52 263
200 403
240 351
161 193
322 427
257 356
156 437
74 299
110 481
430 464
201 485
193 225
236 455
68 440
74 431
34 283
253 340
50 146
130 372
44 176
412 466
357 447
31 294
189 413
158 174
232 244
65 217
391 476
19 308
336 497
113 168
143 439
144 440
395 400
252 265
381 480
79 335
121 190
73 145
50 294
246 278
75 483
147 189
162 390
121 263
198 295
235 259
9 193
151 185
24 130
135 446
11 187
131 291
46 454
282 465
56 281
73 283
83 293
185 394
158 398
147 163
76 380
97 360
449 484
144 153
141 264
465 489
269 270
252 268
248 491
61 359
55 180
37 57
33 376
56 308
208 451
38 125
88 399
169 458
151 390
150 417
9 407
277 398
50 115
17 237
54 238
264 471
138 393
121 209
32 387
289 423
12 154
96 445
329 479
251 422
118 145
100 298
229 262
274 427
165 251
279 287
129 320
143 169
43 163
157 312
472 495
133 442
298 483
122 135
405 438
68 248
65 353
127 161
282 408
8 497
142 226
174 317
297 397
114 336
56 454
67 90
221 427
131 307
63 384
34 330
15 388
385 465
49 145
137 187
224 400
257 370
130 265
195 301
308 331
385 484
87 114
408 444
40 233
10 53
35 148
132 236
303 477
184 490
16 461
369 422
1 41
28 282
42 85
36 63
47 262
391 474
172 206
362 367
390 393
330 420
187 481
134 245
53 492
311 447
318 409
185 482
1 260
34 437
15 245
192 480
138 446
11 206
138 248
218 331
78 173
164 192
85 275
148 359
227 388
248 402
138 290
20 353
454 491
312 408
85 401
336 370
133 421
139 250
75 205
279 313
22 173
109 472
1 169
370 466
237 449
365 428
216 372
94 423
172 175
46 271
267 347
344 495
52 288
211 475
82 367
158 241
221 341
155 439
266 414
93 130
133 336
131 242
269 431
214 231
258 434
247 406
193 425
71 276
50 72
276 293
70 448
150 262
97 366
33 311
174 212
13 216
374 408
99 292
216 230
164 283
52 341
100 386
50 223
115 424
126 478
306 465
300 427
200 202
180 381
182 391
488 489
117 402
264 310
404 466
15 297
389 461
409 495
201 311
133 266
71 455
105 308
287 419
88 478
266 418
159 498
52 234
138 426
70 171
211 223
195 236
58 218
269 304
21 82
355 434
314 481
96 390
35 110
153 367
314 452
341 353
301 336
28 140
311 323
131 338
154 241
58 317
224 430
135 196
208 253
160 203
175 447
280 407
235 369
177 486
389 399
44 314
130 414
34 451
190 434
72 327
289 356
6 418
63 71
10 132
332 386
62 137
29 88
238 340
35 283
388 500
51 112
218 227
193 341
325 403
134 494
466 498
112 160
204 391
287 330
407 443
178 457
66 474
190 460
154 226
337 467
199 326
297 314
42 428
286 470
21 125
30 118
208 322
244 447
254 283
194 235
326 492
58 438
177 357
222 314
343 401
287 297
103 423
258 435
61 315
21 282
133 154
36 321
338 466
317 461
30 367
160 409
40 221
81 469
406 418
63 149
75 360
243 320
26 86
387 419
189 263
458 500
41 381
131 316
45 282
11 203
147 287
355 421
474 476
166 228
186 303
254 426
419 426
331 483
212 256
304 336
3 405
350 357
186 427
191 335
189 200
277 435
397 447
150 311
126 136
338 410
57 445
314 340
189 408
22 79
36 104
93 318
122 429
195 310
96 332
118 244
106 168
166 466
13 351
359 488
91 259
131 369
285 471
248 266
4 187
157 443
2 8
315 452
186 328
40 459
98 130
461 473
37 448
106 280
54 202
240 483
238 429
45 242
346 424
340 362
1 101
79 294
22 354
80 304
130 197
456 458
155 342
41 251
136 449
63 240
296 428
107 166
237 359
330 433
203 381
21 322
278 294
266 487
190 345
239 360
71 382
354 403
254 356
399 438
89 320
267 390
80 243
203 235
34 233
92 360
352 494
26 328
82 82
188 274
235 308
52 179
91 318
181 255
279 376
106 377
129 315
395 479
93 269
178 472
273 342
51 464
421 486
37 215
288 471
70 248
58 432
8 451
258 475
264 320
167 168
84 341
237 277
27 408
335 374
8 422
274 421
85 281
294 450
117 495
173 472
285 326
158 244
128 266
96 392
80 324
228 380
406 409
355 390
242 417
255 345
189 219
274 498
125 442
65 371
14 500
349 387
90 474
63 439
204 471
29 357
401 466
120 142
344 463
143 254
55 84
6 471
44 215
146 433
208 263
61 159
236 276
103 266
221 491
1 373
247 302
178 346
3 94
109 182
27 313
324 360
379 414
338 432
39 122
105 455
374 399
225 266
399 415
35 394
406 457
420 494
58 384
134 299
281 456
259 495
318 443
18 218
80 340
15 333
133 316
86 330
242 436
218 314
369 425
192 434
389 414
211 467
235 412
151 387
23 44
157 473
325 452
79 374
132 143
224 393
94 341
209 251
87 167
109 316
125 483
348 360
77 105
80 204
132 410
136 245
236 494
200 379
248 484
240 329
67 319
56 405
261 390
249 430
47 457
86 161
232 437
371 478
141 262
50 402
50 434
54 376
290 344
184 481
58 94
252 263
51 320
91 129
303 482
23 452
240 402
66 452
359 475
117 447
93 360
457 474
254 453
228 422
241 364
337 393
73 223
22 360
206 387
14 121
140 144
87 459
21 330
73 186
1 121
52 69
60 254
380 429
121 261
75 372
356 495
40 65
67 363
178 459
2 107
107 171
197 360
93 489
367 445
66 403
282 500
188 375
271 368
99 179
318 329
487 487
418 442
376 437
154 489
189 328
264 404
27 459
140 216
113 227
201 209
177 190
10 222
237 379
107 428
47 310
200 304
350 483
379 416
87 468
126 380
78 449
328 406
135 237
113 385
83 280
353 369
434 481
290 292
217 387
181 322
11 402
121 202
28 270
475 487
344 347
313 418
64 429
74 78
207 422
189 481
76 429
81 133
7 120
186 239
296 469
268 420
367 394
74 131
48 103
364 424
426 469
96 376
154 176
356 360
88 413
360 421
289 358
397 446
176 395
288 325
441 459
112 400
318 383
18 367
123 296
243 437
91 202
182 476
181 255
153 305
182 257
50 462
82 340
137 294
13 447
358 406
142 459
90 437
46 143
77 114
412 421
230 480
40 135
57 241
100 100
65 103
88 277
124 463
344 405
417 487
318 466
219 343
255 359
48 387
61 463
406 422
282 360
97 241
256 366
81 258
53 312
138 405
291 434
119 133
203 479
309 436
116 431
149 231
66 263
254 399
74 271
235 413
334 391
28 126
302 452
191 333
221 383
156 202
257 359
330 375
50 423
304 339
101 464
298 383
255 306
160 197
17 147
13 204
30 67
24 156
85 272
29 414
12 112
138 429
255 274
338 340
128 319
51 240
158 466
253 394
126 498
126 150
96 148
156 173
407 427
170 292
243 328
23 344
197 432
280 312
32 416
73 204
148 494
268 271
7 300
359 484
271 500
43 60
133 444
225 323
2 308
229 420
225 479
310 411
228 471
131 323
191 227
298 374
16 52
345 441
172 269
171 468
187 486
19 199
237 238
46 147
241 244
114 454
11 473
6 100
285 497
121 153
89 220
209 270
109 338
3 280
67 211
60 406
58 146
83 458
240 299
324 376
139 469
305 482
59 388
96 222
79 431
114 467
375 452
58 334
44 370
152 212
3 453
350 428
193 438
80 442
82 427
76 156
48 266
172 305
328 473
66 127
77 154
169 455
204 241
173 236
248 358
135 408
252 438
204 450
37 42
7 97
27 112
56 248
14 312
49 299
164 481
153 333
166 174
325 498
116 278
136 239
17 95
97 446
179 329
239 274
32 262
13 320
50 412
86 462
76 425
372 420
78 453
88 428
261 348
123 465
273 448
245 498
140 357
88 331
169 300
48 419
13 359
98 229
134 366
227 276
78 364
308 410
228 476
249 257
10 297
205 281
269 341
193 322
19 483
266 383
142 268
27116
57160
116287
43399
35169
879
78441
107557
10768
31524
111920
33040
43724
61327
88937
124425
55962
42348
76305
94346
43414
95664
55028
37436
3674
100116
107799
6607
94667
7506
3448
56481
97819
27576
87089
16443
95593
18058
122132
5629
114311
35252
83184
89692
119079
181
84304
82583
120189
83136
73201
85939
25896
91087
36696
66816
5669
29926
83313
105877
77415
64982
64837
102790
3747
80865
83860
76176
19686
74107
15998
94701
118228
37515
70791
5492
119114
12377
114642
10925
22190
83319
16032
101237
117623
82362
30563
92575
83329
27581
21558
121002
4294
52374
53089
85394
107943
100183
37997
106224
60249
73972
26264
100854
9461
13431
47454
19929
74904
52237
122120
28121
58153
110215
95666
37825
45382
84527
91136
7668
57226
106609
68843
42434
40536
43658
92222
111924
12846
72422
25163
40626
49036
82148
20417
5871
56447
31512
113077
16640
100345
1547
38161
19429
46114
28123
45359
61405
57759
103850
98751
97507
39431
60170
66329
73691
20541
118471
120351
57572
93546
66054
29004
115564
87953
123439
14358
63002
80313
84358
34961
80849
53993
73395
107827
97568
1769
57245
102769
95840
60888
104083
81268
101579
13947
97504
85695
32421
38936
47047
5028
54010
113927
15360
45044
50241
123238
41066
87813
124219
20389
31193
23660
96292
61755
66025
76738
20234
17917
17690
108770
111719
2983
70418
13698
100953
103283
124552
108563
57603
61934
23244
2224
69241
62530
45685
68715
25001
19693
24512
80882
78687
44100
78086
83134
19928
54097
185
35747
84346
43276
49071
7428
37031
47903
88413
52914
68850
5770
8938
45604
37059
92793
30707
112455
51409
35553
89649
51564
32111
99945
117641
101543
58540
88874
30176
21202
46139
48568
1878
66473
6756
26322
114623
91443
59803
95564
97611
101367
49136
7296
13379
61736
80614
61567
73251
82650
85574
10397
95270
27264
85751
61804
6327
68686
123030
10511
45269
69171
56069
120614
124526
117189
110305
101437
102333
34038
110176
109787
94624
48259
34821
25729
15978
84753
22199
32849
1614
35845
30027
38115
22297
69134
84383
14090
52698
108204
10879
13023
46290
20353
120951
36151
41113
95835
4969
78327
99077
2045
16176
109910
85520
84721
70368
20481
44659
71121
17332
86576
90974
67025
21408
31456
60438
96412
53813
7346
15805
62390
111890
69328
46409
119964
98153
45102
38031
53476
84514
61743
35951
21988
8877
37587
13980
85982
60947
51751
17641
35169
41566
51710
77672
2507
58249
59680
84168
8532
37663
52905
63115
114104
36656
52312
116506
115705
67971
15750
56526
5912
49195
34531
10032
20178
76231
43384
51007
31592
105523
114559
11303
35294
109150
55222
73024
12950
79644
114656
75655
83064
118925
98224
13738
81495
33721
34550
8518
103595
16990
83105
88640
97906
86373
41834
114044
79834
53049
12549
109951
37748
68028
39544
37359
98250
94225
108138
32394
86269
69392
30373
2434
6626
41997
36805
112465
29536
99325
43365
120467
83531
121383
52005
100552
33380
116090
84341
92037
80319
57316
60939
53003
104635
86974
53210
93290
96089
89330
83316
9667
28526
86817
19114
100295
124181
69483
40913
70936
2380
72751
51643
100437
117279
30205
22454
45872
8947
17597
3079
76028
104443
98974
21946
50568
84175
75541
85836
49674
23352
69511
93116
86789
112258
28554
101640
46851
75745
23633
7791
11382
92057
53660
123957
101491
60185
117022
819
5706
118239
29952
116209
79164
43063
74935
109585
33916
6769
118073
86066
103558
38094
34465
104254
46475
14777
53090
120162
96877
25607
758
118211
49267
70784
41254
121148
29232
85166
115763
84818
50793
47977
124463
75786
108568
98692
22409
81460
117495
55433
37150
46699
104994
35998
37743
78715
108147
96404
11472
121639
33856
5532
1403
78732
100880
10403
77754
60500
25982
75620
1617
64178
17643
839
122013
99332
61029
68296
27372
100583
100899
89885
19559
8417
42612
73997
43202
118855
114314
10697
119743
15951
57891
39277
76290
56464
24365
114096
32275
72337
94338
35803
101277
10786
81568
9380
110555
5443
90433
79450
2401
64287
119825
2036
3675
120245
35376
99297
61480
37822
114833
97089
3563
95482
71788
855
7379
69307
75118
68287
73071
117638
13338
15849
22194
115666
123241
99794
23378
79613
60021
89363
52915
94689
33087
92418
110442
89844
9294
102257
719
89536
79026
72444
91031
85701
7820
414
54065
58136
104785
21130
75037
38304
90216
81269
20629
20658
23773
49390
32125
37501
97508
55345
50865
51543
99472
7715
33677
21937
60519
22625
119131
53153
121972
115450
103686
73640
117016
4083
8064
90819
92548
86070
73664
101477
84894
122743
92361
66053
120455
12226
112608
457
81453
69945
109580
48826
22594
90920
33640
80827
85102
116632
16079
95627
35594
2255
26431
8762
100331
96338
5580
90765
61099
111875
68114
51056
33931
109358
21007
91205
28485
79364
92544
71168
82476
51950
63092
61187
107840
31
45661
49354
21696
48027
80399
66022
58309
18682
16007
38728
47284
40384
18880
100383
102728
29273
111391
87012
74919
77314
90847
40423
66496
40289
77505
17629
8471
12246
45054
80033
20180
69484
115000
104939
50893
82917
95465
71577
110849
83570
50535
21482
47977
41725
21296
20683
32835
88345
98900
4251
43984
73947
34736
102250
31474
26707
112545
72909
74590
19333
44963
55842
15899
118405
95490
40000
27379
66636
32504
99322
80913
95923
123609
29607
91569
61657
42839
112632
117989
106781
74413
1097
33533
53117
40512
115578
64736
58612
96523
19113
35712
42277
68844
6712
20647
83318
15198
62469
27340
36955
30867
99086
42232
14381
10394
114262
17880
61670
27312
2313
63976
55289
1837
82001
71108
70941
17790
42260
13723
63612
83536
99558
48736
116596
76751
73653
95170
77167
111234
21960
116647
62324
69184
3731
69644
13601
3878
106425
121928
84162
19020
62463
100264
67689
48310
105672
26305
28038
33825
34738
115302
20025
80456
76496
75523
66349
96945
33101
110420
9553
306
122597
37542
107643
7621
90422
56240
64972
23056
17501
60057
20038
71341
37842
56554
65665
9712
28440
13036
957
32897
102948
66807
48535
51902
33436
102217
50239
119068
25787
85779
63019
97315
118872
46594
111411
5251
53969
8244
47643
85393
41551
104679
79587
74274
79283
31231
95777
44405
104327
76920
99000
20638
75175
102732
77996
82473
45065
58157
110699
117399
117713
90671
45174
50339
66735
98967
28899
114768
27063
82393
45481
121923
104686
51106
27662
14013
12934
28262
38005
44083