题目描述
Russian version of the problem can be read here.
There are N boxes where cats can sleep and eat, numbered from the left to the right starting from 1. Each box contains some type of food, which is a positive integer. Initially, the i-th box contains food of type A[i].
A cat will occupy some consecutive subset of boxes, and all the food in the subset must be of the same type.
M events happened. There are events of two types:
Change the food type to type c in all boxes with indices from l to r, inclusve.
Count the number of possible subsets a cat can choose, considering that he is allowed to occupy only boxes with indices from l to r, inclusve.
Your task is to process all the given events.
Input format
The first line of the input contains two integers N and M. The second line contains N space separated integers, which are the array A[i]. The following M lines contain desription of the events, in chronological order. Each line is if format "0 l r c" in case of an event of the first type, and "1 l r" in case of the second one.
Output format
For each event of the second type print the answer to the corresponding event.
Constraints
1 ≤ N, M ≤ 100,000, all types of food are integers between 1 and 1,000,000,000.
SAMPLE INPUT
7 7
1 2 1 1 1 3 3
1 1 7
1 4 7
0 2 6 2
1 1 7
1 2 6
0 2 3 7
1 1 7
SAMPLE OUTPUT
11
6
17
15
11
输入格式
见题面
输出格式
见题面
样例输入
590 679
106 45 744 408 887 860 42 905 760 78 105 255 958 463 714 906 185 264 940 783 884 509 442 821 460 133 990 471 614 368 327 896 713 990 10 603 373 440 292 52 880 399 874 9 240 387 273 34 715 234 950 222 597 394 807 710 608 475 648 192 780 182 876 323 430 140 540 953 550 425 56 517 500 847 547 659 193 172 694 956 683 149 127 582 112 355 756 553 797 66 225 853 656 280 993 172 688 249 602 223 521 980 961 687 537 639 775 86 93 927 711 800 846 916 80 737 866 482 669 296 716 436 692 235 303 920 558 642 110 925 56 932 221 471 101 846 672 24 328 391 328 936 212 192 531 994 331 92 174 187 489 734 531 632 857 677 697 591 520 285 918 606 287 567 898 122 924 936 786 703 976 142 345 434 872 290 246 212 482 459 665 528 933 275 569 242 606 622 348 187 411 376 266 450 462 925 313 982 27 674 659 710 21 500 827 233 851 96 554 236 984 713 113 715 687 185 401 757 932 81 599 501 835 435 189 321 309 595 990 843 100 778 39 566 110 210 982 180 333 217 222 641 331 573 730 408 673 886 21 621 601 10 493 859 719 596 518 880 946 701 385 194 317 641 178 151 287 933 211 423 959 844 364 293 955 648 657 720 901 140 773 385 242 448 646 603 629 374 83 421 136 438 108 290 477 114 720 177 804 78 587 696 404 162 784 186 937 821 15 305 578 70 468 69 191 585 573 466 827 814 671 972 15 963 512 33 58 322 997 638 952 976 128 184 350 311 543 912 51 658 265 976 189 200 907 245 584 913 231 684 262 730 697 477 253 803 369 62 842 818 525 530 32 358 605 199 921 970 510 113 151 826 133 142 56 994 663 597 880 997 550 128 879 64 269 598 655 675 109 992 764 175 430 627 828 559 867 510 893 850 952 699 300 364 473 431 567 408 856 469 843 328 809 12 58 37 17 375 937 139 273 844 564 782 426 343 942 989 300 706 358 448 911 304 73 415 101 943 468 425 926 498 175 289 457 441 623 101 780 30 59 134 794 799 863 84 754 184 617 341 523 255 550 627 453 184 296 976 407 399 397 168 175 475 364 449 58 277 422 815 562 316 908 880 118 177 191 585 65 492 477 773 785 318 7 57 696 876 659 888 135 563 489 566 996 396 863 240 460 212 832 776 259 709 208 434 812 775 596 578 306 510 176 917 430 572 711 495 778 800 922 86 416 948 127 650 823 814 497 818 634 162 103 705 561 775 454 306 201 65 21 758 851 954 575 358 274 788 742 369 775 803 407 881 675 264 233 292 224 73 804 904 163 467 239 885 863 212 804 239 799 726 384 22 642 940 284 969 308 83
1 444 535
0 483 513 325
0 429 454 434
0 269 340 618
1 406 412
1 151 205
0 426 493 174
0 524 589 996
1 20 42
0 225 245 629
0 219 304 127
0 40 118 377
1 113 180
0 21 70 661
0 529 569 100
0 394 480 120
0 319 377 353
0 96 131 170
1 434 501
0 281 299 143
1 90 135
1 406 467
1 107 204
1 23 75
0 114 212 120
1 317 407
1 317 416
1 339 383
1 356 388
0 24 95 482
0 24 74 429
0 297 374 785
0 473 479 975
1 436 523
1 359 372
1 58 75
1 338 395
0 124 186 783
1 32 96
1 489 569
1 71 135
0 140 207 222
1 475 476
0 256 334 717
1 457 462
0 342 403 506
0 418 493 810
0 486 507 108
1 210 257
0 133 186 200
1 387 427
1 61 88
0 221 296 802
1 222 320
1 132 180
0 96 157 975
0 215 284 264
0 112 135 906
0 289 328 891
0 161 230 578
1 76 164
1 238 330
1 155 195
1 85 170
1 260 349
1 58 123
0 21 82 604
1 418 434
0 423 471 755
1 519 569
1 317 395
0 500 542 425
0 38 126 861
1 339 431
1 3 11
1 137 158
1 437 513
1 11 84
1 185 196
1 189 278
1 400 475
0 420 436 378
0 44 107 791
0 520 572 615
0 434 532 277
1 135 149
1 470 505
0 245 265 375
1 477 538
0 572 578 873
0 119 142 875
0 417 421 64
0 165 204 487
0 39 101 773
1 392 425
0 56 94 174
0 470 489 397
1 389 466
1 112 117
0 361 389 81
0 331 344 677
0 295 343 496
0 409 412 82
1 85 154
0 357 417 407
0 169 241 625
1 311 327
1 185 207
1 41 96
1 441 473
1 337 404
1 495 517
0 427 525 284
0 203 267 330
0 378 412 947
1 160 243
0 176 194 665
0 295 324 117
1 128 184
1 241 334
0 262 300 970
1 297 385
1 175 261
0 13 74 151
0 202 204 265
1 19 46
1 80 163
0 253 332 943
1 69 152
1 380 395
1 483 577
0 211 302 922
0 240 310 462
0 88 122 220
0 98 137 839
0 194 225 968
1 210 278
1 312 366
1 180 235
1 285 336
1 99 139
0 140 193 294
1 198 199
1 439 536
0 116 198 819
1 185 202
0 10 97 482
0 187 233 899
0 306 397 759
1 493 514
1 262 345
1 547 583
1 120 198
1 471 500
0 171 214 497
0 280 347 530
1 406 449
0 143 191 975
1 469 536
0 17 79 950
0 366 421 455
0 33 93 126
1 420 430
1 461 548
0 186 267 824
1 456 484
1 271 345
1 539 543
0 415 479 291
0 451 461 300
0 523 582 127
1 205 278
0 122 126 904
0 472 544 973
1 411 471
1 51 75
1 410 422
0 248 276 559
0 321 398 86
1 353 443
1 106 129
0 291 341 811
0 517 543 252
0 264 353 847
1 77 144
0 420 517 964
1 129 153
1 125 206
1 301 368
1 402 463
0 123 124 609
0 369 429 951
1 106 138
0 504 589 419
1 338 359
1 492 560
1 112 117
1 22 38
1 469 503
1 446 544
1 144 212
1 168 234
1 394 452
0 297 321 661
1 454 468
1 224 306
0 120 140 207
0 401 419 323
1 270 356
1 503 556
1 137 142
0 332 430 501
0 183 255 262
0 119 191 137
1 435 454
0 18 36 319
0 237 326 359
0 226 234 671
1 315 394
1 223 264
0 435 457 858
1 121 178
0 429 431 527
0 236 273 97
0 494 556 135
1 251 281
0 57 118 744
0 147 187 113
1 411 482
1 502 550
0 290 347 263
1 353 364
1 489 513
0 113 113 56
0 497 560 271
0 194 258 669
0 477 535 145
1 140 223
0 87 141 933
0 296 379 801
0 4 73 130
1 424 469
1 518 529
1 64 76
1 72 96
0 215 244 671
0 13 95 528
0 271 336 220
1 138 232
1 275 329
0 117 209 479
1 467 515
0 276 358 475
1 450 482
0 373 414 33
0 213 227 750
1 288 356
0 457 469 158
1 52 102
0 390 395 860
0 372 391 241
1 414 467
0 136 221 176
1 164 259
0 464 484 917
1 530 584
1 43 97
0 324 355 552
1 73 86
0 211 273 569
0 20 54 164
1 129 221
0 284 331 617
0 253 319 754
0 222 270 359
0 467 562 321
1 224 267
0 363 370 275
1 121 194
0 134 140 911
0 492 508 815
1 112 185
0 364 406 258
1 66 161
1 177 263
1 541 577
0 440 444 359
1 177 266
0 349 437 317
1 158 212
0 253 350 989
1 154 171
1 514 533
0 177 197 321
1 150 160
0 270 324 194
0 55 116 201
0 315 409 751
0 267 269 370
0 300 313 576
0 455 526 152
0 461 502 748
0 271 312 458
1 409 418
1 443 531
1 2 86
0 130 145 957
0 105 169 337
1 469 514
1 263 359
0 354 430 969
1 101 194
0 70 159 385
0 125 156 793
1 560 590
0 439 445 124
1 249 305
1 398 408
1 227 265
0 134 199 57
1 250 277
1 416 492
0 190 258 641
1 37 56
0 301 398 743
0 95 100 121
1 14 34
1 87 87
0 392 394 734
1 133 182
0 362 423 491
1 458 527
1 280 289
1 201 238
1 260 323
0 333 410 608
1 62 157
0 101 106 921
1 19 63
0 109 118 435
1 119 207
0 276 290 115
1 115 178
1 432 502
0 344 347 125
0 448 498 808
1 304 332
0 317 375 510
0 304 373 838
1 7 15
1 480 543
1 377 409
0 195 247 680
0 431 480 658
0 366 406 853
0 378 433 481
0 102 189 329
1 223 223
0 75 84 367
0 292 359 861
0 230 253 124
0 70 108 752
0 446 535 489
1 94 103
0 18 85 514
0 315 352 437
1 25 99
0 378 457 385
0 459 475 523
0 517 565 579
0 367 462 366
0 96 172 727
0 7 45 973
1 366 434
0 102 146 133
0 489 498 408
0 490 540 239
1 185 221
0 378 385 416
0 360 440 104
0 42 77 71
1 224 225
1 38 70
1 37 73
0 96 135 978
0 376 456 488
0 204 221 254
0 260 350 524
1 127 134
1 223 284
0 72 161 983
0 374 403 299
1 498 522
1 488 517
0 372 440 192
1 547 563
0 394 470 457
1 55 86
1 204 261
1 452 463
0 86 142 950
0 305 312 595
1 205 245
0 322 369 404
1 285 294
1 482 522
1 454 493
0 186 202 877
1 206 216
1 408 507
0 321 339 658
0 422 480 322
0 426 452 620
1 458 485
1 414 483
1 344 384
0 362 455 352
0 463 558 791
0 333 390 201
1 201 207
1 411 423
1 326 374
1 371 399
0 186 266 549
1 58 103
1 176 198
0 140 190 120
1 287 343
0 260 355 311
1 318 368
1 203 291
0 472 546 662
1 265 338
0 335 408 330
1 478 548
0 523 538 261
0 169 228 933
1 462 557
0 168 196 982
1 110 111
0 180 227 137
0 357 405 851
0 336 427 12
1 82 126
0 393 403 633
0 470 537 665
0 263 342 738
1 56 144
0 288 359 494
0 89 164 745
0 448 492 976
1 363 460
0 403 502 466
1 4 91
1 381 399
0 335 389 162
0 25 117 549
1 407 460
0 169 224 203
0 209 252 36
0 205 205 660
0 454 454 947
0 494 516 399
1 376 388
1 210 293
1 76 76
0 146 244 81
0 444 541 488
0 211 254 682
1 281 356
1 299 356
0 229 233 860
1 68 115
1 190 249
0 37 115 494
1 92 146
1 118 212
1 119 134
1 567 575
1 212 247
0 235 304 972
1 545 586
1 489 555
0 146 231 636
1 298 320
0 135 197 678
0 558 579 254
1 83 126
1 473 542
1 450 483
1 101 137
0 186 275 811
0 378 446 410
0 473 561 842
0 336 353 623
1 338 410
0 85 114 671
0 150 186 546
0 521 533 835
0 68 69 257
0 479 578 700
0 503 511 531
0 207 239 212
1 317 388
1 418 515
0 474 539 366
1 71 142
0 270 359 525
1 148 158
0 31 35 41
0 14 109 508
1 107 148
0 112 134 437
1 443 530
0 417 494 566
0 470 538 1
0 204 255 675
0 138 143 478
0 379 436 485
0 327 360 349
0 189 205 136
1 541 590
0 299 310 154
0 394 492 348
0 38 130 695
1 410 504
1 452 510
0 448 480 65
0 412 421 626
1 512 539
1 268 363
0 383 390 172
0 186 238 713
1 347 347
1 341 368
1 359 411
0 508 581 850
0 8 48 470
1 48 89
1 261 335
0 412 509 52
1 269 307
0 374 406 849
0 60 111 720
0 336 425 658
0 307 341 646
1 523 539
1 65 89
0 323 351 354
1 39 39
1 62 120
1 373 447
0 125 150 374
1 255 336
1 267 350
0 427 482 922
1 268 328
1 500 529
0 400 473 110
0 257 268 972
1 189 269
1 396 448
1 304 362
0 287 352 345
1 227 243
0 169 220 811
0 155 177 84
0 273 290 910
1 305 345
1 5 31
0 422 507 602
0 494 579 741
0 335 408 277
0 450 541 952
1 561 579
1 282 313
0 186 250 937
1 441 502
1 494 581
1 401 422
1 180 263
1 482 565
1 478 512
0 296 331 72
1 290 365
1 325 402
0 380 412 290
1 294 374
0 535 574 22
0 209 227 220
1 206 241
1 98 105
1 492 550
0 219 230 712
1 205 216
0 82 110 548
1 308 359
0 375 474 913
1 277 296
0 493 583 284
0 73 79 621
1 162 191
0 278 329 39
0 178 209 197
1 367 437
1 492 580
0 156 173 665
0 382 406 407
0 423 515 980
0 453 549 149
1 424 451
0 129 220 718
1 160 178
1 110 114
0 84 123 57
1 198 232
1 2 71
1 438 483
1 332 374
0 169 249 671
1 189 281
0 327 360 100
1 44 88
1 269 308
1 215 312
1 108 161
1 212 227
0 75 126 765
1 454 523
0 379 465 419
0 296 342 15
1 282 367
0 295 310 738
0 208 227 772
1 16 59
1 340 377
1 130 177
0 331 390 17
1 92 170
1 414 416
0 362 375 511
0 533 569 839
1 125 175
0 194 209 135
0 350 442 387
1 371 400
0 16 97 456
1 449 495
1 424 461
1 108 143
1 203 264
1 354 431
0 152 179 27
1 114 143
0 423 444 301
0 249 318 470
1 512 588
0 521 555 902
0 481 574 493
0 143 241 424
1 496 506
0 422 468 495
1 75 114
1 239 245
0 155 228 551
0 404 488 869
1 217 256
0 562 581 195
0 219 289 406
0 235 276 455
1 379 412
0 371 467 256
0 293 331 157
1 306 388
0 537 575 485
1 430 441
1 380 460
0 320 327 963
1 257 267
样例输出
92
7
55
23
83
1255
691
1953
398
1191
1894
2065
786
264
1043
105
154
728
1178
1111
545
3
21
718
313
210
3150
1177
915
1961
642
816
1240
598
153
881
1612
2124
9
232
945
1291
78
2079
1365
106
666
1617
194
865
21
548
153
276
903
445
1283
276
1477
339
1082
846
1997
406
667
701
136
1775
1021
431
688
614
783
3
3866
115
253
1810
368
2356
465
344
1691
28
2309
435
2256
15
2082
797
325
51
1652
97
509
171
1316
1551
1096
161
157
1731
13
87
630
2572
1281
1396
942
120
1052
1237
1432
13
210
2109
460
1711
312
784
1225
78
225
1367
381
78
61
149
1301
1540
835
247
2415
1018
437
1991
646
1434
105
2944
990
1890
1231
1108
1564
373
1696
1434
171
210
66
46
1297
1233
673
1957
2354
385
752
66
442
146
771
174
141
1
1226
1210
55
741
776
1027
676
1833
1111
1019
435
27
653
561
1
55
1996
2347
408
3
445
543
36
669
325
408
153
273
526
78
325
55
590
270
66
2294
291
836
445
14
91
931
255
381
146
387
832
2181
2775
2418
1610
3
871
1741
1132
1218
106
1485
91
1326
1
1409
919
1176
553
710
2554
136
45
273
340
1491
164
609
2416
595
282
997
709
1162
763
48
283
2015
798
3564
1032
379
1253
1
246
380
862
739
481
153
325
1
1320
1684
818
1019
631
265
1508
1235
643
93
861
304
190
321
1476
1920
128
2210
2130
630
1184
2380
1495
301
36
1082
46
631
121
193
2052
3917
406
190
8
334
1014
616
826
2018
221
518
1377
708
136
2485
1432
627
288
825
1456
6
854
465
618
380
313
505
3081
214
1054
66
429
16
233
370
924
78
3321
66