img sum 最大 %d using syn scan ide pen
小新经常陪小白去公园玩,也就是所谓的遛狗啦…在小新家附近有一条“公园路”,路的一边从南到北依次排着n个公园,小白早就看花了眼,自己也不清楚该去哪些公园玩了。
一开始,小白就根据公园的风景给每个公园打了分-.-。小新为了省事,每次遛狗的时候都会事先规定一个范围,小白只可以选择第a个和第b个公园之间(包括a、b两个公园)选择**连续**的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时,由于一些公园的景观会有所改变,所以,小白的打分也可能会有一些变化。
那么,就请你来帮小白选择公园吧。
第一行,两个整数N和M,分别表示表示公园的数量和操作(遛狗或者改变打分)总数。
接下来N行,每行一个整数,依次给出小白 开始时对公园的打分。
接下来M行,每行三个整数。第一个整数K,1或2。K=1表示,小新要带小白出去玩,接下来的两个整数a和b给出了选择公园的范围(1≤a,b≤N, a可以大于b!);K=2表示,小白改变了对某个公园的打分,接下来的两个整数p和s,表示小白对第p个公园的打分变成了s(1≤p≤N)。
其中,1≤N≤500 000,1≤M≤100 000,所有打分都是绝对值不超过1000的整数。
小白每出去玩一次,都对应输出一行,只包含一个整数,表示小白可以选出的公园得分和的最大值。
- 5 3
- 1 2 -3 4 5
- 1 2 3
- 2 2 -1
- 1 2 3
- 2
- -1
各个测试点2s
--------------
解:线段树;
e数组维护lsum,rsum,msum,sum;
难在query函数,简单情况大家都懂,难的解决方法是:
开三个结构体:tl,tr,tt;
tl:左边对应的情况;
tr:同上;
tt:即为答案;
- #include < cstdio > #include < cstring > #include < algorithm > #define ll long long using std: :max;
- using std: :swap;
- const int N = 500010;
- struct node {
- int l,
- r,
- lsum,
- rsum,
- msum,
- sum;
- }
- e[N << 2];#define ls ro << 1#define rs ro << 1 | 1 inline void pushup(int ro) {
- e[ro].sum = e[ls].sum + e[rs].sum;
- e[ro].lsum = max(e[ls].lsum, e[ls].sum + e[rs].lsum);
- e[ro].rsum = max(e[rs].rsum, e[rs].sum + e[ls].rsum);
- e[ro].msum = max(max(e[ls].msum, e[rs].msum), e[ls].rsum + e[rs].lsum);
- }
- void build(int ro, int l, int r) {
- e[ro].l = l,
- e[ro].r = r;
- if (l == r) {
- int x;
- scanf("%d", &x);
- e[ro].lsum = e[ro].rsum = e[ro].msum = e[ro].sum = x;
- return;
- }
- int mid = (l + r) >> 1;
- build(ls, l, mid);
- build(rs, mid + 1, r);
- pushup(ro);
- }
- void change(int ro, int x, int p) {
- if (e[ro].l == e[ro].r) {
- if (e[ro].l == x) e[ro].lsum = e[ro].rsum = e[ro].msum = e[ro].sum = p;
- return;
- }
- int mid = (e[ro].l + e[ro].r) >> 1;
- if (x <= mid) change(ls, x, p);
- else change(rs, x, p);
- pushup(ro);
- }
- node query(int ro, int l, int r) {
- node tl,
- tr,
- tt;
- if (e[ro].l == l && e[ro].r == r) return e[ro];
- int mid = (e[ro].l + e[ro].r) >> 1;
- if (r <= mid) return query(ls, l, r);
- else if (mid < l) return query(rs, l, r);
- else {
- tl = query(ls, l, mid);
- tr = query(rs, mid + 1, r);
- tt.msum = max(max(tl.msum, tr.msum), tl.rsum + tr.lsum);
- tt.lsum = max(tl.lsum, tl.sum + tr.lsum);
- tt.rsum = max(tr.rsum, tr.sum + tl.rsum);
- return tt;
- }
- }
- int main() {
- int n,
- m;
- scanf("%d %d", &n, &m);
- build(1, 1, n);
- // for(int i=1;i<=20;i++)
- // printf("std:: %d %d %d %d %d %d\n",e[i].l,e[i].r,e[i].lsum,e[i].rsum,e[i].msum,e[i].sum);
- int dp,
- l,
- r;
- for (int i = 1; i <= m; i++) {
- scanf("%d %d %d", &dp, &l, &r);
- if (dp == 1) {
- if (l > r) swap(l, r);
- node ans = query(1, l, r);
- printf("%d\n", ans.msum);
- } else {
- change(1, l, r);
- // for(int i=1;i<=20;i++)
- // printf("std:: %d %d %d %d %d %d\n",e[i].l,e[i].r,e[i].lsum,e[i].rsum,e[i].msum,e[i].sum);
- }
- }
- return 0;
- }
vijos 1083 小白逛公园
来源: http://www.bubuko.com/infodetail-2356235.html