中文
日本語
English
| P1316小白逛公园 | |
|
问题描述
小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。
一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。
那么，就请你来帮小白选择公园吧。
输入格式
第一行，两个整数N和M，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。
接下来N行，每行一个整数，依次给出小白 开始时对公园的打分。
接下来M行，每行三个整数。第一个整数K，1或2。K=1表示，小新要带小白出去玩，接下来的两个整数a和b给出了选择公园的范围（1≤a,b≤N）；K=2表示，小白改变了对某个公园的打分，接下来的两个整数p和s，表示小白对第p个公园的打分变成了s（1≤p≤N）。
其中，1≤N≤500 000，1≤M≤100 000，所有打分都是绝对值不超过1000的整数。
输出格式
小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。
样例输入 1
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 2 3
样例输出 1
2
-1
样例输入 2
50 100
773
760
-578
-302
-664
272
367
352
891
-569
429
-208
-325
38
148
456
-960
-390
470
271
763
-458
-52
647
-205
-514
399
-611
882
665
257
-718
233
-756
237
-301
650
148
-894
-212
-820
-341
-240
-620
320
932
-498
-252
323
-428
2 5 818
1 35 49
2 15 -87
1 31 48
1 44 37
1 10 25
2 28 -761
2 38 913
1 28 30
1 25 38
2 26 996
1 35 22
2 27 59
2 49 -754
2 7 -366
2 3 -822
1 22 3
2 12 516
1 7 30
2 5 -693
2 22 -193
2 33 -474
1 1 3
1 37 35
2 39 829
2 28 865
1 37 20
1 38 42
1 17 5
1 38 5
2 41 -553
1 18 9
1 18 16
2 48 -20
2 10 -875
1 20 13
1 38 1
1 15 44
2 36 -247
1 11 32
2 18 -703
2 47 -24
1 39 15
1 9 2
1 7 32
1 36 6
2 19 253
2 40 -624
1 12 45
1 25 37
1 4 3
1 40 27
1 28 45
2 6 -851
2 10 410
1 31 48
2 25 -307
2 27 -704
1 25 7
1 35 12
1 17 24
1 29 21
1 15 5
2 18 -70
2 17 568
1 12 45
2 13 -276
2 21 -862
2 47 -513
2 24 -700
1 10 42
1 26 15
2 27 238
2 39 -264
1 10 8
2 8 -5
1 33 34
2 23 665
2 38 -646
1 8 35
2 1 -834
2 2 -908
2 3 -702
2 4 -994
2 5 -883
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
1 2 1
1 3 2
1 4 3
1 5 4
1 3 1
1 4 2
1 5 3
1 4 1
1 5 2
1 5 1
样例输出 2
1252
1252
798
1641
1547
2062
2880
1967
3628
1533
650
4955
1742
1701
5776
1349
456
741
5470
5805
5425
5859
1243
5425
5425
5642
3724
-302
3162
3103
2392
2706
4343
1689
2897
2598
5873
3789
1478
1653
-474
5905
-834
-908
-702
-994
-883
-834
-702
-702
-883
-702
-702
-702
-702
-702
-702