TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1316
  • 题目
  • P1316小白逛公园
    限制 : 时间限制 : 20000 MS   空间限制 : 565536 KB
    问题描述

    小新经常陪小白去公园玩,也就是所谓的遛狗啦…在小新家附近有一条“公园路”,路的一边从南到北依次排着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


    来源  vijos