CF280D k-Maximum Subsequence Sum (线段树)

10W个数10W个操作，操作有两种：

修改单点的值；

从区间[L,R]中选出最多k段不相交区间，使和最大。

k最大为20

用dp思路时间复杂度O(mk^2lgn) == TLE。so，会有其他方法。

如果用费用流解决k段区间最大和，那么找增广路的过程是怎么样的呢。

step 1，找到一条费用最大的增广路L

step 2，若找不到增广路，或L已经是负费用了，goto step 4，否则计算新费用，

step 3，删除L，在残量图中加入与L方向相反，费用相反的反向弧，goto step 1

step 4，输出答案

上面的过程每一轮都至少使流量+1，最多持续k轮。看起来比dp的k^2系数要好，但是要是每次都建图费用流必须TLE，所以可以简化成这样：

step 1，找到[L,R]中的一段最大连续和[l,r]

step 2，若sum[l,r]>0，将sum[l,r]计入答案，否则goto step 4

step 3，将[l,r]的所有数字取反，goto step 1

step 4，输出答案

这个就可以用线段树来实现了，时间复杂度O(mklgn)，常数略大。

岛娘和clj出的题真是不能玩啊，哪怕知道算法敲出来也累死了- -b，我再也不要玩线段树了。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = 101000;
struct Line {
        int l,r,s;
        Line(int l=0,int r=0,int s=0):l(l),r(r),s(s) {}
        Line operator + (Line tt) {
                return Line(l,tt.r,s+tt.s);
        }
        bool operator < (const Line &tt) const {
                return s<tt.s;
        }
        void show() { printf("::%d %d %d\n",l,r,s); }
};
struct Node {
        Line Lmax,Lmin,Rmax,Rmin,Vmax,Vmin,V;
        int rev;
        Node(int l=0,int r=0,int s=0) {
                Lmax = Lmin = Rmax = Rmin = Vmax = Vmin = V = Line(l,r,s);
                rev = 0;
        }
        void up(Node a,Node b) {
                if (a.Lmax.l==0) { *this = b; return; }
                Lmax = max(a.Lmax,a.V+b.Lmax);
                Lmin = min(a.Lmin,a.V+b.Lmin);
                Rmax = max(a.Rmax+b.V,b.Rmax);
                Rmin = min(a.Rmin+b.V,b.Rmin);
                Vmax = max(a.Rmax,b.Lmax);
                Vmax = max(Vmax,max(a.Vmax,b.Vmax));
                Vmax = max(Vmax,a.Rmax+b.Lmax);
                Vmax = max(Vmax,max(Lmax,Rmax));
                Vmin = min(a.Rmin,b.Lmin);
                Vmin = min(Vmin,min(a.Vmin,b.Vmin));
                Vmin = min(Vmin,a.Rmin+b.Lmin);
                Vmin = min(Vmin,min(Lmin,Rmin));
                V = a.V+b.V;
        }
};
Node tree[N<<2];
int n,m;
void rev(int rt) {
        Node &x = tree[rt];
        x.rev ^= 1;
        swap(x.Lmin,x.Lmax); swap(x.Rmin,x.Rmax); swap(x.Vmin,x.Vmax);
        x.Lmin.s *= -1; x.Lmax.s *= -1; x.Rmin.s *= -1; x.Rmax.s *= -1; 
        x.Vmin.s *= -1; x.Vmax.s *= -1; x.V.s *= -1;
}
void down(int rt) {
        if (tree[rt].rev) {
                rev(rt<<1); 
                rev(rt<<1|1);
                tree[rt].rev = 0;
        }
}
void build(int l,int r,int rt) {
        if (l==r) {
                int val; scanf("%d",&val);
                tree[rt] = Node(l,r,val);
                return ;
        }
        int mid = l+r>>1;
        build(lson);
        build(rson);
        tree[rt].up(tree[rt<<1],tree[rt<<1|1]);
}
void modify(int p,int v,int l,int r,int rt) {
        if (l==r) {
                tree[rt] = Node(l,r,v); return ;
        }
        int mid = l+r>>1;
        down(rt);
        if (p<=mid) modify(p,v,lson); 
        else modify(p,v,rson);
        tree[rt].up(tree[rt<<1],tree[rt<<1|1]);
}
void rev(int L,int R,int l,int r,int rt) {
        if (L<=l && r<=R) {
                rev(rt); return ;
        }
        int mid = l+r>>1;
        down(rt);
        if (L<=mid) rev(L,R,lson);
        if (mid< R) rev(L,R,rson);
        tree[rt].up(tree[rt<<1],tree[rt<<1|1]);
}
Node query(int L,int R,int l,int r,int rt) {
        if (L<=l && r<=R) return tree[rt];
        int mid = l+r>>1;
        down(rt);
        Node ret;
        if (L<=mid) ret.up(ret,query(L,R,lson));
        if (R> mid) ret.up(ret,query(L,R,rson));
        return ret;
}
int main() {
        scanf("%d",&n);
        build(1,n,1);
        scanf("%d",&m);
        while (m--) {
                int op;
                scanf("%d",&op);
                if (op==0) {
                        int p,v;
                        scanf("%d%d",&p,&v);
                        modify(p,v,1,n,1);
                } else {
                        int l,r,k,ans = 0;
                        scanf("%d%d%d",&l,&r,&k);
                        vector<Line> zxc;
                        for (int i = 0; i < k; i ++) {
                                Line t = query(l,r,1,n,1).Vmax;
                                zxc.push_back(t);
                                rev(t.l,t.r,1,n,1);
                                if (t.s>0) ans += t.s;
                                else break;
                        }
                        for (int i = 0; i < (int)zxc.size(); i ++)
                                rev(zxc[i].l,zxc[i].r,1,n,1);
                        printf("%d\n",ans);
                }
        }
        return 0;
}

CF280D k-Maximum Subsequence Sum (线段树)

原文：http://blog.csdn.net/hei_nero/article/details/19018929