【分治】BZOJ4979 [Lydsy八月月赛] 凌晨三点的宿舍

三点的宿舍"/>

【分治】BZOJ4979 [Lydsy八月月赛] 凌晨三点的宿舍

【题目】
原题地址
给定一个 n n $n$栋的公寓，第i" role="presentation">ii$i$栋公寓高 hi h i $h_i$，对于一个房间，它上下左右四个方向的房间和它距离为1。现在有 m m $m$个亮灯的房间，问这些房间中距离不超过k" role="presentation">kk$k$的有多少对。

【题目分析】
第一眼看到这题，感觉这是一棵树。又看了看数据范围，不会是个树分治吧？
不过想了一会发现不是很可做，然后考虑单独抽出一段区间的公寓怎么做，然后就可以分治了。
（实际上就是一眼看破是分治了好不好，虽然我不太会做啦）

【解题思路】
这道题还是不错的qwq。
对于两个房间 A,B A , B $A,B$，不妨设 xA≤xB x A ≤ x B $x_A\leq x_B$，那么有：

dis(A,B)=xB−xA+yA+yB−2×min(yA,yB,hxA,hxA+1,…,hxB) d i s ( A , B ) = x B − x A + y A + y B − 2 × m i n ( y A , y B , h x A , h x A + 1 , … , h x B ) $$dis(A,B) = x_B -x_A + y_A + y_B -2\times min(y_A,y_B,h_{x_A},h_{x_{A+1}},\dots ,h_{x_B})$$
若 xA=xB x A = x B $x_A =x_B$，那么直接按照 y y $y$排序然后双指针统计答案即可，接下来只需要考虑xA&lt;xB" role="presentation">xA<xBxA<xB$x_A < x_B$的情况。
对序列 h h $h$进行分治，设solve(l,r)" role="presentation">solve(l,r)solve(l,r)$solve(l,r)$表示处理所有 l≤xA<xB≤r l ≤ x A < x B ≤ r $l \leq x_A < x_B \leq r$ 的点对。
取 mid=⌊l+r2⌋ m i d = ⌊ l + r 2 ⌋ $mid =\lfloor \frac {l+r} 2 \rfloor$，那么递归调用 solve(l,mid) s o l v e ( l , m i d ) $solve(l,mid)$ 和 solve(mid+1,r) s o l v e ( m i d + 1 , r ) $solve(mid+1,r)$ 后，只需要处理 l≤xA≤mid<xB≤r l ≤ x A ≤ m i d < x B ≤ r $l \leq x_A \leq mid < x_B \leq r$ 的点对。
设 fi f i $f_i$表示 min(hi,hi+1,…,hmid) m i n ( h i , h i + 1 , … , h m i d ) $min(h_i,h_{i+1},\dots,h_{mid})$， gi g i $g_i$表示 min(hmid+1,…,hi−1,hi) m i n ( h m i d + 1 , … , h i − 1 , h i ) $min(h_{mid+1},\dots,h_{i-1},h_i)$，则：
dis(A,B)=xB−xA+yA+yB−2×min(yA,yB,hxA,hxA+1,…,hxB)=xB−xA+yA+yB−2×min(min(yA,fxA),min(yB,gxB)) d i s ( A , B ) = x B − x A + y A + y B − 2 × m i n ( y A , y B , h x A , h x A + 1 , … , h x B ) = x B − x A + y A + y B − 2 × m i n ( m i n ( y A , f x A ) , m i n ( y B , g x B ) ) $$dis(A,B) = x_B -x_A + y_A + y_B -2\times min(y_A,y_B,h_{x_A},h_{x_{A+1}},\dots ,h_{x_B}) \\ \qquad \qquad \quad= x_B -x_A + y_A + y_B -2\times min(min(y_A,f_{x_A}),min(y_B,g_{x_B}))$$
枚举 min m i n $min$落在 A A $A$还是B" role="presentation">BB$B$，扫描线 + 树状数组统计即可。
时间复杂度 O(nlogn+mlog2n) O ( n l o g n + m l o g 2 n ) $O(nlogn + mlog^2n)$。

话说我迷之RE，怒开2倍过了。。。

【参考代码】

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=2e5+10;
const int M=N*3;
int n,m,k,tot,T;
int h[N<<1],g[N<<1],q[N<<1],head[N<<1];
int tr[M<<1],vis[M<<1];
LL ans;struct Tway
{int v,nex;Tway(){}Tway(int vv,int nexx){v=vv;nex=nexx;}
};
Tway e[M<<1];struct Tnode
{int w,x,y;Tnode(){}Tnode(int ww,int xx,int yy){w=ww;x=xx;y=yy;}
};
Tnode qa[N],qb[N];void add(int u,int v)
{e[++tot]=(Tway){v,head[u]};head[u]=tot;
}bool cmp(Tnode A,Tnode B)
{return A.w<B.w;
}void work(int x)
{int qs=0;for(int i=head[x];i;i=e[i].nex)q[++qs]=e[i].v;if(qs<=1)return;sort(q+1,q+qs+1);for(int i=1,j=1;i<=qs;++i){while(j<qs && q[j+1]-q[i]<=k)++j;ans+=j-i;}
}int lowbit(int x)
{return x&(-x);
}void update(int x)
{x+=N;for(;x<M;x+=lowbit(x))if(vis[x]<T)vis[x]=T,tr[x]=1;elsetr[x]++;
}void query(int x)
{x=min(x+N,M-1);for(;x>0;x-=lowbit(x))if(vis[x]==T)ans+=tr[x];
}void solve(int l,int r)
{if(l==r)return;int mid=(l+r)>>1,ca=0,cb=0;solve(l,mid);solve(mid+1,r);for(int i=mid,tp=N;i>=l;--i){tp=min(tp,h[i]);for(int j=head[i];j;j=e[j].nex)qa[++ca]=(Tnode){min(tp,e[j].v),i,e[j].v};}for(int i=mid+1,tp=N;i<=r;++i){tp=min(tp,h[i]);for(int j=head[i];j;j=e[j].nex)qb[++cb]=(Tnode){min(tp,e[j].v),i,e[j].v};}if(!ca || !cb)return;sort(qa+1,qa+ca+1,cmp);sort(qb+1,qb+cb+1,cmp);++T;for(int i=ca,j=cb;i;--i){while(j && qa[i].w<=qb[j].w)update(qb[j].x+qb[j].y),--j;query(k+2*qa[i].w+qa[i].x-qa[i].y);}++T;for(int i=cb,j=ca;i;--i){while(j && qb[i].w<qa[j].w)update(qa[j].y-qa[j].x),--j;query(k+2*qb[i].w-qb[i].x-qb[i].y);}
}int main()
{freopen("BZOJ4979.in","r",stdin);freopen("BZOJ4979.out","w",stdout);scanf("%d%d",&n,&k);for(int i=1;i<=n;++i)scanf("%d",&h[i]);scanf("%d",&m);for(int i=1;i<=m;++i){int u,v;scanf("%d%d",&u,&v);add(u,v);}for(int i=1;i<=n;++i)work(i);solve(1,n);printf("%lld\n",ans);return 0;
}

【总结】
水了这么久题目终于遇到一道难一点的分治题了qwq。