CF280D k-Maximum Subsequence Sum

Mobius127 · 2021-09-11 15:07:57 · 题解

题传

发现 k 很小，在上面做文章。

如果 k=1，那么就是一线段树板子，顺带能资瓷单点修改。

考虑反悔贪心，当我们选了一段极长的段，它不一定是最优的，我们可能不需要其中的一部分，但其本质上是新加的一段选取了这一部分，同时丢掉了某一部分，相当于“借”一段给新的，需要消掉这一部分在原串的贡献，于是想到将选取的一段乘上 -1，再取最大连续段。

那么我们在线段树上只需要维护区间取反的操作，相当于这一整段的大值变小，小值变大，所以再维护一个全局最小子段和，取反时将 最大/最小 的互换即可。

注意每个询问互不影响，所以记得将所有取过的都消回去。然后导致码量大幅增加

复杂度 O(nk \log n)，挺好写的。

Code：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <cmath>
#include <cstdlib>
using namespace std;
inline int read(){
    char ch=getchar();int x=0, f=1;
    while(!isdigit(ch)) f=(ch=='-'?-1:f), ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
    return x*f;
}
inline void Swp(int &a, int &b){int t=a;a=b, b=t;return ;}
const int N=1e5+5;
struct node{
    int L, R, sum, tag;
    int lmax, rmax, Mx, Rx, Lx, LXans, RXans;
    int lmin, rmin, Mn, Rn, Ln, LNans, RNans;
    void spread(){
        sum=-sum;tag^=1;
        swap(lmax, lmin), swap(rmax, rmin), swap(Mx, Mn);
        swap(Rx, Rn), swap(Lx, Ln), swap(LXans, LNans), swap(RXans, RNans);
        lmax=-lmax, lmin=-lmin;
        rmax=-rmax, rmin=-rmin;
        Mx=-Mx, Mn=-Mn;
        return ;
    }
}tree[N*4];
node Newnode(int pos, int val){
    return (node){pos, pos, val, 0, val, val, val, pos, pos, pos, pos, val, val, val, pos, pos, pos, pos};
}
node operator + (node A, node B){
    node C;C.sum=A.sum+B.sum, C.L=A.L, C.R=B.R;C.tag=0;

    if(A.sum+B.lmax>A.lmax) C.lmax=A.sum+B.lmax, C.Rx=B.Rx;
    else C.lmax=A.lmax, C.Rx=A.Rx;
    if(B.sum+A.rmax>B.rmax) C.rmax=B.sum+A.rmax, C.Lx=A.Lx;
    else C.rmax=B.rmax, C.Lx=B.Lx;
    if(A.sum+B.lmin<A.lmin) C.lmin=A.sum+B.lmin, C.Rn=B.Rn;
    else C.lmin=A.lmin, C.Rn=A.Rn;
    if(B.sum+A.rmin<B.rmin) C.rmin=B.sum+A.rmin, C.Ln=A.Ln;
    else C.rmin=B.rmin, C.Ln=B.Ln;

    int Maxi=max(max(max(C.lmax, C.rmax), A.rmax+B.lmax), max(A.Mx, B.Mx));
    if(Maxi==C.lmax) C.LXans=C.L, C.RXans=C.Rx;
    else if(Maxi==C.rmax) C.LXans=C.Lx, C.RXans=C.R;
    else if(Maxi==A.rmax+B.lmax) C.LXans=A.Lx, C.RXans=B.Rx;
    else if(Maxi==A.Mx) C.LXans=A.LXans, C.RXans=A.RXans;
    else if(Maxi==B.Mx) C.LXans=B.LXans, C.RXans=B.RXans;
    C.Mx=Maxi;

    int Mini=min(min(min(C.lmin, C.rmin), A.rmin+B.lmin), min(A.Mn, B.Mn));
    if(Mini==C.lmin) C.LNans=C.L, C.RNans=C.Rn;
    else if(Mini==C.rmin) C.LNans=C.Ln, C.RNans=C.R;
    else if(Mini==A.rmin+B.lmin) C.LNans=A.Ln, C.RNans=B.Rn;
    else if(Mini==A.Mn) C.LNans=A.LNans, C.RNans=A.RNans;
    else if(Mini==B.Mn) C.LNans=B.LNans, C.RNans=B.RNans;
    C.Mn=Mini;

    return C;
}
int n, m, a[N];
#define ls k<<1
#define rs k<<1|1
#define mid (tree[k].L+tree[k].R>>1)
void pushup(int k){tree[k]=tree[ls]+tree[rs];}
void pushdown(int k){
    if(!tree[k].tag) return ;
    tree[ls].spread(), tree[rs].spread();tree[k].tag=0;
    return ;
}
void build(int k, int l, int r){
    tree[k].L=l, tree[k].R=r, tree[k].tag=0;
    if(l==r){tree[k]=Newnode(l&r, a[l&r]);return;}
    build(ls, l, mid), build(rs, mid+1, r);
    pushup(k);
}
void modify(int k, int x, int v){
    if(tree[k].L==tree[k].R){tree[k]=Newnode(x, v);return ;}pushdown(k);
    if(x<=mid) modify(ls, x, v);
    else modify(rs, x, v);
    return pushup(k);
}
void change(int k, int x, int y){
    if(x<=tree[k].L&&tree[k].R<=y) return tree[k].spread();pushdown(k);
    if(x<=mid) change(ls, x, y);
    if(mid<y) change(rs, x, y);
    return pushup(k);
}
node query(int k, int x, int y){
    if(x<=tree[k].L&&tree[k].R<=y) return tree[k];pushdown(k);
    if(y<=mid) return query(ls, x, y);
    if(x>mid) return query(rs, x, y);
    node Ll=query(ls, x, y);node Rr=query(rs, x, y);
    return Ll+Rr; 
}
#undef ls
#undef rs 
#undef mid
void doit(int dep, int sum, int &res, int x, int y){
    if(!dep) return ;
    node ans=query(1, x, y);
    res=max(res, sum+=ans.Mx);
    change(1, ans.LXans, ans.RXans);
    doit(dep-1, sum, res, x, y);
    change(1, ans.LXans, ans.RXans);
    return ;
}
signed main(){
    n=read();
    for(int i=1; i<=n; i++) a[i]=read();
    build(1, 1, n);
    m=read();
    for(int i=1, opt, x, y, k; i<=m; i++){
        opt=read();
        if(!opt) x=read(), y=read(), modify(1, x, y);
        else{
            x=read(), y=read(), k=read();
            int ans=0;
            doit(k, 0, ans, x, y);
            printf("%d\n", ans);
        }
    }
    return 0;
}