自动搬运

查看原文

来自洛谷，原作者为

	Petit_Souris 鼓励的话语 无论多少次我都会说给你听 | 你在名为弱小的深渊 究竟看见过什么 | 天空中出现了一种罕见的天文现象

搬运于2025-08-24 23:01:00，当前版本为作者最后更新于2024-08-03 14:59:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面已经告诉我们了：$i$ 处的积水为 $H-h_i$，其中 $H$ 为 $i$ 左侧的最大值和 $i$ 右侧的最大值中的较小值。我们分成 $\sum H$ 和 $\sum h_i$ 两部分计算。

$\sum h_i$ 是好计算的，这就是 $2^{n-1}\sum (a_i+b_i)$。（你可以考虑计算每个位置的贡献）

对于 $\sum H$，我们不妨采用这样一种方式计算：把 $H$ 拆成 $\sum\limits_{X=1}^{\infty}[H\ge X]$，也就是枚举 $X$，计算每个位置 $H\ge X$ 的方案数之和。

我们对 $X$ 从大到小做扫描线，将 $\ge X$ 的设为 $1$，$\le X$ 的设为 $0$。这样每个位置就有三种状态：$a_i,b_i$ 中恰好有 $0/1/2$ 个 $1$。我们现在要给每个位置选一个 $a_i$ 或 $b_i$，并统计有多少位置 $i$ 满足 $[1,i]$ 和 $[i,n]$ 中都至少有一个 $1$，对这样的数量求和。

我们分类讨论一下：当存在至少一个位置有 $2$ 个 $1$ 的时候，设最左边的为 $L$，最右边的为 $R$，那么 $[L,R]$ 中的位置任意填都可以满足，$[1,L-1]$ 中的只需要满足前缀中有 $1$，$[R+1,n]$ 中的只需要满足后缀中有 $1$。

假设正在统计 $x\in [1,L-1]$ 的贡献，设 $[1,x-1]$ 中有 $p$ 个位置有 $1$ 个 $1$，那么方案数为 $(2^p-1)2^{x-p}=2^x-2^{x-p}$。前面的这个贡献是固定的，后面这个贡献每当 $x$ 前面出现 $1$ 的时候就会除以 $2$，可以用一个线段树维护，当扫描线将某些 $0$ 修改成 $1$ 的时候做一个后缀乘。$[R+1,n]$ 的贡献同理。

当不存在位置有 $2$ 个 $1$ 的时候，设 $x$ 前面有 $cL$ 个 $1$，右边有 $cR$ 个 $1$，那么贡献为 $(2^{cL}-1)(2^{cR}-1)2^{n-cL-cR}$，后面这个是个定值（扫到目前的 $X$ 对于所有 $x$ 来说 $cL+cR$ 都相等），前面的拆开后也可以类似上面一部分用两棵线段树维护。

但是发现如果当前位置是 $1$，这个贡献是有问题的，因为自己选了 $1$ 就同时满足了前缀和后缀，稍微分类讨论一下就可以了。

总时间复杂度 $\mathcal O(n\log n)$。

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
ll read(){
	ll 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;
}
void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const ll N=5e5+9,Mod=1e9+7,inv2=(Mod+1)/2;
ll n,a[N],b[N],L,R,cnt[N],tmp[N<<1],k,pw2[N],ta[N],tb[N],pre[N],bin[N],pre2[N];
ll pw(ll x,ll p){
    ll res=1;
    while(p){
        if(p&1)res=res*x%Mod;
        x=x*x%Mod,p>>=1;
    }
    return res;
}
struct Tree{
    ll tr[N<<2],tag[N<<2];
    void Pushup(ll x){
        tr[x]=(tr[x<<1]+tr[x<<1|1])%Mod;
    }
    void Build(ll x,ll l,ll r,ll v){
        tag[x]=1;
        if(l==r){
            tr[x]=v;
            return ;
        }
        ll mid=(l+r)>>1;
        Build(x<<1,l,mid,v);
        Build(x<<1|1,mid+1,r,v);
        Pushup(x);
    }
    void Pushtag(ll x,ll v){
        tr[x]=tr[x]*v%Mod;
        tag[x]=tag[x]*v%Mod;
    }
    void Pushdown(ll x){
        if(tag[x]==1)return ;
        Pushtag(x<<1,tag[x]);
        Pushtag(x<<1|1,tag[x]);
        tag[x]=1;
    }
    void Upd(ll x,ll l,ll r,ll ql,ll qr,ll v){
        if(ql>qr)return ;
        if(l>qr||r<ql)return ;
        if(ql<=l&&r<=qr){
            Pushtag(x,v);
            return ;
        }
        ll mid=(l+r)>>1;
        Pushdown(x);
        Upd(x<<1,l,mid,ql,qr,v);
        Upd(x<<1|1,mid+1,r,ql,qr,v);
        Pushup(x);
    }
    void Cov(ll x,ll l,ll r,ll u,ll v){
        if(l>u||r<u)return ;
        if(l==r){
            tr[x]=v;
            return ;
        }
        ll mid=(l+r)>>1;
        Pushdown(x);
        Cov(x<<1,l,mid,u,v);
        Cov(x<<1|1,mid+1,r,u,v);
        Pushup(x);
    }
    ll Query(ll x,ll l,ll r,ll ql,ll qr){
        if(l>qr||r<ql||ql>qr)return 0;
        if(ql<=l&&r<=qr)return tr[x];
        ll mid=(l+r)>>1;
        Pushdown(x);
        return (Query(x<<1,l,mid,ql,qr)+Query(x<<1|1,mid+1,r,ql,qr))%Mod;
    }
}T1,T2;
vector<ll>vec[N<<1];
bool Med;
int main(){
    // freopen("wall.in","r",stdin);
    // freopen("wall.out","w",stdout);
    n=read();
    rep(i,1,n)a[i]=read();
    rep(i,1,n)b[i]=read();
    rep(i,1,n)tmp[i]=a[i];
    rep(i,1,n)tmp[i+n]=b[i];
    pw2[0]=1;
    rep(i,1,n)pw2[i]=pw2[i-1]*2%Mod;
    sort(tmp+1,tmp+(n<<1)+1);
    k=unique(tmp+1,tmp+(n<<1)+1)-tmp-1;
    rep(i,1,n){
        ta[i]=lower_bound(tmp+1,tmp+k+1,a[i])-tmp;
        tb[i]=lower_bound(tmp+1,tmp+k+1,b[i])-tmp;
    }
    T1.Build(1,1,n,pw2[n]),T2.Build(1,1,n,pw2[n]);
    rep(i,1,n){
        vec[ta[i]].push_back(i);
        vec[tb[i]].push_back(i);
    }
    rep(i,0,n-1)pre[i]=((pw2[n]+pw2[n-i])%Mod*(i+1)%Mod-2*pw2[n-i]%Mod*(pw2[i+1]-1)%Mod+Mod)%Mod;
    rep(i,0,n-1)pre2[i]=((pw2[n]+pw2[n-i-1])%Mod*(i+1)%Mod-2*pw2[n-i]%Mod*(pw2[i+1]-1)%Mod+Mod)%Mod;
    ll ans=0,c1=0;
    per(i,k,1){
        for(ll x:vec[i]){
            bin[x]++;
            if(bin[x]==2){
                if(!L){
                    L=R=x;
                    T1.Build(1,1,n,pw2[n]);
                    T2.Build(1,1,n,pw2[n]);
                    rep(j,1,L){
                        if(bin[j]==1)T1.Upd(1,1,n,j,L,inv2);
                    }
                    rep(j,R+1,n){
                        if(bin[j]==1)T2.Upd(1,1,n,R,j,inv2);
                    }
                }
                else{
                    L=min(L,x);
                    R=max(R,x);
                }
            }
            else {
                c1++;
                if(!L){
                    T1.Upd(1,1,n,x+1,n,inv2);
                    T2.Upd(1,1,n,1,x-1,inv2);
                }
                else {
                    if(x<=L)T1.Upd(1,1,n,x,L,inv2);
                    if(x>=R)T2.Upd(1,1,n,R,x,inv2);
                }
            }
        }
        ll len=(i==1?tmp[i]:tmp[i]-tmp[i-1])%Mod;
        // cout<<"current "<<len<<" "<<L<<" "<<R<<endl;
        if(!L){
            ll coef=((pw2[n]+pw2[n-c1]+Mod)*n%Mod-T1.tr[1]-T2.tr[1]+Mod*2)%Mod;
            ll qd=pre[c1-1],nqd=pre2[c1-1];
            coef=(coef-nqd+qd*inv2%Mod+c1*pw2[n-1]%Mod+Mod)%Mod;
            // cout<<coef<<endl;
            ans=(ans+coef*len)%Mod;
        }
        else {
            ll coef=(pw2[n]*n%Mod-T1.Query(1,1,n,1,L-1)-T2.Query(1,1,n,R+1,n)+Mod*2)%Mod;
            // cout<<coef<<endl;
            ans=(ans+coef*len)%Mod;
        }
    }
    rep(i,1,n)ans=(ans-pw2[n-1]*(a[i]+b[i])%Mod+Mod)%Mod;
    write(ans);
	return 0;
}