24/02/24 CF280D k-Maximum Subsequence Sum

标签：24 02 int Sum mx rmx 端点 lmx sum

这题是我在 Luogu 上的第 $400$ AC!

比惊喜更棒的是三倍惊喜！！！

$400$AC祭

以及元宵祭！

这个其实不是很难的黑题，大家可以去写一下啊。那接下来我们先下午休息一下，然后之后再来讲这个挺好的，大家可以把它写一下，锻炼一下。嗯，写了黑题很有成就感，对吧？——lxl 24/02/16上课时对此题的评论

题目描述

Consider integer sequence $ a_{1},a_{2},...,a_{n} $ . 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: $ a_{i}=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 $ a_{l},a_{l+1},...,a_{r} $ . Formally, you should choose at most $ k $ pairs of integers $ (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{t},y_{t}) $ $ (l<=x_{1}<=y_{1}<x_{2}<=y_{2}<...<x_{t}<=y_{t}<=r; t<=k) $ such that the sum $ a_{x1}+a_{x1}+1+...+a_{y1}+a_{x2}+a_{x2}+1+...+a_{y2}+...+a_{xt}+a_{xt}+1+...+a_{yt} $ 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.

输入格式

The first line contains integer $ n $ $ (1<=n<=10^{5}) $ , showing how many numbers the sequence has. The next line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ $ (|a_{i}|<=500) $ .

The third line contains integer $ m $ $ (1<=m<=10^{5}) $ — the number of queries. The next $ m $ lines contain the queries in the format, given in the statement.

All changing queries fit into limits: $ 1<=i<=n $ , $ |val|<=500 $ .

All queries to count the maximum sum of at most $ k $ non-intersecting subsegments fit into limits: $ 1<=l<=r<=n $ , $ 1<=k<=20 $ . It is guaranteed that the number of the queries to count the maximum sum of at most $ k $ non-intersecting subsegments doesn't exceed $ 10000 $ .

输出格式

For each query to count the maximum sum of at most $ k $ non-intersecting subsegments print the reply — the maximum sum. Print the answers to the queries in the order, in which the queries follow in the input.

提示

In the first query of the first example you can select a single pair $ (1,9) $ . So the described sum will be 17.

Look at the second query of the first example. How to choose two subsegments? (1, 3) and (7, 9)? Definitely not, the sum we could get from (1, 3) and (7, 9) is 20, against the optimal configuration (1, 7) and (9, 9) with 25.

The answer to the third query is 0, we prefer select nothing if all of the numbers in the given interval are negative.

题意简述

长度为 $n$ 的数列，支持两种操作：

修改某个位置的值
询问区间 $[l,r]$ 里选出至多 $k$ 个不相交的子段和的最大值。

一共有 $m$ 个操作

一道*2800的大数据结构，码了 3.87KB，考虑到猪国杀还没写完，这是我目前提交过最长的代码了（笑。

总体难度可能不大，但真的很锻炼码力daze。

先将问题简化一下，如果只有 $k=1$ 怎么做？这就是普通的最大子段和。

如果 $k=2$ 哪？

不太方便直接做，如果每次都选最大的区间，区间可能会有交：

而且贪心地去取最大的并不太对，比如这种情况：

如果贪心地去取，第一次就把区间取完了，但如果分两次取，则可以略去中间的负数。

贪心地取最大子段和就走不通了，接下来我们有两条路可以走：

1.费用流

这题我会！裸的费用流！

构建一下费用流模型：源点 $S$ 向每个点 $i$ 连一条流量为 $1$ ，费用为 $0$ 的边；点 $i$ 向点 $i+1$ 连一条流量为 $1$ ，费用为 $a_i$ 的边；点 $i$ 向汇点 $T$连流量为 $1$ ，费用为 $0$ 的边。

此时，网络流的每点流量相当于选择一个区间，我们要求的就是流量不大于 $k$ 的情况下最大的费用。

时间复杂度是 $\Theta($ $)$

dinic 和 dijkstra 拉满了也跑过不去，朴素的网络流算法肯定用不了了。

我们可以拐个弯，不用朴素的费用流算法。

比如说……用什么比较快的东西模拟费用流的运行？

2.反悔贪心

第一条路暂且按下不表，先看看第二条路。

为什么贪心做法是错误的呢？

因为贪心的目光太短浅了，只会选择当前局面的最优解而非全局最优解。

就如此题，早的决策可能会占据以后的最优决策的位置，最优决策就不能选了。

归根结底，贪心有点太武断了，被选择的结果以后也不会更改。

……那要是我们动动手脚，使贪心的结果可以更改呢？

反悔贪心就基于这样的思想，一般情况下与普通的贪心一样选择局部最优解。

但当发现存在更优解时，反悔贪心会撤销原来的决策，替换原本的最优解。

问题来了，怎样撤销呢？

一个简单的想法是记录决策，暴力回溯至撤销位置。

等等，这不就是暴力dfs吗？！

时间复杂度还是$\Theta($ $)$。

那我们再走回第一条路。

1.费用流

如果你了解网络流，那你一定熟识反向边这一操作。

反向边可以理解成一种撤销，走反向边就意味着撤销上次流经正向边的若干流量，这也就是为什么扣除正向边容量时要给反向边加上相应的容量：反向边的容量意味着可以撤销的量。

撤销，有点眼熟。

类似的，反向边的费用是正向边的相反数，每次走反向边就意味撤销之前走过的费用。

怎么又是撤销？

仔细想想，每点流量由源点流向汇点，就意味着进行了一次决策，每次反流，是不是就意味着撤销了一次决策？

事实上，网络流的本质就是贪心，一种 $反悔贪心$ 。

每一滴流量在网络上流动，就意味着一次决策被作出、撤销或是修改。

现在，我们回到第二条路。

2.反悔贪心

借鉴费用流的经验，我们可以用相反数来表示一次撤销操作。

具体的，每取一个区间，我们都将区间整体乘上 $-1$ 。

举个例子：考虑这样一个区间,$k=3$

第一次显然是全部选取：

然后将被选择区间取反:

第二次选取 $1,1$ :

然后取反：

第三次，此时最大子段和已为负数，再取答案会减小，于是我们退出，输出答案。

仔细看这个过程，当选择的区间有重叠时，重叠的部分就彼此抵消了，就像进行了一次异或操作。

这个东西怎么维护呢？交给神奇的线段树吧！

用线段树维护这个过程，时间复杂度为 $\Theta(mk\operatorname{log}n)$。

事实上，这个算法就是大名鼎鼎的

模拟费用流

代码实现

*2500 的思维难度，*2800 的码量。

每次取出最大子段和后需要知道其对应的区间，就要知道它的左端点和右端点，而最大子段和有三种转移，我们就要维护最大子段和左端点，最大子段和右端点，最大前缀右端点，最大后缀左端点。

由于有取反操作，所以我们还要维护最小子段和，最小前缀，最小后缀，最小子段和左端点，最小子段和右端点，最小前缀右端点，最小后缀左端点。

加起来，有十多种信息、标记之间的合并方式。

军火展示：

struct tree{
    int l,r;//左端点，右端点
    int sum,len;//区间和，区间长度
    int mx,lmx,rmx,mxl,mxr,lmxr,rmxl;//最大子段和，最大前缀，最大后缀，最大子段和左端点，最大子段和右端点，最大前缀右端点，最大后缀左端点
    int mn,lmn,rmn,mnl,mnr,lmnr,rmnl;//最小子段和，最小前缀，最小后缀，最小子段和左端点，最小子段和右端点，最小前缀右端点，最小后缀左端点
    int tag;//反转标记
    //军火展示
    inline friend tree const operator+(const tree&x,const tree&y){
        tree t;
        t.l=x.l,t.r=y.r;
        t.sum=x.sum+y.sum;
        t.len=x.len+y.len;

        if(x.sum+y.lmx>x.lmx)t.lmx=x.sum+y.lmx,t.lmxr=y.lmxr;
        else t.lmx=x.lmx,t.lmxr=x.lmxr;
        if(y.sum+x.rmx>y.rmx)t.rmx=y.sum+x.rmx,t.rmxl=x.rmxl;
        else t.rmx=y.rmx,t.rmxl=y.rmxl;
        if(x.mx>y.mx)t.mx=x.mx,t.mxl=x.mxl,t.mxr=x.mxr;
        else t.mx=y.mx,t.mxl=y.mxl,t.mxr=y.mxr;
        if(x.rmx+y.lmx>t.mx)t.mx=x.rmx+y.lmx,t.mxl=x.rmxl,t.mxr=y.lmxr;

        if(x.sum+y.lmn<x.lmn)t.lmn=x.sum+y.lmn,t.lmnr=y.lmnr;
        else t.lmn=x.lmn,t.lmnr=x.lmnr;
        if(y.sum+x.rmn<y.rmn)t.rmn=y.sum+x.rmn,t.rmnl=x.rmnl;
        else t.rmn=y.rmn,t.rmnl=y.rmnl;
        if(x.mn<y.mn)t.mn=x.mn,t.mnl=x.mnl,t.mnr=x.mnr;
        else t.mn=y.mn,t.mnl=y.mnl,t.mnr=y.mnr;
        if(x.rmn+y.lmn<t.mn)t.mn=x.rmn+y.lmn,t.mnl=x.rmnl,t.mnr=y.lmnr;

        return t;
    }
}t[N<<2];

不愧是至今为止写过最难的题呢，而且是完全靠自己写出来的。

看来我还是更适合数据结构 daze

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+5;
int n,m,a[N];
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
struct tree{
    int l,r;//左端点，右端点
    int sum,len;//区间和，区间长度
    int mx,lmx,rmx,mxl,mxr,lmxr,rmxl;//最大子段和，最大前缀，最大后缀，最大子段和左端点，最大子段和右端点，最大前缀右端点，最大后缀左端点
    int mn,lmn,rmn,mnl,mnr,lmnr,rmnl;//最小子段和，最小前缀，最小后缀，最小子段和左端点，最小子段和右端点，最小前缀右端点，最小后缀左端点
    int tag;//反转标记
    //军火展示
    inline friend tree const operator+(const tree&x,const tree&y){
        tree t;
        t.l=x.l,t.r=y.r;
        t.sum=x.sum+y.sum;
        t.len=x.len+y.len;

        if(x.sum+y.lmx>x.lmx)t.lmx=x.sum+y.lmx,t.lmxr=y.lmxr;
        else t.lmx=x.lmx,t.lmxr=x.lmxr;
        if(y.sum+x.rmx>y.rmx)t.rmx=y.sum+x.rmx,t.rmxl=x.rmxl;
        else t.rmx=y.rmx,t.rmxl=y.rmxl;
        if(x.mx>y.mx)t.mx=x.mx,t.mxl=x.mxl,t.mxr=x.mxr;
        else t.mx=y.mx,t.mxl=y.mxl,t.mxr=y.mxr;
        if(x.rmx+y.lmx>t.mx)t.mx=x.rmx+y.lmx,t.mxl=x.rmxl,t.mxr=y.lmxr;

        if(x.sum+y.lmn<x.lmn)t.lmn=x.sum+y.lmn,t.lmnr=y.lmnr;
        else t.lmn=x.lmn,t.lmnr=x.lmnr;
        if(y.sum+x.rmn<y.rmn)t.rmn=y.sum+x.rmn,t.rmnl=x.rmnl;
        else t.rmn=y.rmn,t.rmnl=y.rmnl;
        if(x.mn<y.mn)t.mn=x.mn,t.mnl=x.mnl,t.mnr=x.mnr;
        else t.mn=y.mn,t.mnl=y.mnl,t.mnr=y.mnr;
        if(x.rmn+y.lmn<t.mn)t.mn=x.rmn+y.lmn,t.mnl=x.rmnl,t.mnr=y.lmnr;

        return t;
    }
}t[N<<2];
inline void push_up(int p){
    int tmp=t[p].tag;
    t[p]=t[ls]+t[rs];
    t[p].tag=tmp;
}
inline void make_tag(int p){
    t[p].tag^=1;
    t[p].sum=-t[p].sum;
    t[p].mx=-t[p].mx;
    t[p].mn=-t[p].mn;
    t[p].lmx=-t[p].lmx;
    t[p].rmx=-t[p].rmx;
    t[p].lmn=-t[p].lmn;
    t[p].rmn=-t[p].rmn;
    swap(t[p].mn,t[p].mx);
    swap(t[p].lmn,t[p].lmx);
    swap(t[p].rmn,t[p].rmx);
    swap(t[p].mnl,t[p].mxl);
    swap(t[p].mnr,t[p].mxr);
    swap(t[p].lmnr,t[p].lmxr);
    swap(t[p].rmnl,t[p].rmxl); 
}
inline void push_down(int p){
    if(t[p].tag){
        make_tag(ls),make_tag(rs);
        t[p].tag=0;
    }
}
void build(int p,int l,int r){
    if(l==r){
        t[p].l=l,t[p].r=r;
        t[p].lmx=t[p].rmx=t[p].mx=t[p].lmn=t[p].rmn=t[p].mn=t[p].sum=a[l];
        t[p].mxl=t[p].mxr=t[p].lmxr=t[p].rmxl=t[p].mnl=t[p].mnr=t[p].lmnr=t[p].rmnl=r;
        t[p].tag=0,t[p].len=1;
        return;
    }
    build(ls,l,mid),build(rs,mid+1,r);
    push_up(p);
}
void update(int p,int l,int r,int k,int x){
    if(l==r){
        t[p].lmx=t[p].rmx=t[p].mx=t[p].lmn=t[p].rmn=t[p].mn=t[p].sum=x;
        return;
    }
    push_down(p);
    if(k<=mid)update(ls,l,mid,k,x);
    else update(rs,mid+1,r,k,x);
    push_up(p);
}
void update_rev(int p,int l,int r,int L,int R){
    if(l>=L&&r<=R)return make_tag(p);
    if(l>R||r<L)return;
    push_down(p);
    update_rev(ls,l,mid,L,R),update_rev(rs,mid+1,r,L,R);
    push_up(p);
}
tree query(int p,int l,int r,int L,int R){
    if(l==L&&r==R)return t[p];
    push_down(p);
    if(mid<L)return query(rs,mid+1,r,L,R);
    else if(mid>=R)return query(ls,l,mid,L,R);
    else return query(ls,l,mid,L,mid)+query(rs,mid+1,r,mid+1,R);
}
int L[N],R[N],tot;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    cin>>m;
    for(int i=1;i<=m;i++){
        int op,l,r,k,x;
        cin>>op;
        if(op==0){
            cin>>k>>x;
            update(1,1,n,k,x);
        }
        else{
            cin>>l>>r>>k;
            int res=0;tot=0;
            for(int i=1;i<=k;i++){
                tree p=query(1,1,n,l,r);
                // cout<<p.mx<<' '<<p.mxl<<' '<<p.mxr<<endl;
                if(p.mx<=0)break;
                res+=p.mx;
                L[++tot]=p.mxl,R[tot]=p.mxr;
                update_rev(1,1,n,L[tot],R[tot]);
            }
            cout<<res<<'\n';
            for(int i=tot;i;i--)update_rev(1,1,n,L[i],R[i]);
        }
    }
    return 0;
}
//coder:Iictiw
//date:24/02/24
//When I wrote a piece of code, her and I knew what it was doing
//400题！加油！

//咏唱组一生推！

标签：24,02,int,Sum,mx,rmx,端点,lmx,sum
From： https://www.cnblogs.com/Iictiw/p/18031540

24/02/24 CF280D k-Maximum Subsequence Sum

题目描述

输入格式

输出格式

提示

题意简述

1.费用流

2.反悔贪心

1.费用流

2.反悔贪心

模拟费用流

代码实现

相关文章

赞助商

阅读排行