题目

Codeforces280D

原文

Consider integer sequence a1, a2, ..., an. You should run queries of two types:

• The query format is "0 i val". In reply to this query you should make the following assignment: ai = val.
• The query format is "1 l r k". In reply to this query you should print the maximum sum of at most k non-intersecting subsegments of sequence al, al + 1, ..., ar. Formally, you should choose at most k pairs of integers (x1, y1), (x2, y2), ..., (xt, yt) (l ≤ x1 ≤ y1 < x2 ≤ y2 < ... < xt ≤ yt ≤ r; t ≤ k) such that the sum ax1 + ax1 + 1 + ... + ay1 + ax2 + ax2 + 1 + ... + ay2 + ... + axt + axt + 1 + ... + ayt is as large as possible. Note that you should choose at most k subsegments. Particularly, you can choose 0 subsegments. In this case the described sum considered equal to zero.

中文

给你一个长为\(n\)的序列，每回给你一个区间\([l,r]\)，询问在这段区间里选取不超过\(k\)段连续的元素，最大的元素和是多少。支持修改。修改询问一共\(m\)次
\(1\leqslant n,m\leqslant 10^5\qquad 1\leqslant k\leqslant20\qquad\)不会爆int

思路

数据结构，思想

• 模拟费用流
• 线段树

关于模拟费用流

• 本质就是观察一个费用流的图，发现它有一些特殊性质，然后利用这些性质加速增广。
• 由于这些题大多奥妙重重，你直接想贪心也想得出来

真·思路

• 先说结论：就是取\(k\)次区间最大子段和，并每一次取过之后把对应区间取反（变为相反数）。如果哪一次最大子段和为负数了，就可以提前终止。
• 先由贪心来思考一下，看一看这么做为什么是对的。
  • 最后的这段序列，一定是一段选取，一段不选，间隔着来的。
  • 那么，某一段选取的不继续往边上扩展，肯定是有原因的——两边要么到边了，要么是负数了。
  • 而每一段选取的区间，最左和最右一定是正数。
  • 所以，我们每次选取，肯定能选到最后答案的两个断点（断点即选与不选的区间交界的地方，显然最多有\(2k\)个），并且不会重复（重复的话以前选取的就不再是最大子段和了）。因此我们最后能最多得到\(2k\)个断点，正好就能得到答案。
• 再考虑一下费用流
  • 发现费用流的图，是S点向A点连一条（费用0/流量k）的边，选取的区间每一个点都有一个代表节点。A点向每个点的代表节点连（费用这个点的权值/流量1）的边，每一个节点再向他的后一个节点连一条（费用下个点的权值/流量1的边），最后每个点再都向T点连一条（费用0/流量1）的边。
  • 于是我们这个过程就与费用流很像。取反则对应着弄出反向边。
• 然后来看，我们就要支持三种操作：
  • 单点修改
  • 区间查询最大子段和
  • 区间取反
• 我们可以线段树来完成，就是标记有点多（我写了17个）。

代码

#include<bits/stdc++.h>
#define LL long long
#define MAXN 100000
using namespace std;
template<typename T>void Read(T &cn)
{
    char c;int sig = 1;
    while(!isdigit(c = getchar()))if(c == '-')sig = -1; cn = c-48;
    while(isdigit(c = getchar()))cn = cn*10+c-48; cn*=sig;
}
template<typename T>void Write(T cn)
{
    if(cn<0) {putchar('-'); cn = 0-cn; }
    int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
    while(cn)wei++,cm = cm*10+cn%10,cn/=10;
    while(wei--)putchar(cm%10+48),cm/=10;
    putchar(cx+48);
}
struct qwe{
    int l,r;
};
struct dan{
    int l,r,ans;
};
struct dx{
    int zuo,you,da,he;
    int l,r,z,y;
};
dan mk(int cn,int cm,int cx) {dan guo; guo.l = cn; guo.r = cm; guo.ans = cx; return guo; }
struct Seg{
    struct node{
        dx d,x;
        int p;
    };
    node t[MAXN*4+1];
    void zhuang(dx &cn,int cm,int cx)
    {
        cn.zuo = cn.you = cn.da = cn.he = cm;
        cn.l = cn.r = cn.z = cn.y = cx;
    }
    void build(int cn,int l,int r,int a[])
    {
        t[cn].p = 0;
        if(l == r){
            zhuang(t[cn].d,a[l],l); zhuang(t[cn].x,-a[l],l);
            return;
        }
        build(cn<<1,l,(l+r)>>1,a); build((cn<<1)|1,((l+r)>>1)+1,r,a);
        update(cn,(l+r)>>1);
    }
    void r_update(dx &cn,dx ls,dx rs,int zh)
    {
        cn.he = ls.he + rs.he;
        if(ls.da > rs.da)cn.da = ls.da,cn.l = ls.l,cn.r = ls.r;
        else cn.da = rs.da,cn.l = rs.l,cn.r = rs.r;
        if(cn.da < ls.you + rs.zuo)cn.da = ls.you + rs.zuo,cn.l = ls.y,cn.r = rs.z;
        
        if(ls.zuo > ls.he + rs.zuo)cn.zuo = ls.zuo,cn.z = ls.z;
        else cn.zuo = ls.he + rs.zuo,cn.z = rs.z;
        if(cn.zuo < ls.he)cn.zuo = ls.he,cn.z = zh;
        
        if(rs.you > rs.he + ls.you)cn.you = rs.you,cn.y = rs.y;
        else cn.you = rs.he + ls.you,cn.y = ls.y;
        if(cn.you < rs.he)cn.you = rs.he,cn.y = zh+1;
    }
    void update(int cn,int zh)
    {
        int ls = cn<<1,rs = ls+1;
        r_update(t[cn].d,t[ls].d,t[rs].d,zh); r_update(t[cn].x,t[ls].x,t[rs].x,zh);
    }
    void tui(int cn)
    {
        if(!t[cn].p)return;
        int ls = cn<<1,rs = (cn<<1)|1;
        t[ls].p ^= 1; swap(t[ls].d,t[ls].x);
        t[rs].p ^= 1; swap(t[rs].d,t[rs].x);
        t[cn].p = 0;
    }
    void gai(int cn,int cm,int cx,int l,int r)
    {
        if(l == r) {
            zhuang(t[cn].d,cx,l); zhuang(t[cn].x,-cx,l);
            return;
        }
        tui(cn);
        int zh = (l+r)>>1;
        if(cm <= zh)gai(cn<<1,cm,cx,l,zh); else gai((cn<<1)|1,cm,cx,zh+1,r);
        update(cn,(l+r)>>1);
    }
    void qufan(int cn,int cl,int cr,int l,int r)
    {
        if(cl <= l && r <= cr) {
            dx lin = t[cn].d; t[cn].d = t[cn].x; t[cn].x = lin; 
            t[cn].p ^= 1;
            return;
        }
        tui(cn);
        int zh = (l+r)>>1;
        if(cl <= zh)qufan(cn<<1,cl,cr,l,zh);
        if(cr > zh)qufan((cn<<1)|1,cl,cr,zh+1,r);
        update(cn,(l+r)>>1);
    }
    dx xun(int cn,int cl,int cr,int l,int r)
    {
        if(cl <= l && r <= cr)return t[cn].d;
        tui(cn);
        int zh = (l+r)>>1;
        if(cl <= zh){
            dx guo = xun(cn<<1,cl,cr,l,zh);
            if(cr > zh){
                dx guo2 = xun((cn<<1)|1,cl,cr,zh+1,r);
                r_update(guo,guo,guo2,zh);
            }
            return guo;
        }
        if(cr > zh)return xun((cn<<1)|1,cl,cr,zh+1,r);
    }
}T;
int n,q;
int a[MAXN+1];
qwe zhan[MAXN+1];
int zlen;
int main()
{
//  freopen("a.in","r",stdin);
//  freopen("a.ou","w",stdout);
    Read(n);
    for(int i = 1;i<=n;i++)Read(a[i]);
    T.build(1,1,n,a);
    Read(q);
    for(int i = 1;i<=q;i++)
    {
        int bx,bn,bm,by;
        Read(bx); Read(bn); Read(bm);
        if(!bx)T.gai(1,bn,bm,1,n);
        else{
            Read(by);
            zlen = 0;
            LL guo = 0;
            for(int j = 1;j<=by;j++)
            {
                dx lin = T.xun(1,bn,bm,1,n);
                if(lin.da <= 0)break;
                guo += lin.da;
                zhan[++zlen].l = lin.l; zhan[zlen].r = lin.r;
                T.qufan(1,lin.l,lin.r,1,n);
            }
            for(int j = 1;j<=zlen;j++)T.qufan(1,zhan[j].l,zhan[j].r,1,n);
            Write(guo); putchar('\n');
        }
    }
    return 0;
}