【Ynoi2013】D2T2

mrsrz 2月 20, 2020

分块，分治。

题目大意：

给定一个长度为 $n$ 的序列，多次询问，每次给出 $l,r,L,R$ ，需要求出，只保留权值在 $[L,R]$ 中的数，其他数的权值为 $0$ 时，区间 $[l,r]$ 的最大子段和。

题解：

~~第七分块太难了就先来写一下这个。~~

~~结果交了 59 发才过……~~

有一个非常简单的做法，将值域离散化之后对值域进行莫队，用线段树维护最大子段和。时间复杂度为 $O(n\sqrt m\log n)$ 。

考虑更优的做法。如果我们有一种时间复杂度 $O(n^2)$ 的做法求出一个长度为 $n$ 的序列的所有不同值域限制下的全局最大子段和，那我们就可以通过分块将这个复杂度降为 $O(n\sqrt n)$ 。

关于最大子段和的问题，分治是一个常见的思路。由于长度为 $n$ 的序列，只有 $O(n^2)$ 个本质不同的值域限制，所以我们希望每层都能 $O(n^2)$ 合并信息。这样分治的复杂度为 $T(n)=2T(\frac n 2)+O(n^2)$ 。根据主定理即可得到 $T(n)=O(n^2)$ 。

我们考虑已知两个子区间的本质不同的值以及限制，如何合并为这一层的答案。对于合并上来的 $[L,R]$ ，我们需要在左、右分别找到区间 $[L_1,R_1]$ 和 $[L_2,R_2]$ ，其中 $[L_1,R_1]$ 和 $[L_2,R_2]$ 都是被 $[L,R]$ 包含的最大区间。那么这两个区间的最大子段和信息进行合并，即可得到 $[L,R]$ 的最大子段和信息。

我们考虑预处理对每个 $L$ ，左、右区间第一个大于等于 $L$ 的值。同样，对于 $R$ ，预处理左、右区间第一个小于等于 $R$ 的值。由于我们是要选最大的两个区间合并，那么两个端点和 $L,R$ 最接近的一定是最大的。这样就可以直接 $O(n^2)$ 枚举 $L,R$ ，然后 $O(1)$ 找到两个需要合并的区间，进行合并。

分治的时空复杂度均为 $O(n^2)$ ，考虑对序列分块，每个块的大小为 $O(\sqrt n)$ ，则对每个块进行分治的时间复杂度为 $O(n)$ 。分治花费的时间复杂度为 $O(n\sqrt n)$ 。

对于一个询问，拆成整块的和边角的。对于边界的显然可以 $O(\sqrt n)$ 解决。对于整块的，我们已经知道所有本质不同的值域限制的答案，那么对于值域限制为 $[L,R]$ 的询问，我们要找到被它包含的最大的区间的信息。那么和上面的处理方式相同，对每个 $L$ 和 $R$ 分别找到最靠近的端点即可。这里为了保证复杂度，必须用双指针处理，否则时间复杂度将退化为 $O(m\sqrt n\log n)$ 。

由于直接存储所有块的信息需要 $O(n\sqrt n)$ 的空间，无法接受。所以我们对询问离线，在一个块的信息处理完后，直接把这个块对所有询问的贡献都更新掉。这样空间复杂度为 $O(n)$ 。

时间复杂度为 $O((n+m)\sqrt n)$ 。

注意实现时的常数。

Code：

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<functional>
using namespace std;
typedef long long LoveLive;
typedef unsigned long long ULL;
#define bel(x)((x-1)/siz+1)
const int N=1e5+5,siz=200,B=siz+2;
char buf[(int)1e7],*ss=buf;
inline int init(){buf[fread(buf,1,(int)1e7-1,stdin)]='\n';fclose(stdin);return 0;}
const int __START__=init();
inline int readint(){
    int d=0;bool f=0;
    while(!isdigit(*ss))f=*ss++=='-';
    while(isdigit(*ss))d=d*10+(*ss++^'0');
    return f?-d:d;
}
char bwf[5000005],*ww=bwf;
int xx[24];
inline void print(LoveLive x){
    static int*q=xx;
    if(!x)*ww++='0';else{
        for(;x;x/=10)*q++=(x%10)^'0';
        while(q!=xx)*ww++=*--q;
    }
    *ww++='\n';
}
int n,m,A[N],a[B],beL[N],beR[N],b[B],tmp[B],vec[B];
struct data{
    LoveLive lmax,rmax,mx,sum;
    inline data(LoveLive a,LoveLive b,LoveLive c,LoveLive d):lmax(a),rmax(b),mx(c),sum(d){}
    inline data(){lmax=rmax=mx=sum=0;}
    inline data(LoveLive x){sum=x,lmax=rmax=mx=max(x,0LL);}
    inline data operator+(const data&rhs)const{
        return(data){max(lmax,sum+rhs.lmax),max(rhs.rmax,rhs.sum+rmax),max({mx,rhs.mx,rmax+rhs.lmax}),sum+rhs.sum};
    }
    inline void operator+=(const data&rhs){mx=max({mx,rhs.mx,rmax+rhs.lmax}),lmax=max(lmax,sum+rhs.lmax),rmax=max(rhs.rmax,rhs.sum+rmax),sum+=rhs.sum;}
}ans[N],p[65536],Lt[65536],Rt[65536];
ULL lf[N],rg[N];
int IT[B];
struct que{
    int l,r,L,R;
}q[N];
struct info{
    int zt;
    data s;
}D[600000],*ed;
void solve(int l,int r,info*V,int&tot){
    if(l==r){
        V[tot++]=(info){a[l]<<8|a[l],data(vec[a[l]])};
        return;
    }
    const int mid=l+r>>1;
    info*L=ed;ed+=(mid-l+1)*(mid-l+2);
    info*R=ed;ed+=(r-mid+1)*(r-mid);
    int cntL=0,cntR=0;
    solve(l,mid,L,cntL),solve(mid+1,r,R,cntR);
    int i=l,j=mid+1,t=l,k;
    while(i<=mid&&j<=r)if(b[i]<=b[j])tmp[t++]=b[i++];else tmp[t++]=b[j++];
    while(i<=mid)tmp[t++]=b[i++];while(j<=r)tmp[t++]=b[j++];
    for(int i=0;i<cntL;++i)Lt[L[i].zt]=L[i].s;
    for(int i=0;i<cntR;++i)Rt[R[i].zt]=R[i].s;
    static int _L[B],_R[B],L_[B],R_[B];
    t=l,k=mid+1;
    for(int i=l;i<=r;++i){
        while(t<=mid&&b[t]<tmp[i])++t;
        while(k<=r&&b[k]<tmp[i])++k;
        _L[i]=t<=mid?b[t]:114514,L_[i]=k<=r?b[k]:114514;
    }
    t=mid,k=r;
    for(int i=r;i>=l;--i){
        while(t>=l&&b[t]>tmp[i])--t;
        while(k>mid&&b[k]>tmp[i])--k;
        _R[i]=t>=l?b[t]:0,R_[i]=k>mid?b[k]:0;
    }
    for(int i=l;i<=r;++i)b[i]=tmp[i];
    for(int i=l;i<=r;++i)if(i==l||b[i]!=b[i-1])
    for(int j=i;j<=r;++j)if(j==i||b[j]!=b[j-1]){
        const data&ztL=Lt[_L[i]<<8|_R[j]],&ztR=Rt[L_[i]<<8|R_[j]];const int X=b[i]<<8|b[j];
        if(_L[i]<=_R[j]&&L_[i]<=R_[j])V[tot++]=(info){X,ztL+ztR};else
        if(_L[i]<=_R[j])V[tot++]=(info){X,ztL};else
        if(L_[i]<=R_[j])V[tot++]=(info){X,ztR};
    }
    ed=L;
}
inline data get(int l,int r,const int&L,const int&R){
    LoveLive lm=0,rm=0,sum=0,mx=0,s=0;
    for(int i=l;i<=r;++i)if(lm<(s+=(L<=A[i]&&A[i]<=R)?A[i]:0))lm=s;
    s=0;
    for(int i=r;i>=l;--i)if(rm<(s+=(L<=A[i]&&A[i]<=R)?A[i]:0))rm=s;
    s=0;
    for(int i=l;i<=r;++i){
        const int x=(L<=A[i]&&A[i]<=R)?A[i]:0;
        sum+=x,s+=x;
        if(mx<s)mx=s;
        if(s<0)s=0;
    }
    return data(lm,rm,mx,sum);
}
int main(){
    n=readint(),m=readint();
    for(int i=1;i<=n;++i)A[i]=readint();
    for(int i=1;i<=m;++i){
        int l=readint(),r=readint(),L=readint(),R=readint();
        q[i]=(que){l,r,L,R},L+=1000000000,R+=1000000000,lf[i]=(ULL)L<<32|i,rg[i]=(ULL)R<<32|i;
    }
    sort(lf+1,lf+m+1),sort(rg+1,rg+m+1,greater<ULL>());
    for(int l=siz+1,r=2*siz;r<=n;l+=siz,r+=siz){
        int len=r-l+1;
        for(int i=l;i<=r;++i)vec[i-l]=A[i];
        int Val=len;
        sort(vec,vec+len);
        Val=unique(vec,vec+len)-vec;
        for(int i=l;i<=r;++i)a[i-l]=lower_bound(vec,vec+Val,A[i])-vec;
        memcpy(b,a,sizeof a);
        int tp=0;
        ed=D+len*(len+1);
        solve(0,len-1,D,tp);
        for(int i=0;i<tp;++i)p[D[i].zt]=D[i].s;
        int it1=0,it2=Val-1;
        for(int i=1;i<=m;++i){
            while(it1<Val&&(lf[i]>>32)>vec[it1]+1000000000)++it1;
            while(~it2&&(rg[i]>>32)<vec[it2]+1000000000)--it2;
            beL[(int)lf[i]]=it1,beR[(int)rg[i]]=it2;
        }
        for(int i=1;i<=m;++i)if(beL[i]<=beR[i]&&q[i].l<l&&r<q[i].r)ans[i]+=p[beL[i]<<8|beR[i]];
    }
    for(int i=1;i<=m;++i){
        int l=q[i].l,r=q[i].r;
        const int bL=bel(l),bR=bel(r);
        if(bL==bR)print(get(l,r,q[i].L,q[i].R).mx);else
        print((get(l,bL*siz,q[i].L,q[i].R)+ans[i]+get((bR-1)*siz+1,r,q[i].L,q[i].R)).mx);
    }
    fwrite(bwf,ww-bwf,1,stdout);
    return 0;
}

Gitalking ...