P7164分块做法

· · 题解

发现题解区没有本做法于是来发一篇~

题目大意就是让求

\max\limits_{j\leq i}\{(i-j+1)\min\limits_{k=j}^ia_k\min\limits_{k=i}^jb_k\}

那么我们考虑把上面的式子拆成三项相乘，移动指针 i 维护每个指针 j 到它的答案，每次取 max 即可。

切换一下变量名，设 av 为题目中给出的 a 数组，a_j 为 \min\limits_{k=j}^{i}av_k，剩下两个数组类似。

首先接着让我们拆一下式子。下面钦定 j\geq k，则a_j\geq a_k,b_j\geq b_k。

如果令 v_i=a_i\times b_i，则若对于当前的 i，ans_j\geq ans_k，有：

(i-j+1)v_j\geq (i-k+1)v_k (v_j-v_k)(i+1)\geq jv_j-kv_k i+1\geq \frac{jv_j-kv_k}{(v_j-v_k)}

容易看出，只要我们维护出一个凸包就可以求最值了。

那么如何维护呢？

我们使用单调栈求出对于当前的 i，第二项需要改变的范围 [l_1,i]，第三项需要改变的范围 [l_2,i]，在下图中讨论 l_1\leq l_2的情况，l_2\leq l_1 的情况类似。位置关系如下图。

对于修改操作：

对于 j\in[l_1,l_2) 要将所有的 a_j\to av_i，对于 j\in[l_2,i] 要将所有的 a_j\to av_i,b_j\to bv_i。

区间赋值大家都会，问题是如何维护凸包。修改后显然有对于 j\in[l_2,i] 只有 l_2 这个位置可能在凸包上继续存在，所以把别的位置都删掉就行了。对于 j\in[l_1,l_2) 有任意 a_j 相等，那么接上上面的式子，有：

i+1\geq \frac{ja_jb_j-ka_kb_k}{a_jb_j-a_kb_k} i+1\geq \frac{jb_j-kb_k}{b_j-b_k}

发现凸包和 a 无关，于是我们另外维护一个 b 的凸包，求答案时乘上一个 a 就可以了。

相对应的另一种情况我们也要维护 a 的凸包，但是在上面的情况中显然有对于 j\in[l_1,l_2) 只有 l_1 这个位置可能在凸包上继续存在。于是把别的位置都删掉就行了。

剩下部分不用动。然后我们直接在凸包上二分就行了......吗？

如果用线段树这样做，一个父节点无法轻易合并两个子节点信息。所以我们考虑分块。设块长为 B。

对于散块修改，我们暴力重构，复杂度 O(B)，整块打上区间赋值标记即可，复杂度 O(\frac{n}{B}) 。

对于查询操作，散块可以暴力取最值，复杂度 O(B) ，整块可以在凸包上二分，复杂度 O(\frac{n}{B}\log n)。

那么总复杂度就是 O(n(B+\frac{n}{B}\log n)) 的，容易发现当 B 取到 \sqrt{n\log n} 时理论复杂度最优，为 O(n\sqrt{n\log n})。

上面讨论的是时间复杂度，而空间复杂度由于只需要对每个块开块长的凸包，是 O(n) 的。爆标了

Code


#include<cassert>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
namespace EMT{
    typedef long long ll;typedef long double db;
    #define pf printf
    #define F(i,a,b) for(int i=a;i<=b;i++)
    #define D(i,a,b) for(int i=a;i>=b;i--)
    inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
    inline void file(){freopen("cuboid.in","r",stdin);freopen("cuboid.out","w",stdout);}
    inline ll max(ll a,ll b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
    inline void pi(int x){pf("%d ",x);}inline void pn(){pf("\n");}
    const int N=2e5+10,B=200;const db inf=1e18;
    struct dp{ll x,y;db K;friend bool operator <(dp a,dp b){return a.K<b.K;}}s[N/B+10][3][B+10];
    int top[N/B+10][3],bel[N],L[N/B+10],R[N/B+10],n,a[N],b[N],av[N],bv[N],lz1[N/B+10],lz2[N/B+10],nw;ll ans;
    inline db slope(dp &a,dp &b){return (db)(a.y-b.y)/(db)(a.x-b.x);}
    inline void down(int x){
        int lim=min(nw,R[x]);
        if(lz1[x]){F(i,L[x],lim)a[i]=lz1[x];lz1[x]=0;}
        if(lz2[x]){F(i,L[x],lim)b[i]=lz2[x];lz2[x]=0;}
    }
    inline void build(int x){
        int lim=min(nw,R[x]);
        top[x][0]=0;
        F(i,L[x],lim){
            if(i>L[x]&&a[i]==a[i-1])continue;
            dp p={a[i],1ll*i*a[i],0};
            while(top[x][0]>1&&slope(s[x][0][top[x][0]-1],p)<=s[x][0][top[x][0]-1].K)top[x][0]--;
            if(top[x][0])s[x][0][top[x][0]].K=slope(s[x][0][top[x][0]],p);s[x][0][++top[x][0]]=p;
        }s[x][0][top[x][0]].K=inf;
        top[x][1]=0;
        F(i,L[x],lim){
            if(i>L[x]&&b[i]==b[i-1])continue;
            dp p={b[i],1ll*i*b[i],0};
            while(top[x][1]>1&&slope(s[x][1][top[x][1]-1],p)<=s[x][1][top[x][1]-1].K)top[x][1]--;
            if(top[x][1])s[x][1][top[x][1]].K=slope(s[x][1][top[x][1]],p);s[x][1][++top[x][1]]=p;
        }s[x][1][top[x][1]].K=inf;
        top[x][2]=0;
        F(i,L[x],lim){
            if(i>L[x]&&1ll*a[i]*b[i]==1ll*a[i-1]*b[i-1])continue;
            dp p={1ll*a[i]*b[i],1ll*i*a[i]*b[i],0};
            while(top[x][2]>1&&slope(s[x][2][top[x][2]-1],p)<=s[x][2][top[x][2]-1].K)top[x][2]--;
            if(top[x][2])s[x][2][top[x][2]].K=slope(s[x][2][top[x][2]],p);s[x][2][++top[x][2]]=p;
        }s[x][2][top[x][2]].K=inf;
    }
    inline void change1(int l,int r,int tp,int v){
        if(bel[l]==bel[r]){
            down(bel[l]);
            F(i,l,r)if(tp==1)a[i]=v;else b[i]=v;
            build(bel[l]);
        }else{
            down(bel[l]),down(bel[r]);
            F(i,l,R[bel[l]])if(tp==1)a[i]=v;else b[i]=v;
            F(i,L[bel[r]],r)if(tp==1)a[i]=v;else b[i]=v;
            build(bel[l]),build(bel[r]);
            F(i,bel[l]+1,bel[r]-1){
                if(tp==1){
                    lz1[i]=v;
                    s[i][0][top[i][0]=1]={v,1ll*L[i]*v,inf};
                }else{
                    lz2[i]=v;
                    s[i][1][top[i][1]=1]={v,1ll*L[i]*v,inf};
                }
            }
        }
    }
    inline void change2(int l,int r,int v1,int v2){
        if(bel[l]==bel[r]){
            down(bel[l]);
            F(i,l,r)a[i]=v1,b[i]=v2;
            build(bel[l]);
        }else{
            down(bel[l]),down(bel[r]);
            F(i,l,R[bel[l]])a[i]=v1,b[i]=v2;
            F(i,L[bel[r]],r)a[i]=v1,b[i]=v2;
            build(bel[l]),build(bel[r]);
            F(i,bel[l]+1,bel[r]-1){
                lz1[i]=v1,lz2[i]=v2;
                s[i][0][top[i][0]=1]={v1,1ll*L[i]*v1,inf};
                s[i][1][top[i][1]=1]={v2,1ll*L[i]*v2,inf};
            }
        }
    }
    inline ll clac(dp &p,int v){
        return 1ll*v*p.x-p.y;
    }
    inline void ask(int l,int r,int v){
        if(bel[l]==bel[r]){
            down(bel[l]);
            F(i,l,r)ans=max(ans,1ll*a[i]*b[i]*(nw-i+1));
        }else{
            down(bel[l]),down(bel[r]);
            F(i,l,R[bel[l]])ans=max(ans,1ll*a[i]*b[i]*(nw-i+1));
            F(i,L[bel[r]],r)ans=max(ans,1ll*a[i]*b[i]*(nw-i+1));
            F(i,bel[l]+1,bel[r]-1){
                if(lz1[i]){
                    int x=std::lower_bound(s[i][1]+1,s[i][1]+top[i][1]+1,(dp){0,0,(db)v})-s[i][1];
                    if(x<=top[i][1])ans=max(ans,1ll*lz1[i]*clac(s[i][1][x],v));
                    if(x+1<=top[i][1])ans=max(ans,1ll*lz1[i]*clac(s[i][1][x+1],v));
                    if(x-1)ans=max(ans,1ll*lz1[i]*clac(s[i][1][x-1],v));
                }else if(lz2[i]){
                    int x=std::lower_bound(s[i][0]+1,s[i][0]+top[i][0]+1,(dp){0,0,(db)v})-s[i][0];
                    if(x<=top[i][0])ans=max(ans,1ll*lz2[i]*clac(s[i][0][x],v));
                    if(x+1<=top[i][0])ans=max(ans,1ll*lz2[i]*clac(s[i][0][x+1],v));
                    if(x-1)ans=max(ans,1ll*lz2[i]*clac(s[i][0][x-1],v));
                }else{
                    int x=std::lower_bound(s[i][2]+1,s[i][2]+top[i][2]+1,(dp){0,0,(db)v})-s[i][2];
                    if(x<=top[i][2])ans=max(ans,clac(s[i][2][x],v));
                    if(x+1<=top[i][2])ans=max(ans,clac(s[i][2][x+1],v));
                    if(x-1)ans=max(ans,clac(s[i][2][x-1],v));
                }
            }
        }
    }
    inline short main(){
        n=read();
        F(i,1,n)av[i]=read(),bv[i]=read(),bel[i]=(i-1)/B+1;
        F(i,1,bel[n])L[i]=R[i-1]+1,R[i]=min(n,i*B);
        static int sta1[N],top1,sta2[N],top2;
        F(i,1,n){
            nw=i;
            while(top1&&av[sta1[top1]]>=av[i])top1--;
            int l1=sta1[top1]+1;sta1[++top1]=i;
            while(top2&&bv[sta2[top2]]>=bv[i])top2--;
            int l2=sta2[top2]+1;sta2[++top2]=i;
            if(l1<l2)change1(l1,l2-1,1,av[i]);
            if(l2<l1)change1(l2,l1-1,2,bv[i]);
            change2(max(l1,l2),i,av[i],bv[i]);
            if(i==R[bel[i]])build(bel[i]);
            ask(1,i,i+1);
        }pf("%lld\n",ans);
        return 0;
    }
}
signed main(){return EMT::main();}

可能最近 Ynoi 做多了，导致一看到数据结构题就往根号上想...

有没有好哥哥能把复杂度里面的 \log n 去掉啊！