poj2750 线段树 +DP Potted Flower

问题描述：给定一个环形序列，进行在线操作，每次修改一个元素，输出环上的最大连续子列的和，但不能是完全序列。

算法：把环从一个地方，切断拉成一条直线，用线段树记录当前区间的非空最大子列和当前区间的非空最小子列。

动态规划解决过静态的序列最大连续子序列和问题，时间复杂度可以达到 n（环形序列可能复杂度更高）。但是这里涉及到动态更新，更新频度很大，如果计算子序列和复杂度仍然是n,就会非常耗时。

如果环上的数都是正整数，答案是：环上数的总和－根结点的非空最小子列；否则，答案是：max{根结点的非空最大子列, 环上数的总和－根结点的非空最小子列}

一开始想到，如果将环从一点断开，那么最大和如果包括断点的最后一个点和第一个点，那该如何求

，仔细看了一下，终于向明白了，如果段的最大自序列包括断点那么断点一定是正数；

那么环上数的总和－根结点的非空最小子列，就将断点包括了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define maxn 100005

int maxsub[maxn<<2], minsub[maxn<<2];
int lmax[maxn<<2], rmax[maxn<<2];
int lmin[maxn<<2], rmin[maxn<<2];
int sum[maxn<<2];

void PushUp(int rt) {
    int l = rt<<1;
    int r = l+1;
    sum[rt] = sum[l] + sum[r];
    maxsub[rt] = max(max(maxsub[l], maxsub[r]), rmax[l]+lmax[r]);
    minsub[rt] = min(min(minsub[l], minsub[r]), rmin[l]+lmin[r]);
    lmax[rt] = max(lmax[l], sum[l]+lmax[r]);
    rmax[rt] = max(rmax[r], sum[r]+rmax[l]);
    lmin[rt] = min(lmin[l], sum[l]+lmin[r]);
    rmin[rt] = min(rmin[r], sum[r]+rmin[l]);
}

void build(int l, int r, int rt) {
    if (l == r) {
       scanf("%d", &sum[rt]);
       minsub[rt] = lmax[rt] = rmax[rt] = lmin[rt] = rmin[rt] = maxsub[rt] = sum[rt];
       return;
    }
    int m = (l+r)>>1;
    build(l, m, rt<<1);
    build(m+1, r, rt<<1|1);
    PushUp(rt);
}

void update(int target, int val, int l, int r, int rt) {
    if (l == r) {
        sum[rt] = maxsub[rt] = minsub[rt] = val;
        lmax[rt] = rmax[rt] = lmin[rt] = rmin[rt] = val;
        return;
    }
    int m = (l+r)>>1;
    if (m >= target) update(target, val, l, m, rt<<1);
    else update(target, val, m+1, r, rt<<1|1);
    PushUp(rt);
}

int main()
{
    int n, m, ans;

    scanf ("%d", &n);
    build(1, n, 1);
    scanf("%d", &m);
    while (m--) {
        int a, b;
        scanf ("%d%d", &a, &b);
        update(a, b, 1, n, 1);
        if (sum[1] == maxsub[1]) //序列全为非负数的时候
            ans = sum[1] - minsub[1];
        else ans = max(maxsub[1], sum[1]-minsub[1]);
        printf ("%d
", ans);
    }
    return 0;
}

poj2750 线段树 +DP Potted Flower

相关推荐