FJUT3568 中二病也要敲代码（线段树维护区间连续最值）题解

时间：2021-07-14 15:54:20

题意：有一个环，有1~N编号，m次操作，将a位置的值改为b，问你这个环当前最小连续和多少（不能全取也不能不取）

思路：用线段树维护一个区间最值连续和。我们设出两个变量Lmin，Rmin，Mmin表示区间左边最小连续和，右边最小连续和，区间最小连续和，显然这可以通过这个方式更新维护。

FJUT3568 中二病也要敲代码（线段树维护区间连续最值）题解

现在我们已经可以维护一个区间最值连续和了，那么怎么求“环”的最小连续和呢？显然如果最小区间横跨1和n是不能表示出来的（比如最小区间是2，1，n，n-1之和），那么我们可以转化为求sum-Mmax即区间和减去区间最大值，那么显然最终答案是min( sum[1] - Mmax[1], Mmin[1] )，但由题意“不能全取也不能不取”，那么特判。

好久没做线段树维护连续区间的题了...

代码：

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<stdio.h>

#include<string.h>

#include<queue>

#include<cmath>

#include<map>

#include<set>

#include<vector>

using namespace std;

#define inf 0x3f3f3f3f

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define mem(a,b) memset(a,b,sizeof(a));

#define lowbit(x)  x&-x;

typedef long long ll;

typedef unsigned long long ull;

const double eps = 1e-;

const int maxn = 1e5+;

const ll mod = 1e8+;

ll Lmax[maxn << ], Rmax[maxn << ], Mmax[maxn << ], sum[maxn << ];

ll Lmin[maxn << ], Rmin[maxn << ], Mmin[maxn << ];

ll a[maxn];

void push_up(int rt){

    Lmax[rt] = max(Lmax[rt << ], sum[rt << ] + Lmax[rt <<  | ]);

    Rmax[rt] = max(Rmax[rt <<  | ], sum[rt <<  | ] + Rmax[rt << ]);

    Mmax[rt] = max(max(Mmax[rt << ], Mmax[rt <<  | ]), Rmax[rt << ] + Lmax[rt <<  | ]);

    Lmin[rt] = min(Lmin[rt << ], sum[rt << ] + Lmin[rt <<  | ]);

    Rmin[rt] = min(Rmin[rt <<  | ], sum[rt <<  | ] + Rmin[rt << ]);

    Mmin[rt] = min(min(Mmin[rt << ], Mmin[rt <<  | ]), Rmin[rt << ] + Lmin[rt <<  | ]);

    sum[rt] = sum[rt << ] + sum[rt <<  | ];

}

void build(int l, int r, int rt){

    if(l == r){

        Mmax[rt] = Rmax[rt] = Lmax[rt] = Mmin[rt] = Rmin[rt] = Lmin[rt] = sum[rt] = a[l];

        return;

    }

    int m = (l + r) >> ;

    build(l, m, rt << );

    build(m + , r, rt <<  | );

    push_up(rt);

}

void update(int pos, int l, int r, int v, int rt){

    if(l == r){

        Mmax[rt] = Rmax[rt] = Lmax[rt] = Mmin[rt] = Rmin[rt] = Lmin[rt] = sum[rt] = v;

        return;

    }

    int m = (l + r) >> ;

    if(pos <= m)

        update(pos, l, m, v, rt << );

    else

        update(pos, m + , r, v, rt <<  | );

    push_up(rt);

}

int main(){

    int n, m, A;

    ll B;

    while(~scanf("%d", &n)){

        for(int i = ; i <= n; i++){

            scanf("%lld", &a[i]);

        }

        build(, n, );

        scanf("%d", &m);

        while(m--){

            ll MAX, MIN, ans;

            scanf("%d%lld", &A, &B);

            update(A, , n, B, );

            if(Mmax[] == sum[]){

                ans = Mmin[];

            }

            else if(Mmin[] == sum[]){

                ans = Mmin[] - Mmax[];

            }

            else{

                ans = min(sum[] - Mmax[], Mmin[]);

            }

            printf("%lld\n", ans);

        }

    }

    return ;

}

相关文章