#2385. 线段树
线段树
线段树
题目描述
2 线段树 2.1 题目描述 九条可怜是一个喜欢数据结构的女孩子,在常见的数据结构中,可怜最喜欢的就是线段树。 线段树的核心是懒标记,下面是一个带懒标记的线段树的伪代码,其中tag 数组为懒标记: 1: function Pushdown(Node) 2: if tag[Node]= 1 then 3: tag[Lson(Node)]←1 4: tag[Rson(Node)]←1 5: tag[Node]←0 6: end if 7: end function 8: 9: function Modify(Node, l, r, ql, qr) 10: if [l, r] ∩[ql, qr] = ∅then 11: return 12: end if 13: if [l, r] ⊆[ql, qr] then 14: tag[Node] ←1 15: return 16: end if 17: m ←⌊l+r 2 ⌋ 18: Pushdown(Node) 19: Modify(Lson(Node),l, m, ql, qr) 20: Modify(Rson(Node),m + 1, r, ql, qr) 21: end function 其中函数Lson(Node) 表示Node 的左儿子,Rson(Node) 表示Node 的右儿子。 现在可怜手上有一棵[1, n] 上的线段树,编号为1。这棵线段树上的所有节点的tag 均为 0。接下来可怜进行了m 次操作,操作有两种: • 1 l r,假设可怜当前手上有t 棵线段树,可怜会把每棵线段树复制两份(tag 数组也 一起复制),原先编号为i 的线段树复制得到的两棵编号为2i −1 与2i,在复制结束 后,可怜手上一共有2t 棵线段树。接着,可怜会对所有编号为奇数的线段树进行一次 Modify(root, 1, n, l, r)。 • 2,可怜定义一棵线段树的权值为它上面有多少个节点tag 为1。可怜想要知道她手上所 有线段树的权值和是多少。 2.2 输入Ḑ式 第一行输入两个整数n, m 表示初始区间长度和操作个数。 接下来m 行每行描述一个操作,输入保证1 ≤l ≤r ≤n。 5
2.3 输出Ḑ式 对于每次询问,输出一行一个整数表示答案,答案可能很大,对998244353 取模后输出即 可。 2.4 ḋ例输入 5 5 2 1 1 3 2 1 3 5 2 2.5 ḋ例输出 0 1 6 2.6 ḋ例㾷䞞 [1, 5] 上的线段树如下图所示: 在第一次询问时,可怜手上有一棵线段树,它所有点上都没有标记,因此答案为0。 在第二次询问时,可怜手上有两棵线段树,按照编号,它们的标记情况为:
- 点[1, 3] 上有标记,权值为1。
- 没有点有标记,权值为0。 6
因此答案为1。 在第三次询问时,可怜手上有四棵线段树,按照编号,它们的标记情况为:
- 点[1, 2], [3, 3], [4, 5] 上有标记,权值为3。
- 点[1, 3] 上有标记,权值为1。
- 点[3, 3], [4, 5] 上有标记,权值为2。
- 没有点有标记,权值为0。 因此答案为6。 2.7 数据㣗ೈ与约定 测试点 n m 其他约定 1 ≤1000 ≤10 无 2 3 ≤1000 4 5 ≤105 ≤105 询问只有一个 6 7 8 无 9 10 对于100% 的数据,1 ≤l ≤r ≤n。 7
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 5
2
1 1 3
2
1 3 5
2
0
1
6
样例 2
997 1000
1 125 365
1 311 646
1 119 489
1 119 817
1 152 880
1 340 995
1 350 987
1 575 968
1 741 800
1 194 273
1 273 398
1 88 338
1 236 419
1 281 610
1 8 222
1 314 758
1 216 650
1 272 690
1 526 643
1 614 877
1 31 375
1 72 84
1 373 615
1 575 928
1 146 651
1 436 914
1 407 663
1 544 856
1 276 427
1 390 465
1 139 729
1 670 753
1 171 840
1 118 307
1 440 991
1 107 320
1 719 849
1 640 851
1 194 680
1 413 422
1 216 973
1 57 219
1 250 275
1 524 532
1 71 715
1 162 733
1 189 260
1 584 914
1 38 323
1 230 378
1 684 708
1 19 49
1 445 787
1 447 824
1 611 750
1 686 979
1 58 408
1 55 72
1 409 925
1 236 638
1 323 964
1 560 679
1 678 767
1 344 551
1 320 540
1 582 792
1 330 614
1 604 634
1 244 449
1 66 659
1 1 740
1 140 530
1 112 376
1 61 117
1 592 920
1 15 394
1 660 871
1 697 750
1 632 897
1 115 393
1 788 858
1 131 595
1 165 202
1 517 793
1 369 780
1 940 996
1 376 467
1 197 218
1 162 992
1 179 940
1 199 975
1 545 670
1 509 703
1 70 990
1 255 558
1 394 960
1 674 797
1 451 799
1 684 804
1 189 231
1 437 796
1 206 675
1 392 498
1 505 639
1 519 843
1 270 836
1 640 990
1 278 767
1 199 644
1 426 467
1 500 779
1 625 776
1 886 953
1 761 896
1 356 946
1 416 900
1 153 579
1 354 618
1 372 741
1 853 964
1 713 739
1 118 959
1 649 888
1 138 582
1 108 200
1 320 501
1 65 890
1 252 943
1 8 296
1 618 786
1 540 812
1 203 761
1 349 887
1 89 966
1 407 410
1 270 412
1 43 980
1 279 756
1 222 870
1 229 442
1 435 585
1 3 500
1 735 914
1 183 555
1 129 470
1 403 746
1 438 810
1 509 900
1 478 636
1 579 848
1 55 842
1 569 764
1 245 628
1 236 664
1 201 429
1 306 496
1 272 558
1 395 975
1 455 668
1 856 941
1 931 989
1 696 853
1 245 859
1 219 587
1 438 861
1 127 802
1 485 685
1 388 861
1 499 962
1 37 324
1 387 987
1 688 754
1 439 678
1 544 990
1 38 839
1 79 944
1 428 485
1 106 685
1 93 685
1 260 686
1 352 770
1 57 271
1 142 740
1 654 707
1 417 703
1 51 236
1 545 696
1 97 250
1 23 977
1 211 472
1 129 914
1 102 510
1 56 432
1 392 618
1 415 784
1 579 692
1 281 899
1 650 977
1 181 518
1 685 962
1 519 946
1 132 281
1 79 979
1 1 939
1 556 888
1 514 957
1 763 857
1 309 719
1 344 344
1 7 803
1 449 489
1 422 505
1 635 682
1 649 899
1 177 183
1 783 840
1 589 676
1 523 775
1 255 969
1 178 914
1 513 738
1 477 608
1 787 906
1 27 486
1 181 969
1 97 597
1 34 102
1 79 726
1 310 959
1 113 782
1 124 695
1 847 945
1 516 855
1 289 522
1 431 809
1 277 402
1 699 927
1 498 967
1 444 853
1 30 473
1 644 911
1 288 323
1 294 419
1 61 873
1 603 617
1 127 589
1 442 753
1 72 274
1 548 960
1 594 645
1 333 469
1 465 943
1 94 507
1 460 559
1 114 667
1 35 605
1 88 559
1 84 277
1 70 374
1 270 868
1 39 471
1 130 917
1 99 147
1 415 693
1 291 307
1 407 960
1 763 827
1 465 932
1 608 944
1 716 756
1 165 355
1 482 762
1 340 482
1 181 459
1 530 969
1 803 857
1 729 809
1 43 848
1 389 946
1 771 883
1 132 563
1 681 962
1 400 437
1 783 987
1 93 472
1 802 920
1 26 185
1 58 210
1 932 961
1 268 978
1 52 645
1 148 482
1 198 257
1 382 842
1 195 857
1 206 480
1 195 769
1 744 871
1 553 940
1 211 658
1 108 435
1 512 841
1 38 749
1 542 719
1 183 452
1 337 859
1 293 933
1 176 268
1 129 152
1 38 629
1 391 736
1 121 328
1 214 598
1 451 641
1 616 801
1 12 319
1 524 631
1 166 495
1 402 563
1 62 603
1 620 856
1 251 449
1 122 868
1 446 917
1 31 306
1 27 217
1 565 800
1 847 848
1 542 950
1 708 774
1 365 991
1 533 543
1 621 920
1 178 800
1 484 742
1 729 933
1 232 905
1 280 441
1 213 832
1 348 979
1 296 935
1 828 981
1 907 934
1 689 813
1 235 964
1 323 574
1 360 532
1 429 824
1 372 542
1 145 487
1 675 737
1 156 284
1 697 703
1 401 428
1 17 97
1 7 546
1 804 893
1 200 344
1 315 615
1 579 918
1 9 18
1 118 281
1 87 96
1 68 526
1 217 245
1 167 482
1 177 546
1 805 836
1 6 349
1 89 929
1 224 281
1 563 648
1 16 688
1 300 451
1 133 225
1 381 601
1 443 671
1 532 777
1 409 612
1 218 591
1 378 801
1 459 565
1 329 982
1 69 954
1 196 694
1 444 985
1 698 945
1 19 393
1 867 939
1 402 520
1 88 597
1 264 718
1 556 766
1 138 434
1 162 627
1 376 818
1 776 794
1 301 520
1 240 445
1 96 360
1 586 959
1 627 675
1 233 400
1 235 397
1 265 850
1 229 710
1 156 327
1 571 773
1 394 964
1 424 510
1 209 526
1 187 563
1 640 760
1 42 53
1 569 760
1 27 554
1 63 360
1 151 528
1 598 765
1 346 818
1 817 826
1 13 19
1 956 993
1 577 905
1 566 911
1 275 646
1 642 971
1 163 952
1 279 988
1 806 946
1 67 724
1 394 451
1 435 980
1 321 776
1 1 161
1 370 735
1 620 771
1 668 933
1 121 385
1 774 973
1 590 845
1 110 590
1 632 662
1 199 961
1 623 983
1 433 771
1 312 603
1 185 514
1 181 258
1 427 551
1 398 836
1 233 515
1 404 706
1 225 524
1 425 893
1 517 959
1 62 969
1 439 898
1 517 897
1 160 377
1 847 935
1 32 852
1 4 723
1 131 993
1 513 561
1 111 706
1 549 569
1 663 693
1 89 922
1 584 701
1 61 991
1 751 816
1 613 872
1 107 164
1 9 463
1 353 550
1 475 547
1 380 637
1 511 870
1 751 896
1 232 543
1 480 953
1 71 113
1 179 585
1 439 654
1 26 533
1 296 704
1 379 549
1 361 790
1 397 763
1 387 451
1 784 877
1 182 983
1 644 708
1 475 627
1 541 884
1 459 532
1 713 819
1 92 895
1 449 918
1 828 876
1 175 355
1 27 37
1 374 560
1 404 815
1 527 708
1 61 501
1 60 798
1 66 551
1 386 865
1 720 752
1 370 457
1 641 931
1 269 552
1 223 983
1 347 955
1 86 303
1 380 404
1 236 692
1 10 287
1 282 743
1 528 540
1 45 778
1 586 770
1 79 929
1 131 400
1 110 656
1 783 978
1 65 274
1 307 930
1 623 792
1 74 758
1 485 807
1 178 179
1 684 875
1 281 966
1 772 907
1 559 882
1 288 648
1 119 393
1 390 854
1 209 407
1 130 593
1 687 884
1 537 873
1 440 451
1 20 390
1 872 991
1 886 909
1 571 850
1 78 689
1 10 693
1 12 743
1 542 964
1 301 545
1 493 797
1 188 386
1 150 553
1 49 69
1 357 385
1 148 434
1 134 509
1 342 451
1 386 870
1 534 756
1 257 524
1 45 990
1 233 600
1 585 605
1 652 685
1 605 994
1 63 120
1 290 622
1 81 864
1 174 657
1 321 705
1 573 608
1 47 689
1 171 870
1 574 989
1 140 321
1 232 301
1 181 746
1 310 673
1 970 977
1 191 832
1 172 456
1 227 295
1 7 582
1 42 654
1 355 570
1 217 657
1 229 542
1 109 157
1 202 493
1 571 873
1 696 789
1 347 661
1 261 366
1 814 970
1 172 388
1 232 758
1 353 406
1 192 237
1 753 938
1 687 782
1 14 349
1 339 770
1 342 964
1 758 928
1 206 316
1 181 652
1 142 549
1 94 914
1 104 712
1 112 882
1 409 817
1 332 506
1 84 979
1 216 978
1 159 163
1 143 214
1 239 657
1 745 995
1 197 828
1 882 940
1 497 796
1 374 589
1 690 700
1 525 665
1 27 749
1 645 661
1 636 675
1 16 281
1 431 627
1 239 987
1 614 760
1 264 796
1 78 106
1 153 170
1 320 634
1 497 847
1 159 269
1 246 691
1 645 946
1 290 735
1 449 527
1 331 487
1 260 323
1 658 876
1 221 863
1 283 468
1 551 626
1 49 742
1 325 920
1 486 723
1 520 619
1 138 183
1 172 726
1 45 66
1 22 278
1 404 793
1 150 980
1 112 691
1 778 837
1 525 857
1 702 970
1 85 859
1 433 692
1 717 966
1 156 499
1 53 119
1 140 400
1 230 656
1 701 885
1 187 929
1 285 718
1 216 684
1 275 781
1 35 313
1 124 238
1 285 566
1 389 940
1 300 896
1 99 702
1 913 993
1 488 750
1 32 37
1 268 576
1 74 139
1 96 767
1 58 60
1 194 902
1 225 772
1 495 560
1 13 703
1 314 331
1 594 913
1 714 846
1 117 411
1 108 553
1 213 487
1 3 105
1 432 436
1 701 945
1 209 581
1 648 900
1 220 462
1 17 555
1 4 66
1 501 577
1 315 800
1 22 446
1 278 709
1 724 868
1 198 237
1 295 651
1 29 380
1 669 877
1 347 415
1 135 399
1 243 755
1 106 985
1 188 831
1 8 78
1 118 226
1 233 876
1 102 890
1 40 839
1 215 917
1 152 985
1 763 972
1 73 686
1 64 990
1 497 675
1 294 810
1 449 824
1 307 696
1 327 667
1 5 200
1 87 246
1 597 606
1 396 509
1 293 863
1 697 867
1 15 63
1 8 16
1 154 418
1 418 785
1 452 543
1 811 917
1 87 966
1 248 545
1 211 820
1 395 843
1 806 933
1 492 870
1 174 294
1 563 894
1 185 530
1 349 554
1 16 335
1 612 748
1 94 930
1 379 501
1 539 596
1 361 643
1 255 828
1 67 613
1 387 586
1 205 564
1 76 368
1 20 932
1 211 728
1 87 508
1 408 846
1 121 150
1 263 553
1 816 980
1 770 901
1 191 549
1 141 353
1 381 675
1 267 867
1 51 315
1 179 186
1 226 896
1 498 693
1 365 636
1 268 723
1 518 922
1 556 775
1 215 405
1 230 534
1 158 818
1 322 950
1 458 524
1 154 955
1 437 506
1 112 733
1 677 908
1 188 992
1 654 771
1 548 953
1 580 673
1 254 519
1 23 391
1 451 971
1 283 352
1 653 673
1 686 935
1 460 830
1 250 868
1 340 500
1 967 991
1 376 490
1 481 889
1 759 800
1 246 881
1 778 925
1 298 603
1 344 781
1 538 967
1 308 783
1 44 863
1 279 679
1 62 857
1 106 621
1 342 773
1 145 438
1 142 194
1 414 440
1 725 986
1 353 819
1 603 904
1 3 18
1 173 414
1 73 407
1 16 166
1 539 577
1 286 798
1 348 899
1 681 990
1 451 959
1 77 538
1 459 670
1 824 967
1 659 809
1 564 930
1 377 912
1 313 953
1 361 982
1 323 480
1 208 682
1 13 49
1 329 567
1 39 595
1 386 745
1 646 952
1 485 996
1 443 450
1 577 849
1 22 466
1 534 874
1 679 889
1 305 729
1 49 648
1 197 524
1 760 804
1 209 497
1 136 476
1 410 906
1 618 656
1 331 844
1 213 350
1 409 819
1 152 473
1 928 992
1 756 933
1 512 989
1 230 287
1 254 609
1 306 857
1 301 321
1 691 951
1 73 482
1 330 635
1 479 554
1 330 704
1 31 600
1 471 833
1 568 953
1 25 72
1 114 813
1 668 708
1 369 420
1 312 935
1 537 945
1 368 447
1 206 501
1 92 330
1 312 412
1 268 546
1 173 284
1 385 597
1 645 762
1 68 121
1 273 795
1 59 689
1 229 658
1 232 600
1 166 320
1 181 780
1 355 886
1 130 654
1 448 480
1 666 895
1 131 536
1 167 494
1 59 495
1 773 898
1 227 790
1 583 933
1 15 492
1 742 896
1 288 776
1 66 627
1 435 609
1 399 509
1 277 378
1 45 426
1 47 633
1 177 854
1 82 281
1 18 864
1 845 910
1 73 172
1 38 561
1 402 502
1 497 733
1 31 792
1 699 750
1 696 957
1 531 836
1 849 879
1 24 293
1 223 638
1 272 517
1 55 391
1 296 561
1 118 762
1 37 420
1 841 939
1 175 584
1 155 814
1 446 947
1 452 465
1 418 806
1 495 961
1 257 258
1 103 736
1 535 958
1 692 745
1 381 568
1 580 808
1 111 384
1 160 463
1 417 938
1 720 938
1 306 441
1 592 668
1 519 735
1 393 477
1 568 597
1 8 424
1 289 600
1 502 730
1 589 886
1 672 889
1 466 505
1 224 970
1 319 343
1 310 616
1 460 770
1 434 732
1 448 583
1 237 692
1 277 327
1 413 720
1 616 660
1 297 432
1 6 824
1 179 634
1 240 878
1 983 997
1 816 942
1 475 722
1 5 59
1 27 152
2
681760845