题解：P5693 EI 的第六分块

Tmbcan · 2024-11-12 10:41:49 · 题解

P5693 EI 的第六分块

题目描述

给定一个整数序列，支持区间加正整数以及查询区间最大子段和。

思路

使用线段树记录四个信息来维护答案：

合并时我们分类讨论：

KTT 部分

我推荐直接去看集训队论文或者一些大佬的讲解。复杂度我不会证，请看 EI 队长的证明。
（KTT 我没学会严谨说明，只能全靠感性理解了。）

现在每个信息记录的都不是一个具体值，而是一条一次函数 f(x)=kx+b。
其中 k 为最大子段的长度，x 为变化量，f(0)=b 为当前维护的具体值。
同时，对于两条函数，记录一个阈值 dx，表示当前区间最大值是否在两个函数间进行交替。我们需要维护四个信息的最大值，现在问题变成了一次函数比大小。

Push_down/Push_up

前置知识：人教版八年级下册 19.2.3一次函数与方程、不等式。
在对两条函数进行合并取最大值时，需要知道具体应该何时选取哪条函数。我们知道应该看函数的交点相对于区间的位置，来对取值情况分类讨论。
交替阈值就干了这样一件事情，维护时记录下何时应该对函数选取进行交替，并只在需要交替时交替，以此优化时间复杂度。

具体地，当区间加 q 时，函数向上进行了移动，函数的交点相对于区间进行了左右移动。此时我们令阈值 dx 减小，当 dx<0 时表示此时选取的函数要进行交替了（即决策点向左进行了移位）。
由于同一个区间可能有两个不同的函数进行维护，所以在合并区间时，阈值不仅要对左右区间取最小值，还需要包含当前两条函数的交点。

Rebuild

我们在 Update 后，可能会导致节点子树内的 dx 发生变化，而当 dx<0 时会导致最大值选取发生变化。
所以我们在做更新后需要对节点子树 Rebuild，二次递推来更新 dx。

Update/Query

正常进行修改和查询即可，记得 Rebuild。
同时注意左右区间的合并顺序。

代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T&x){//快读
    int w=0;x=0;
    char ch = getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') w=1;
        ch = getchar();
    }
    while(ch>='0' && ch<='9'){
        x = (x<<1)+(x<<3)+(ch^48);
        ch = getchar();
    }
    if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
    read(t);read(args...);
}
template <typename T>
inline T Min(T x,T y){ return (x < y ? x : y); }
const int N = 4e5+10;
const ll INF = 1e16;
struct Func{//一次函数
    ll k,b;
    Func(){
        k = 0; b = 0;
    }
    Func(ll tk,ll tb){
        k = tk; b = tb;
    }
    inline Func operator + (const Func&G) const{//函数合并
        return Func(k+G.k,b+G.b);
    }
    inline bool operator < (const Func&G) const{//钦定函数的位置关系
        return k==G.k && b<G.b || k<G.k;
    }
    inline ll operator & (const Func&G) const{//求交点
        return (G.b-b)/(k-G.k);
    }
    inline void operator += (const ll&G){//函数向上移动
        b += k*G;
    }
};
struct Tree{
    Func lx,rx,sum,mx; ll dx;//维护区间的四个信息以及阈值
    Tree(){
        dx = INF;//初始化为无穷大值，表示永远不会对最大值产生影响
    }
    Tree(Func tlx,Func trx,Func tsum,Func tmx,ll tdx){
        lx = tlx; rx = trx; sum = tsum; mx = tmx; dx = tdx;
    }
    inline void Merge_lx(Func x,Func y,Tree &tmp) const{//求lmax
        if(x<y) swap(x,y); 
        if(x.b>=y.b) tmp.lx = x;//钦定过了函数位置，此时两条函数没有交点
        else tmp.lx = y,tmp.dx = Min(tmp.dx,x&y);
    }
    inline void Merge_rx(Func x,Func y,Tree &tmp) const{//求rmax
        if(x<y) swap(x,y);
        if(x.b>=y.b) tmp.rx = x;
        else tmp.rx = y,tmp.dx = Min(tmp.dx,x&y);
    }
    inline void Merge_mx(Func x,Func y,Tree &tmp) const{//求mx
        if(x<y) swap(x,y);
        if(x.b>=y.b) tmp.mx = x;
        else tmp.mx = y,tmp.dx = Min(tmp.dx,x&y);
    }
    inline Tree operator + (const Tree&G) const{//区间合并
        Tree tmp; tmp.dx = Min(dx,G.dx); tmp.sum = sum+G.sum;
        Merge_lx(lx,sum+G.lx,tmp);Merge_rx(G.rx,G.sum+rx,tmp);
        Merge_mx(G.mx,mx,tmp);Merge_mx(tmp.mx,rx+G.lx,tmp);
        return tmp;
    }
    inline void operator += (const ll&G){//区间加
        lx += G; rx += G; mx += G; sum += G; dx -= G;
    }
}tr[N*3];
int P=1,DEP=0,st[N*3]; ll tag[N*3];
inline void push_down(int p){//正常push_down
    if(tag[p]){
        tag[p<<1] += tag[p]; tr[p<<1] += tag[p];
        tag[p<<1|1] += tag[p]; tr[p<<1|1] += tag[p];
        tag[p] = 0;
    }
}
inline void rebuild(int p){
    if(tr[p].dx>=0) return ;
    int head = 1,tail = 0;
    st[++tail] = p; push_down(p);
    while(tail>=head){
        int ttail = tail;
        for(int j=tail,pos;j>=head;--j){
            pos = st[j]; //看子节点的子树是否需要更新
            if(tr[pos<<1].dx<0) st[++tail]=pos<<1,push_down(pos<<1);
            if(tr[pos<<1|1].dx<0) st[++tail]=pos<<1|1,push_down(pos<<1|1);
        }
        head = ttail+1;
    }//重新维护
    do{ tr[st[tail]]=tr[st[tail]<<1]+tr[st[tail]<<1|1]; } while(--tail); 
}
inline void update(int l,int r,ll k){
    l += P-1; r += P+1;//先push_down
    for(int dep=DEP;dep;--dep) push_down(l>>dep),push_down(r>>dep);
    while(l^1^r){
        if(~l&1) tag[l^1]+=k,tr[l^1]+=k,rebuild(l^1);//别忘了rebuild
        if(r&1) tag[r^1]+=k,tr[r^1]+=k,rebuild(r^1);
        l>>=1;r>>=1;
        tr[l] = tr[l<<1]+tr[l<<1|1];
        tr[r] = tr[r<<1]+tr[r<<1|1];
    }
    for(l>>=1; l ;l>>=1) tr[l] = tr[l<<1]+tr[l<<1|1];
}
inline ll query(int l,int r){
    l += P-1; r += P+1;//先push_down
    for(int dep=DEP;dep;--dep) push_down(l>>dep),push_down(r>>dep);
    Tree resl,resr;
    while(l^1^r){
        //注意左右区间的合并顺序
        if(~l&1) resl = resl+tr[l^1];
        if(r&1) resr = tr[r^1]+resr;
        l>>=1;r>>=1;
    }
    return (resl+resr).mx.b;
}
int main(){
    // freopen("in.in","r",stdin);
    // freopen("out.out","w",stdout);
    int n,m;read(n,m);
    while(P<=n+1) P<<=1,++DEP;
    for(int i=1,k;i<=n;++i){
        read(k); Func res = Func(1ll,1ll*k);
        tr[i+P] = Tree(res,res,res,res,INF);//初始时都是y=x+a[i]
    }
    for(int i=P-1;i;--i) tr[i] = tr[i<<1]+tr[i<<1|1];
    for(int i=1,opt,l,r;i<=m;++i){
        read(opt,l,r); ll k;
        if(opt==1) read(k),update(l,r,k);
        else printf("%lld\n",(k=query(l,r))<0?0ll:k);//区间可以不选
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

我的第一篇黑题，感谢 NianFeng 提供的帮助。