lsum 、lmax 、rsum 、 rmax 都是代表着从最左边开始或者从最右边开始

第一类：

仅仅要求求解的区间要求是连续的

我们考虑设置三个变量 lsum , rsum , sum 分别记录从左边开始的连续区间大小，从右边开始的连续区间的大小，整个区间的连续区间的大小的最大值

然后我们采取线段树去维护这三个变量就可以了

 

因为我们要求的是连续的区间，所以我们 pushup 操作的时候也需要确保我们的区间是连续的

sum 维护的是整个范围内最大的连续区间 ： 左右两个区间最大的或者是在中间的某一段

 

 

这一类连续区间的求解问题的典型例题：

P2894 [USACO08FEB]Hotel G

题目链接：https://www.luogu.com.cn/problem/P2894

#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <ctime>
#include <bitset>
#include <cmath>
#include <sstream>
#include <iostream>
#include <unordered_map>

#define ll long long
#define ull unsigned long long
#define ls nod<<1
#define rs (nod<<1)+1
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define INF 0x3f3f3f3f3f3f3f3f
#define max(a, b) (a>b?a:b)
#define min(a, b) (a<b?a:b)


const double eps = 1e-10;
const int maxn = 5e4 + 10;
const ll MOD = 99999999999999;

int sgn(double a) { return a < -eps ? -1 : a < eps ? 0 : 1; }

using namespace std;

int sum[maxn << 2],lazy[maxn << 2];
int lsum[maxn << 2],rsum[maxn << 2];

void build(int l,int r,int nod) {
    sum[nod] = lsum[nod] = rsum[nod] = (r-l+1);
    lazy[nod] = -1;
    if (l == r)
        return ;
    int mid = (l + r) >> 1;
    build(l,mid,ls);
    build(mid+1,r,rs);
}

void pushup(int l,int r,int nod) {
    int mid = (l + r) >> 1;
    sum[nod] = max(max(sum[ls],sum[rs]),rsum[ls] + lsum[rs]);
    lsum[nod] = lsum[ls];
    rsum[nod] = rsum[rs];
    if (lsum[ls] == (mid - l + 1))
        lsum[nod] = lsum[ls] + lsum[rs];
    if (rsum[rs] == (r - mid))
        rsum[nod] = rsum[rs] + rsum[ls];
}

void pushdown(int l,int r,int nod) {
    int mid = (l + r) >> 1;
    sum[ls] = lsum[ls] = rsum[ls] = (lazy[nod]) * (mid - l + 1);
    sum[rs] = lsum[rs] = rsum[rs] = (lazy[nod]) * (r - mid);
    lazy[ls] =lazy[rs] = lazy[nod];
    lazy[nod] = -1;
}
void modify(int l,int r,int x,int y,int z,int nod) {
    if (x <= l && y >= r) {
        sum[nod] = lsum[nod] = rsum[nod] = (r-l+1)*z;
        lazy[nod] = z;
        return ;
    }
    if (lazy[nod] != -1) {
        pushdown(l,r,nod);
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
        modify(l,mid,x,y,z,ls);
    if (y > mid)
        modify(mid+1,r,x,y,z,rs);
    pushup(l,r,nod);
}

int query(int l,int r,int siz,int nod) {
    int mid = (l + r) >> 1;
    if (l == r && siz == 1)
        return l;
    if (lazy[nod] != -1)
        pushdown(l,r,nod);
    if (sum[nod] >= siz) {
        if (sum[ls] >= siz) {
            return query(l,mid,siz,ls);
        }
        else if (rsum[ls] + lsum[rs] >= siz) {
            return mid + 1 - rsum[ls];
        }
        else
            return query(mid+1,r,siz,rs);
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    build(1,n,1);
    while (m--) {
        int op,x,y;
        cin >> op;
        if (op == 1) {
            cin >> x;
            int l = query(1,n,x,1);
            cout << l << endl;
            if (!l)
                continue;
            modify(1,n,l,l+x-1,0,1);
        }
        else {
            cin >> x >> y;
            modify(1,n,x,x+y-1,1,1);
        }
    }
    return 0;
}

 

第二类：

要求求解的连续区间是最大的

因为要求的连续区间是最大的，所以我们需要维护四个变量 sum , lmax , rmax , ans  分别代表区间和，左边连续区间的最大值，右边连续区间的最大值，整个区间的连续区间的最大值

因为我们要求的是连续的区间，所以我们 pushup 操作的时候也需要确保我们的区间是连续的

lmax 维护： 左区间的lmax和整个左区间 + 右区间的lmax 中的最大值

 

 这类问题的典型例题：

P4513 小白逛公园

题目链接：https://www.luogu.com.cn/problem/P4513

 

#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <ctime>
#include <bitset>
#include <cmath>
#include <sstream>
#include <iostream>
#include <unordered_map>

#define ll long long
#define ull unsigned long long
#define ls nod<<1
#define rs (nod<<1)+1
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define INF 0x3f3f3f3f
#define max(a, b) (a>b?a:b)
#define min(a, b) (a<b?a:b)


const double eps = 1e-10;
const int maxn = 5e5 + 10;
const ll MOD = 99999999999999;

int sgn(double a) { return a < -eps ? -1 : a < eps ? 0 : 1; }

using namespace std;

// #define int ll

int a[maxn];
struct segment_tree {
    int l,r;
    int sum,lmax,rmax,ans;
}tree[maxn << 2];


void pushup(int nod) {
    tree[nod].sum = tree[ls].sum + tree[rs].sum;
    tree[nod].lmax = max(tree[ls].lmax,tree[ls].sum + tree[rs].lmax);
    tree[nod].rmax = max(tree[rs].rmax,tree[rs].sum + tree[ls].rmax);
    tree[nod].ans = max(max(tree[ls].ans,tree[rs].ans),tree[ls].rmax + tree[rs].lmax);
}

void build(int l,int r,int nod) {
    tree[nod].l = l,tree[nod].r = r;
    if (l == r) {
        tree[nod].ans = tree[nod].lmax = tree[nod].rmax = tree[nod].sum = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    pushup(nod);
}

void modify(int k,int z,int nod) {
    int l = tree[nod].l,r = tree[nod].r;
    if (l == r) {
        tree[nod].ans = tree[nod].lmax = tree[nod].rmax = tree[nod].sum = z;
        return ;
    }
    int mid = (l + r) >> 1;
    if (k <= mid)
        modify(k,z,ls);
    if (k > mid)
        modify(k,z,rs);
    pushup(nod);
}

segment_tree query(int x,int y,int nod) {
    int l = tree[nod].l,r = tree[nod].r;
    if (x <= l && y >= r)
        return tree[nod];
    int mid = (l + r) >> 1;
    if (y <= mid)
        return query(x,y,ls);
    else if (x > mid)
        return query(x,y,rs);
    else {
        segment_tree le = query(x,y,ls),ri = query(x,y,rs),end;
        end.sum = le.sum + ri.sum;
        end.lmax = max(le.lmax,le.sum + ri.lmax);
        end.rmax = max(ri.rmax,ri.sum + le.rmax);
        end.ans = max(max(le.ans,ri.ans),le.rmax + ri.lmax);
        return end;
    }
}

int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
        cin >> a[i];
    build(1,n,1);
    while (m--) {
        int op,x,y;
        cin >> op >> x >> y;
        if (op == 1 && x > y)
            swap(x,y);
        if (op == 1)
            cout << query(x,y,1).ans << endl;
        else
            modify(x,y,1);
    }
    return 0;
}