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 
  
   
#include 
   
     #include 
    
      #include 
     
       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
      
       >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
       
         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; }