题解 P5693 【EI的第六分块】

· · 题解

首先，欢迎加入EI队长粉丝裙:450567214

本题的一个 O((n+m)\log^3 n+q\log n) 做法由 EI 队长在她的集训队论文《浅谈函数最值的动态维护》中给出，其中 n,m,q 分别代表序列长度、修改次数、查询次数. 该数据结构被称为 Kinetic Tournament 树 (KTT).

该做法的原理在 EI's blog 或论文中有详细阐述，这里仅给出一个直接实现及可参考的代码.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=400500;
const long long INF=2e18;
int n,w[N],m;
long long tag[N<<2];
struct LINE//一次函数
{
    int k;long long b;
    LINE operator +(const LINE &a)const{return (LINE){k+a.k,b+a.b};}
};
pair<LINE,long long> max(LINE a,LINE b)//对两个一次函数取x=0时的最值，同时给出max的选取不发生变化的最大值C(即 x>C 时max变成另一个)
{
    if(a.k<b.k||(a.k==b.k&&a.b<b.b))swap(a,b);
    if(a.b>=b.b){return make_pair(a,INF);}
    return make_pair(b,(b.b-a.b)/(a.k-b.k));
}
struct Node
{
    LINE ls,rs,ans,sum;long long x;//增量>x时子树内会有max的选取发生变化
    Node operator +(const Node &a)const
    {
        Node t;t.x=min(x,a.x);
        pair<LINE,long long>tmp=max(ls,sum+a.ls);
        t.ls=tmp.first,t.x=min(t.x,tmp.second);
        tmp=max(a.rs,rs+a.sum);
        t.rs=tmp.first,t.x=min(t.x,tmp.second);
        tmp=max(ans,a.ans);t.x=min(t.x,tmp.second);
        tmp=max(tmp.first,rs+a.ls);
        t.ans=tmp.first,t.x=min(t.x,tmp.second);
        t.sum=sum+a.sum;
        return t;
    }
}a[N<<2];
void build(int rot,int lt,int rt)
{
    if(lt==rt)
    {
        LINE t={1,w[lt]};
        a[rot]=(Node){t,t,t,t,INF};
        return;
    }
    int mid=(lt+rt)>>1;
    build(rot<<1,lt,mid),build(rot<<1|1,mid+1,rt);
    a[rot]=a[rot<<1]+a[rot<<1|1];
}
void upd(int rot,long long w)
{
    tag[rot]+=w;a[rot].x-=w;
    a[rot].ls.b+=a[rot].ls.k*w;
    a[rot].rs.b+=a[rot].rs.k*w;
    a[rot].ans.b+=a[rot].ans.k*w;
    a[rot].sum.b+=a[rot].sum.k*w;
}
void upd(int rot,int lt,int rt,long long w)
{
    if(w>a[rot].x)//如果增量使得子树内有max发生变化则递归下去重构
    {
        long long t=tag[rot]+w;tag[rot]=0;int mid=(lt+rt)>>1;
        upd(rot<<1,lt,mid,t),upd(rot<<1|1,mid+1,rt,t);
        a[rot]=a[rot<<1]+a[rot<<1|1];
    }
    else upd(rot,w);
}
void pushdown(int rot)
{
    if(tag[rot])
    {
        long long t=tag[rot];tag[rot]=0;
        upd(rot<<1,t),upd(rot<<1|1,t);
    }
}
void update(int rot,int lt,int rt,int lq,int rq,int x)
{
    if(lt>=lq&&rt<=rq){upd(rot,lt,rt,x);return;}
    pushdown(rot);
    int mid=(lt+rt)>>1;
    if(lq<=mid)update(rot<<1,lt,mid,lq,rq,x);
    if(rq>mid)update(rot<<1|1,mid+1,rt,lq,rq,x);
    a[rot]=a[rot<<1]+a[rot<<1|1];
}
Node query(int rot,int lt,int rt,int lq,int rq)
{
    if(lt>=lq&&rt<=rq)return a[rot];
    pushdown(rot);
    int mid=(lt+rt)>>1;
    if(rq<=mid)return query(rot<<1,lt,mid,lq,rq);
    if(lq>mid)return query(rot<<1|1,mid+1,rt,lq,rq);
    return query(rot<<1,lt,mid,lq,mid)+query(rot<<1|1,mid+1,rt,mid+1,rq);
}
int getin()
{
    int x=0,f=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x*f;
}
int main()
{
    n=getin(),m=getin();
    for(int i=1;i<=n;i++)w[i]=getin();
    build(1,1,n);
    for(int i=1,opt,l,r,x;i<=m;i++)
    {
        opt=getin(),l=getin(),r=getin();
        if(opt==1)x=getin(),update(1,1,n,l,r,x);
        else printf("%lld\n",max(0ll,query(1,1,n,l,r).ans.b));
    }
}