分块分治卡常

EnofTaiPeople · 2022-09-25 15:27:21 · 题解

[Ynoi2013] D2T2 是我的第二道黑 Ynoi，从卡空间变成了卡时间。

序列上直接做怎么也想不到方法，对值域莫队可以做到 O(n\sqrt{q}\log_2n)，显然过不去。

对于一个长度为 n 的区间本质不同值域个数只有不到 n^2 个，将它们全部处理出来，可以使用分治，先求出左半和右半的各 \frac{n^2}{4} 个答案，再将答案合并，双指针就可以 O(n^2) 解决，时空复杂度 T(n)=O(n^2)+2T(\frac{n}{2})=O(n^2)。

对于每一个询问双指针就可以 O(n+q) 得到每一个询问的答案，但是 O(n^2+n+q) 肯定过不了。

发现 n^2 与 n+q 并不平衡，我们需要通过分块来让它们平衡，具体来说，将原序列分成 \sqrt n\times\sqrt n 的区间，每一个区间单独分治，复杂度为 O(n)，这样单块复杂度为 O(n+\sqrt n+q)，散块暴力复杂度是 O(q\sqrt n)，总时间复杂度为 O(\sqrt n(n+\sqrt n+q)+q\sqrt n)=O((n+q)\sqrt n)，空间 O(n+q)，代码很好写：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=105005;
namespace fast_io{
    char bf[N+5],ob[N+38];
    int it,ed,x,f,c,ot,t,stk[38];
#define gc (it==ed&&(ed=(it=0)+fread(bf,1,N,stdin),it==ed))?EOF:bf[it++]
    inline int read(){
        for(c=gc,f=0;c<48;c=gc)if(c=='-')f=!f;
        for(x=0;c>47;x=x*10+(48^c),c=gc);if(f)x=-x;
        return x;
    }inline void fls(){
        fwrite(ob,1,ot,stdout),ot=0;
    }
    void wt(ll x){
        if(x>9)wt(x/10);
        ob[ot++]=48^(x%10);
    }
    inline void write(ll x){
        if(x>9)wt(x/10);ob[ot++]=48^(x%10);
        ob[ot++]='\n';if(ot>N)fls();
    }
}using fast_io::read;
using fast_io::write;
int a[N],n,m,mp[N<<1],mt,ff[719];
struct Q{int l,r,L,R,id;}q[N];
struct anstp{
    ll l,m,r,sm;
    inline void operator+=(const anstp &z){
        m=max({m,z.m,r+z.l});
        l=max(l,sm+z.l),r=max(r+z.sm,z.r);
        sm=sm+z.sm;
    }inline void operator|=(const int &p){
        l=m=r=p>0?p:0;sm=p;
    }
}ans[N];
using V=vector<anstp>;
vector<V>f[719];
vector<int>d[719];
int b[N],sz,l_[N<<1],r_[N<<1];
inline int solve(int x,int l,int r){
    if(l==r){
        d[x][0]=a[l],f[x][0][0]|=a[l];
        return 1;
    }int i,md=l+r>>1,ls=x<<1,rs=ls|1,t;
    int lz=solve(ls,l,md),rz=solve(rs,md+1,r);
    merge(&d[ls][0],&d[ls][lz],&d[rs][0],&d[rs][rz],b);
    sz=unique(b,b+lz+rz)-b;
    for(i=t=0;i<sz;++i){
        while(t<lz&&d[ls][t]<b[i])++t;
        l_[i]=t;
    }for(i=sz-1,t=lz-1;~i;--i){
        while(t>=0&&d[ls][t]>b[i])--t;
        r_[i]=t;
    }for(l=0;l<sz;++l)
        for(r=l;r<sz;++r)
            if(l_[l]<lz&&r_[r]>-1)f[x][l][r]=f[ls][l_[l]][r_[r]];
            else f[x][l][r]={0};
    for(i=t=0;i<sz;++i){
        while(t<rz&&d[rs][t]<b[i])++t;
        l_[i]=t;
    }for(i=sz-1,t=rz-1;~i;--i){
        while(t>=0&&d[rs][t]>b[i])--t;
        r_[i]=t;
    }for(l=0;l<sz;++l)
        for(r=l;r<sz;++r)
            if(l_[l]<rz&&r_[r]>-1)
                f[x][l][r]+=f[rs][l_[l]][r_[r]];
    for(i=0;i<sz;++i)d[x][i]=b[i];return sz;
}
int main(){
    int i,l,r,t,sz,_l,_r,j;
    for(l=2,ff[1]=256;l<=511;++l)ff[l]=ff[l>>1]>>1;
    for(l=1;l<=511;++l){
        d[l].resize(ff[l]),f[l].resize(ff[l]);
        for(i=0;i<ff[l];++i)f[l][i].resize(ff[l]);
    }
    for(i=1,n=read(),m=read();i<=n;++i)a[i]=read();
    for(i=1;i<=m;++i){
        q[i]={read(),read(),read(),read(),i};
        mp[++mt]=q[i].L,mp[++mt]=q[i].R;
    }sort(mp+1,mp+mt+1),mt=unique(mp+1,mp+mt+1)-mp-1;
    for(i=1;i<=m;++i){
        q[i].L=lower_bound(mp+1,mp+mt+1,q[i].L)-mp;
        q[i].R=lower_bound(mp+1,mp+mt+1,q[i].R)-mp;
    }
    int i1,i2,i3,i4,i5,i6,i7,i8;
    for(l=1;l<=n;l=r+1){
        r=l+255,sz=solve(1,l,r);
        for(i=1,t=0;i<=mt;++i){
            while(t<sz&&d[1][t]<mp[i])++t;
            l_[i]=t;
        }for(i=mt,t=sz-1;i;--i){
            while(t>=0&&d[1][t]>mp[i])--t;
            r_[i]=t;
        }for(i=1;i<=m;i=i8+1){
            i1=i,i2=i1+1,i3=i2+1,i4=i3+1;
            i5=i4+1,i6=i5+1,i7=i6+1,i8=i7+1;
            if(q[i1].l<=l&&q[i1].r>=r){
                if(l_[q[i1].L]<sz&&r_[q[i1].R]>-1)
                    ans[i1]+=f[1][l_[q[i1].L]][r_[q[i1].R]];  
            }else if(q[i1].l<=r&&q[i1].r>=l){
                _l=max(q[i1].l,l),_r=min(q[i1].r,r);
                for(j=_l;j<=_r;++j)
                    if(a[j]>=mp[q[i1].L]&&a[j]<=mp[q[i1].R])
                        ans[0]|=a[j],ans[i1]+=ans[0];
            }
            if(q[i2].l<=l&&q[i2].r>=r){
                if(l_[q[i2].L]<sz&&r_[q[i2].R]>-1)
                    ans[i2]+=f[1][l_[q[i2].L]][r_[q[i2].R]];  
            }else if(q[i2].l<=r&&q[i2].r>=l){
                _l=max(q[i2].l,l),_r=min(q[i2].r,r);
                for(j=_l;j<=_r;++j)
                    if(a[j]>=mp[q[i2].L]&&a[j]<=mp[q[i2].R])
                        ans[0]|=a[j],ans[i2]+=ans[0];
            }
            if(q[i3].l<=l&&q[i3].r>=r){
                if(l_[q[i3].L]<sz&&r_[q[i3].R]>-1)
                    ans[i3]+=f[1][l_[q[i3].L]][r_[q[i3].R]];  
            }else if(q[i3].l<=r&&q[i3].r>=l){
                _l=max(q[i3].l,l),_r=min(q[i3].r,r);
                for(j=_l;j<=_r;++j)
                    if(a[j]>=mp[q[i3].L]&&a[j]<=mp[q[i3].R])
                        ans[0]|=a[j],ans[i3]+=ans[0];
            }
            if(q[i4].l<=l&&q[i4].r>=r){
                if(l_[q[i4].L]<sz&&r_[q[i4].R]>-1)
                    ans[i4]+=f[1][l_[q[i4].L]][r_[q[i4].R]];  
            }else if(q[i4].l<=r&&q[i4].r>=l){
                _l=max(q[i4].l,l),_r=min(q[i4].r,r);
                for(j=_l;j<=_r;++j)
                    if(a[j]>=mp[q[i4].L]&&a[j]<=mp[q[i4].R])
                        ans[0]|=a[j],ans[i4]+=ans[0];
            }
            if(q[i5].l<=l&&q[i5].r>=r){
                if(l_[q[i5].L]<sz&&r_[q[i5].R]>-1)
                    ans[i5]+=f[1][l_[q[i5].L]][r_[q[i5].R]];  
            }else if(q[i5].l<=r&&q[i5].r>=l){
                _l=max(q[i5].l,l),_r=min(q[i5].r,r);
                for(j=_l;j<=_r;++j)
                    if(a[j]>=mp[q[i5].L]&&a[j]<=mp[q[i5].R])
                        ans[0]|=a[j],ans[i5]+=ans[0];
            }
            if(q[i6].l<=l&&q[i6].r>=r){
                if(l_[q[i6].L]<sz&&r_[q[i6].R]>-1)
                    ans[i6]+=f[1][l_[q[i6].L]][r_[q[i6].R]];  
            }else if(q[i6].l<=r&&q[i6].r>=l){
                _l=max(q[i6].l,l),_r=min(q[i6].r,r);
                for(j=_l;j<=_r;++j)
                    if(a[j]>=mp[q[i6].L]&&a[j]<=mp[q[i6].R])
                        ans[0]|=a[j],ans[i6]+=ans[0];
            }
            if(q[i7].l<=l&&q[i7].r>=r){
                if(l_[q[i7].L]<sz&&r_[q[i7].R]>-1)
                    ans[i7]+=f[1][l_[q[i7].L]][r_[q[i7].R]];  
            }else if(q[i7].l<=r&&q[i7].r>=l){
                _l=max(q[i7].l,l),_r=min(q[i7].r,r);
                for(j=_l;j<=_r;++j)
                    if(a[j]>=mp[q[i7].L]&&a[j]<=mp[q[i7].R])
                        ans[0]|=a[j],ans[i7]+=ans[0];
            }
            if(q[i8].l<=l&&q[i8].r>=r){
                if(l_[q[i8].L]<sz&&r_[q[i8].R]>-1)
                    ans[i8]+=f[1][l_[q[i8].L]][r_[q[i8].R]];  
            }else if(q[i8].l<=r&&q[i8].r>=l){
                _l=max(q[i8].l,l),_r=min(q[i8].r,r);
                for(j=_l;j<=_r;++j)
                    if(a[j]>=mp[q[i8].L]&&a[j]<=mp[q[i8].R])
                        ans[0]|=a[j],ans[i8]+=ans[0];
            }
        }
    }for(i=1;i<=m;++i)write(ans[i].m);
    fast_io::fls();return 0;
}

这个写法太丑了，卡了一版，每一次总有几个测试点有 \text{760ms}，这时，常数的优化至关重要。

在将块合并时，对边界的特判浪费了很多时间，可以通过在每一个离散化数组的末尾添加一个 2e9 来避免。

将闭区间改为半闭半开区间，这样就只需要处理 \ge l 和 \ge r 的第一个数，就可以得到包含的最大区间了，常数减小了一半，可以通过：

inline int solve(int x,int l,int r){
    if(l==r){
        d[x][0]=a[l],d[x][1]=2e9;
        f[x][0][1]|=a[l];
        f[x][0][0]=f[x][1][1]={0};
        return 2;
    }int i,md=l+r>>1,ls=x<<1,rs=ls|1,tl,tr;
    int lz=solve(ls,l,md),rz=solve(rs,md+1,r);
    merge(&d[ls][0],&d[ls][lz],&d[rs][0],&d[rs][rz],b);
    sz=unique(b,b+lz+rz)-b;
    for(i=tl=tr=0;i<sz;++i){
        while(d[ls][tl]<b[i])++tl;l_[i]=tl;
        while(d[rs][tr]<b[i])++tr;r_[i]=tr;
    }
    for(l=0;l<sz;++l)
        for(r=l;r<sz;++r)
            f[x][l][r]=f[ls][l_[l]][l_[r]]+f[rs][r_[l]][r_[r]];
    for(i=0;i<sz;++i)d[x][i]=b[i];return sz;
}