#1793. 不是这一道据数构结题
不是这一道据数构结题
不是这一道据数构结题
题目描述
标题: 不是这一道据数构结题 - Problem - QOJ.ac
#7771. 不是这一道据数构结题
The problem was used in the following contests:
给定一个长度为 n 的序列 a,q 次询问,每次询问一个区间 [l,r] 的权值 f(al∼r)。
f(A) 定义为:执行 m 轮操作,非空的轮数。
具体的,令 A 数组长度为 m,则执行 m 轮操作。
第 i 轮从 i 开始,依次检查 Ai 与 A_i+1∼Am 的大小关系,设当前检查 Ai 与 At 的大小关系,若 Ai<At 则交换 Ai 与 At,若第 i 轮进行了至少一次交换,称这一轮非空。
具体的,以 f([1,4,2,3]) 为例,每一轮操作之后,数组分别为 [4,1,2,3],[4,3,1,2],[4,3,2,1],[4,3,2,1],前 3 轮是非空的,所以 f([1,4,2,3])=3。
注意,f 函数对 原数组 a 不造成任何实质上的影响,仅用于计算权值。
输入格式
第一行输入两个整数表示 n,q。 接下来一行输入 n 个整数表示 a 数组。 接下来输入 q 行,每行两个整数表示每次询问的区间。
输出格式
输出共 q 行,每行一个整数表示该组询问的答案。
样例输入 1
5 5
2 2 1 3 3
1 2
1 5
2 4
2 5
1 4
样例输出 1
0
4
2
3
2
样例输入 2
10 10
4 10 4 8 2 3 3 10 6 8
3 4
4 4
3 5
8 9
2 5
10 10
1 2
1 5
1 4
7 8
样例输出 2
1
0
1
0
1
0
1
2
2
1
样例 3
见 下发文件 。
数据范围与提示
对于所有的数据,满足 1≤n,q≤106,1≤ai≤n。
测试点编号n,q是否 a 形如排列1∼1≤100是2∼2≤100否3∼5≤3000是6∼8≤3000否9∼10≤10000是11∼12≤10000否13∼13≤200000是14∼16≤200000否17∼17≤1000000是18∼20≤1000000否
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1000 1000
976 638 999 342 999 490 842 564 972 577 264 212 227 45 231 14 308 62 763 567 261 965 644 577 565 811 997 578 703 446 978 853 117 68 945 398 749 229 552 73 638 164 755 60 513 77 900 439 400 859 622 869 58 203 521 786 180 866 321 230 399 773 77 111 768 58 343 4 845 391 375 103 786 732 393 650 850 47 385 793 387 475 409 779 335 464 326 176 331 250 56 225 441 324 432 226 870 927 223 989 232 902 478 17 450 436 285 22 558 970 890 757 288 969 216 34 79 262 939 239 366 918 376 999 143 385 611 559 750 196 161 920 374 824 616 559 549 303 2 371 560 566 216 853 384 743 699 594 702 507 618 208 987 860 240 515 117 848 550 751 382 633 397 365 851 605 623 887 464 317 98 121 815 299 985 913 318 611 176 127 537 645 64 223 116 205 836 207 109 469 325 294 51 478 607 726 55 12 742 388 932 162 756 52 1 457 268 843 465 298 460 339 184 93 518 541 152 297 169 98 414 418 678 672 651 592 847 862 923 673 352 643 961 599 223 229 497 798 105 323 959 155 244 220 82 870 293 964 402 746 220 713 140 268 566 652 889 710 690 18 970 346 42 241 195 742 512 639 946 787 407 337 582 444 148 455 625 822 235 932 404 31 466 667 826 392 127 936 623 250 635 408 544 652 259 376 178 869 203 527 307 956 787 773 861 293 832 217 675 207 428 721 107 335 362 177 581 252 555 197 179 547 222 802 545 647 793 942 75 254 472 963 896 499 140 443 533 438 719 78 730 401 230 127 478 619 612 522 734 303 361 87 991 817 454 671 113 62 358 543 860 966 210 374 371 771 689 368 276 426 466 502 438 843 574 564 768 374 963 294 694 322 715 830 569 877 354 759 86 516 53 221 187 164 668 991 552 396 962 984 885 520 989 186 128 997 826 484 692 703 121 946 806 547 608 432 291 552 891 377 483 181 239 522 496 319 486 230 253 608 772 854 643 311 24 681 791 770 758 664 874 583 385 905 311 982 815 602 469 621 954 80 600 275 970 876 782 667 26 656 839 341 472 702 581 626 115 608 889 762 394 542 817 468 511 391 807 554 234 979 129 513 541 237 457 670 509 245 356 391 471 472 765 742 962 580 412 964 842 294 28 799 925 253 296 49 2 632 379 187 123 123 777 423 529 314 8 328 34 766 618 250 682 527 67 468 98 673 899 36 116 999 671 425 844 9 759 874 673 342 740 402 564 790 642 221 213 205 846 453 88 170 12 942 394 446 278 84 695 970 690 609 524 25 562 654 114 228 258 707 292 967 432 697 41 616 395 333 185 971 996 14 717 977 120 129 814 792 20 9 888 312 5 4 529 91 874 75 841 479 631 722 779 917 310 825 426 257 166 471 187 635 808 512 771 587 135 206 457 341 749 993 739 707 338 2 450 120 388 618 7 392 276 330 410 910 239 265 937 669 710 928 570 902 602 884 881 736 889 462 929 127 123 153 492 537 758 103 86 80 628 471 641 397 101 703 846 685 615 994 666 825 165 295 273 125 671 593 199 780 238 297 184 57 563 634 767 423 840 461 398 822 117 847 341 734 44 929 342 957 662 727 755 724 678 797 877 600 565 987 937 430 81 671 682 268 367 108 619 68 1 178 318 181 153 178 560 960 117 715 362 215 154 985 457 528 365 241 619 205 526 227 497 134 541 569 569 570 643 145 702 752 533 108 726 10 929 29 247 686 354 593 358 131 166 177 524 376 978 381 477 8 270 57 706 969 116 298 973 304 5 444 370 248 699 300 448 57 204 660 247 328 953 7 596 109 785 791 392 463 6 349 515 465 855 210 454 392 469 927 360 248 770 815 693 259 851 618 658 304 806 20 474 962 381 415 240 479 118 508 361 920 17 42 424 98 557 23 295 389 648 931 99 662 962 106 248 303 560 751 906 624 893 384 931 196 674 395 320 587 15 766 5 748 792 20 552 149 927 935 504 500 440 798 592 176 511 843 677 577 27 338 312 417 650 37 145 360 90 765 469 360 414 921 97 207 529 523 180 109 517 184 467 860 611 586 456 801 685 976 445 747 431 190 578 801 606 457 327 129 752 451 287 359 959 283 58 559 551 9 417 324 623 836 264 236 127 611 286 880 341 567 164 489 320 599 95 795 916 846 564 817 211 617 583 298 32 257 792 664 683 300 399 829 143 708 393 44 62 829 624 289 873 255 294 557 909 176 197 133 974 515 945 372 129 772 195 993 627 828 518 385 208 316 113 648 118 251 357 946
69 719
716 979
159 393
9 677
778 935
139 522
233 423
314 326
730 854
58 501
591 638
22 878
196 420
83 909
234 651
918 934
211 903
338 831
189 531
528 907
245 348
382 576
245 824
14 510
700 923
758 877
605 854
469 652
90 457
202 968
160 979
411 888
547 808
127 498
874 968
98 747
512 943
249 286
64 223
319 640
138 965
12 122
75 356
220 554
14 202
585 614
376 904
419 544
49 923
86 912
70 126
576 978
391 937
495 601
128 570
228 544
506 705
403 728
263 893
249 918
129 531
118 798
264 494
348 715
704 987
261 921
249 945
441 761
177 588
390 722
654 864
468 690
183 440
211 243
283 589
103 483
80 830
41 617
332 579
516 724
897 949
593 783
549 985
536 552
122 816
164 486
581 907
58 304
110 390
82 239
322 738
135 403
45 237
378 798
452 910
697 971
772 823
1 372
394 442
79 147
804 949
323 758
830 960
288 418
60 932
159 794
98 310
459 553
11 603
562 828
123 197
723 998
523 743
324 692
350 809
132 514
116 266
382 795
232 617
62 475
176 935
821 914
741 840
292 380
798 905
102 485
313 978
485 755
20 806
318 735
374 843
236 977
809 964
428 436
355 662
41 958
643 780
271 552
778 845
523 725
257 710
33 904
557 646
56 239
511 818
406 584
7 741
227 895
218 621
813 817
103 270
140 151
471 969
504 658
139 783
72 197
536 641
50 497
77 115
652 737
388 540
534 749
862 948
853 910
456 960
181 834
131 676
308 618
242 293
471 642
37 146
215 791
483 838
207 405
130 502
49 845
317 463
450 686
583 612
479 559
126 831
266 411
78 391
469 719
795 928
45 814
102 976
121 719
75 562
445 451
495 722
419 702
87 92
254 643
297 481
374 624
552 558
256 360
19 496
61 763
92 639
173 979
326 959
895 911
384 824
613 873
435 895
746 813
264 301
473 957
299 359
14 742
327 877
12 303
462 903
608 944
53 475
477 488
219 674
229 900
384 691
457 644
294 476
410 554
652 914
140 420
413 570
490 677
595 769
248 852
95 110
90 499
143 377
138 320
213 899
353 599
311 526
93 689
49 914
206 930
627 900
287 543
139 571
702 724
50 525
155 725
41 791
584 742
215 972
170 576
345 559
681 840
94 150
224 741
481 989
107 121
227 686
548 779
97 657
507 538
740 993
34 657
837 910
154 936
415 544
633 999
204 401
54 625
779 970
3 989
238 515
106 942
218 741
151 746
159 913
144 365
722 887
208 447
493 921
275 839
100 787
248 708
264 526
282 924
277 312
592 935
645 997
411 564
160 439
42 583
321 881
568 749
248 965
591 958
527 857
112 334
673 858
35 723
130 304
444 684
357 801
145 538
197 719
173 559
359 577
306 994
58 145
45 206
676 913
420 607
358 552
109 141
451 793
105 538
335 839
277 603
284 286
1 462
625 657
244 942
81 276
239 495
147 902
360 770
479 978
143 285
268 521
615 717
352 784
328 778
147 308
234 570
93 564
446 669
412 680
458 476
110 496
46 71
450 879
112 976
385 613
70 510
4 277
61 616
3 408
231 687
377 755
202 246
483 816
405 993
35 292
507 859
386 730
23 859
265 810
369 787
418 672
415 742
221 968
95 934
818 830
238 899
640 716
83 887
22 629
478 727
131 991
347 509
225 995
343 947
234 394
507 784
191 300
659 896
125 443
164 935
898 907
820 844
263 282
214 360
428 611
417 773
189 419
659 789
538 940
831 882
369 873
526 997
31 756
706 861
618 690
99 221
276 466
656 709
764 959
43 717
815 871
165 168
635 964
50 693
227 720
274 381
464 474
278 984
203 893
92 707
417 611
662 691
715 867
182 275
640 683
380 778
761 914
232 482
59 521
770 952
547 910
505 752
50 986
189 500
621 921
278 384
259 964
624 993
246 951
928 948
350 897
40 352
168 833
516 653
860 922
586 600
117 274
17 974
443 606
86 245
510 970
20 85
291 728
202 964
687 785
184 910
335 452
87 449
50 437
195 961
334 516
319 599
8 88
156 502
114 352
859 931
318 767
54 840
537 688
652 657
350 393
434 849
172 622
352 976
31 843
263 793
350 459
164 333
267 356
167 292
249 365
217 886
5 111
208 350
901 965
771 855
388 914
734 769
22 786
591 870
133 427
159 405
79 919
113 336
141 481
250 927
263 780
272 1000
403 886
34 759
681 905
688 732
193 447
338 968
427 866
185 679
815 989
774 852
186 988
643 829
337 397
280 326
323 382
269 480
37 447
787 865
422 690
747 799
386 479
900 966
595 844
713 812
1 671
16 292
560 681
399 615
259 463
804 981
469 872
414 986
489 967
455 528
247 1000
182 858
331 703
693 861
149 526
653 669
539 686
146 372
24 758
71 680
15 823
75 370
610 830
106 325
313 597
33 856
572 586
620 792
15 754
185 617
477 489
166 907
211 617
113 333
17 561
43 981
133 399
523 639
862 888
342 706
280 902
45 406
304 800
293 868
150 997
257 595
868 938
213 233
150 886
121 705
8 784
97 239
583 818
386 933
204 992
698 887
101 421
164 418
641 657
79 633
321 735
249 324
223 500
147 544
376 445
692 696
342 439
15 367
89 515
324 512
43 707
574 829
492 729
298 965
152 304
11 836
389 812
914 951
620 782
617 771
97 666
639 955
533 890
470 589
30 384
838 992
17 743
57 677
450 985
3 547
71 281
628 704
670 930
695 929
392 551
328 377
129 642
59 408
277 335
15 324
511 743
71 660
155 202
320 926
287 386
150 979
413 796
107 155
11 469
102 419
775 884
75 323
301 952
382 419
207 960
490 636
7 923
9 489
641 845
232 386
780 917
123 131
172 426
30 405
284 911
200 830
441 492
423 705
113 267
187 877
694 944
436 901
592 824
130 449
156 163
52 172
871 931
19 728
594 661
23 51
678 969
407 468
180 847
338 477
573 873
186 433
79 658
579 951
107 180
214 709
484 520
172 656
211 271
197 341
203 556
270 802
193 520
70 875
334 517
529 662
511 659
927 948
165 886
219 525
680 990
729 982
552 675
36 823
48 654
169 722
313 642
452 824
76 525
22 122
89 921
556 808
179 690
194 825
162 804
28 715
59 801
24 946
810 934
337 899
50 456
743 853
36 51
212 522
349 818
200 703
57 953
213 816
37 953
585 874
437 475
722 983
29 591
34 803
563 723
890 968
572 814
38 663
304 751
918 919
193 504
202 354
272 904
273 944
391 472
785 948
577 806
263 774
218 741
206 611
273 982
150 643
110 890
6 191
367 804
463 845
279 904
349 523
141 593
156 574
743 873
141 208
635 990
290 879
348 713
319 958
97 851
198 628
282 396
105 381
317 735
28 161
390 734
661 673
907 940
420 613
721 978
143 623
105 949
36 738
528 845
143 461
277 394
34 671
718 796
182 745
616 654
83 710
50 56
120 486
177 499
580 743
53 465
646 844
60 595
38 822
200 286
11 705
33 170
943 993
438 838
635 819
29 766
289 737
516 955
357 366
645 759
409 478
252 733
60 141
583 775
847 903
580 928
486 866
204 851
181 361
227 529
489 767
283 306
271 712
780 798
190 662
167 632
387 439
441 553
260 958
145 233
377 418
155 568
42 550
388 493
171 262
475 738
168 530
22 838
268 277
11 350
724 778
154 429
317 421
242 543
224 499
198 365
124 505
258 625
812 859
339 658
636 738
175 232
348 880
321 324
153 607
358 523
155 673
138 368
319 456
100 944
760 963
141 798
247 916
13 996
85 943
42 869
127 452
147 465
74 446
649 673
63 302
468 806
345 680
366 373
195 925
259 774
750 942
612 837
223 340
650 746
291 430
168 711
154 483
493 703
246 686
58 835
101 909
553 586
525 766
717 720
388 625
45 894
345 602
79 799
303 715
552 581
557 795
54 419
149 150
251 655
614 837
228 586
95 255
88 172
428 964
532 802
128 281
135 671
515 617
168 284
192 703
4 182
235 882
168 499
245 640
93 996
455 817
218 570
199 240
246 981
171 363
427 620
9 538
199 311
371 403
460 907
771 958
25 365
224 713
318 906
525 819
464 791
626 865
84 193
151 811
397 442
44 716
317 659
781 983
390 978
404 558
570 613
406 1000
67 106
95 595
115 524
283 291
207 629
344 419
287 877
197 823
82 431
75 685
612 763
97 995
601 786
523 929
183 730
78 149
174 567
199 885
422 860
491 741
790 793
133 954
47 980
428 943
363 876
332 531
13 97
36 723
566 816
304 787
241 423
4 839
527 703
87 161
123 389
449 931
153 161
686 699
124 950
275 463
69 308
711 720
592 883
329 999
293 454
536 817
84 405
157 872
700 871
77 931
790 962
455 533
160 781
16 109
278 335
551 859
619 716
721 875
247 339
3 205
11 147
295 575
497 588
785 896
808 869
816 859
131 134
92 686
621 744
265 684
168 242
62 474
532 876
410 575
643 904
2 981
552 672
123 449
300 572
292 359
854 941
20 160
168 491
143 914
472 580
143 853
20 417
289 319
650
263
234
668
156
383
190
12
124
443
47
855
224
825
416
16
692
493
342
379
103
194
579
496
223
118
249
182
367
765
818
477
261
371
94
648
431
37
159
320
826
110
281
334
188
29
528
125
873
825
56
402
546
106
442
316
198
325
630
669
402
679
230
366
283
660
696
320
411
331
210
221
257
32
306
380
749
576
247
208
52
190
436
16
693
322
325
246
280
157
416
268
192
420
458
274
51
371
48
68
145
435
130
130
871
634
212
94
592
266
74
274
220
367
459
382
150
413
385
413
758
93
99
88
107
383
665
270
785
417
469
741
155
8
306
916
137
281
67
202
452
870
89
183
307
178
733
668
403
4
167
11
498
153
643
125
105
447
38
85
152
215
86
57
504
652
545
310
51
170
109
576
355
198
372
795
146
235
29
80
704
145
313
249
133
768
873
598
487
6
226
282
5
388
184
250
6
104
477
701
547
805
633
16
440
260
460
67
37
484
60
727
550
291
441
336
422
11
454
671
306
186
182
144
262
280
157
186
174
604
15
409
234
182
686
246
215
596
864
724
273
256
432
22
475
569
749
158
757
406
214
159
56
517
508
14
458
231
560
31
252
623
73
781
129
366
197
571
190
984
277
835
523
594
753
221
164
239
428
564
686
459
262
642
35
343
352
153
279
541
560
181
717
367
330
222
185
687
174
239
444
393
522
386
218
688
87
161
237
187
194
32
342
433
504
326
1
461
32
698
195
256
754
410
499
142
253
102
432
450
161
336
471
222
267
18
386
25
429
863
228
440
273
555
404
455
378
44
333
588
257
352
344
835
545
418
253
327
747
838
12
661
76
803
607
249
859
162
770
604
160
277
109
237
318
770
9
24
18
146
183
356
230
130
402
51
504
471
724
155
72
122
190
53
194
674
56
3
329
643
492
107
10
706
689
615
194
29
152
93
43
398
152
250
462
181
363
247
935
311
300
106
705
369
705
20
547
312
664
137
62
14
157
956
163
159
460
65
437
761
98
725
117
362
387
765
182
280
80
346
238
72
449
785
151
5
43
415
450
624
811
530
109
169
89
125
116
669
105
142
64
84
526
34
763
279
294
246
839
223
340
677
517
728
483
724
224
44
254
630
439
494
174
78
801
186
60
46
59
211
410
78
267
52
93
66
249
99
670
276
121
216
204
177
403
572
478
73
753
675
371
168
377
16
147
226
733
609
807
295
220
219
284
822
14
172
738
432
12
740
406
220
544
937
266
116
26
363
622
361
496
575
846
338
70
20
735
584
775
142
235
547
787
189
320
254
16
554
414
75
277
397
69
4
97
352
426
188
664
255
237
667
152
824
423
37
162
154
569
316
357
119
354
154
725
620
535
543
210
76
259
234
159
49
513
349
58
309
232
589
47
606
99
828
383
48
458
317
108
248
651
37
753
145
915
480
204
154
136
8
254
375
627
629
51
281
154
689
250
465
232
319
7
120
60
708
67
28
291
61
666
139
300
247
579
372
73
494
36
484
60
144
353
532
327
804
183
133
148
21
720
306
310
252
123
786
606
552
328
372
449
100
831
252
511
630
641
687
741
921
124
562
406
110
15
310
469
503
895
603
915
289
38
260
562
768
160
78
242
625
447
0
311
152
632
671
81
163
229
511
523
405
709
493
779
185
437
382
625
174
452
418
129
67
355
589
364
639
753
430
114
276
418
133
344
12
33
193
257
480
843
701
317
318
117
637
78
562
38
627
6
366
322
163
412
198
535
783
86
694
137
50
400
184
736
448
439
9
114
69
481
81
192
56
348
380
646
180
302
278
23
440
18
472
465
52
112
698
88
41
413
508
105
91
263
362
815
8
339
54
275
104
301
275
167
380
367
47
318
102
56
532
3
454
165
518
230
137
843
202
656
669
982
857
826
325
318
372
24
239
338
334
5
729
515
191
225
117
96
139
543
329
209
439
776
807
33
241
2
237
848
257
719
411
29
238
365
0
403
223
358
160
84
536
269
153
536
102
116
511
178
647
331
394
902
362
352
41
735
192
193
529
112
32
447
186
340
488
588
294
327
239
109
659
45
672
341
201
588
154
43
594
39
500
409
8
421
75
590
625
349
610
151
897
185
406
546
71
393
685
438
250
3
820
932
515
513
199
84
686
250
483
182
834
176
74
266
482
6
13
824
188
239
7
291
670
161
281
321
714
171
853
172
78
620
93
57
308
97
154
92
200
136
280
91
111
61
43
3
594
123
418
74
412
343
165
261
978
120
326
272
67
87
140
323
770
108
709
397
30