题解：P10764 [BalticOI 2024] Wall
Petit_Souris
·
·
题解
题面已经告诉我们了：i 处的积水为 H-h_i，其中 H 为 i 左侧的最大值和 i 右侧的最大值中的较小值。我们分成 \sum H 和 \sum h_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)$。
```cpp
#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;
}
```