自动搬运

查看原文

来自洛谷，原作者为

	Kubic Go straight ahead 'til we've lost it all.

搬运于2025-08-24 22:39:33，当前版本为作者最后更新于2022-08-12 15:35:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一个不太一样的做法，想的时候一直以为是 $2\log$，写的时候发现实际上很容易 $1\log$。

首先考虑 $l=1,r=n$ 怎么做。

可以发现两两可以匹配等价于任意相邻两个可以匹配。

于是考虑对于每个 $i$ 求出 $L_i,R_i$ 分别表示 $i$ 左右两边第一个 $\ge a_i+d$ 的位置。把它看成数轴上的区间 $(L_i,R_i)$。一组方案合法当且仅当选出的所有 $i$ 所对应的线段两两不交。

此时有一个非常关键的 observation：这些线段相互之间的关系只有包含和相离。

证明只需反证即可，这里不再赘述。

对于一个线段，如果它包含其它线段，那么选择它肯定不优。称一个线段为“好线段”当且仅当它不包含其它线段。显然我们一定可以选择所有的“好线段”，而这就是我们的最优策略。

此时问题就变为了统计“好线段”的个数。

通过分析可以得到，对于一个 $i$，$(L_i,R_i)$ 是一条好线段等价于 $\forall j\in(L_i,R_i),a_i<a_j$。

我们可以对于每个 $i$ 求出左右两边第一个比它小的位置，进一步可以求出最大的 $d$ 使得 $(L_i,R_i)$ 是一个“好线段”，设这个值为 $w_i$。我们的问题就转化为了求出区间中有多少个 $\ge d$ 的 $w_i$。直接上主席树即可。

吗？

我们会发现可能会有一个 $i$，满足 $(L_i,R_i)$ 中存在 $<a_i$ 的值，但是这个值在询问的区间外。这种情况下 $i$ 实际上是可以选的，但是我们会认为它不能选，导致算出的答案偏小。

一种无脑的解决方案是直接上三维数点干掉这个情况，时空复杂度都是 $O(n\log ^2n)$，不知道能不能过。

可以观察到，左右两个边界处各有至多一个 $i$ 被我们漏掉了，考虑如何找到左边界处的 $i$，右边界处的可以类似处理。

分析 $i$ 的性质：

• $i$ 一定是一个 $[l,r]$ 的前缀最小值。

• $i$ 一定满足 $L_i<l$，而对于所有 $[l,r]$ 的前缀最小值而言，满足 $L_i<l$ 的 $i$ 一定是一段前缀。

• $i$ 一定是这段前缀中的最后一个。

上面的三条性质的证明都比较容易，这里不再赘述。

有了这些性质，我们可以直接在 $[l,r]$ 的所有前缀最小值构成的序列上二分找到唯一可能合法的 $i$，再判断其是否合法即可。

前缀最小值序列可以用可持久化数据结构维护，也可以建成一棵树形结构并把二分改为倍增。

至此，我们在 $O((n+m)\log n)$ 的时间复杂度内解决了这道题。

参考代码：

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define mid ((l+r)/2)
#define clz __builtin_clz
const int N=100005,M=4000005,up=1e9;
int n,a[N],st[N],w[N],w1[N],w2[N],fa1[17][N],fa2[17][N],mx[17][N];
int cntS,rt[N];struct Seg {int vl,ch[2];}sg[M];
int qMx(int l,int r)
{
	if(l>r) return 0;int t=31-clz(r-l+1);
	return max(mx[t][l],mx[t][r-(1<<t)+1]);
}
void upd(int p,int &p1,int l,int r,int x)
{
	sg[p1=++cntS]=sg[p];++sg[p1].vl;if(l==r) return;
	if(x<=mid) upd(sg[p].ch[0],sg[p1].ch[0],l,mid,x);
	else upd(sg[p].ch[1],sg[p1].ch[1],mid+1,r,x);
}
int qSm(int p,int l,int r,int qL,int qR)
{
	if(!p || qL>qR) return 0;
	if(l>=qL && r<=qR) return sg[p].vl;int res=0;
	if(qL<=mid) res=qSm(sg[p].ch[0],l,mid,qL,qR);
	if(qR>mid) res+=qSm(sg[p].ch[1],mid+1,r,qL,qR);return res;
}
void init(int n1,vector<int> a1)
{
	n=n1;for(int i=1;i<=n;++i) a[i]=mx[0][i]=a1[i-1];
	for(int i=1;i<=n;++i)
	{
		while(st[0] && a[i]<a[st[st[0]]]) --st[0];
		fa1[0][i]=st[0]?st[st[0]]:0;st[++st[0]]=i;
		for(int j=1;j<=16;++j) fa1[j][i]=fa1[j-1][fa1[j-1][i]];
	}st[0]=0;for(int i=0;i<=16;++i) fa2[i][n+1]=n+1;
	for(int i=n;i;--i)
	{
		while(st[0] && a[i]<a[st[st[0]]]) --st[0];
		fa2[0][i]=st[0]?st[st[0]]:n+1;st[++st[0]]=i;
		for(int j=1;j<=16;++j) fa2[j][i]=fa2[j-1][fa2[j-1][i]];
	}
	for(int i=1;i<=16;++i) for(int j=1;j+(1<<i)-1<=n;++j)
		mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
	for(int i=1;i<=n;++i)
	{
		w1[i]=qMx(fa1[0][i]+1,i-1)-a[i];
		w2[i]=qMx(i+1,fa2[0][i]-1)-a[i];w[i]=min(w1[i],w2[i]);
		if(w[i]>0) upd(rt[i-1],rt[i],1,up,w[i]);else rt[i]=rt[i-1];
	}
}
bool chk(int x,int l,int r,int d)
{
	if(x<l || x>r || w[x]>=d) return 0;
	if(w1[x]<d && fa1[0][x]>=l) return 0;
	if(w2[x]<d && fa2[0][x]<=r) return 0;return 1;
}
int max_towers(int l,int r,int d)
{
	int t,t1=++r,t2=++l,res;
	res=qSm(rt[r],1,up,d,up)-qSm(rt[l-1],1,up,d,up);
	for(int i=16;i>=0;--i)
	{t=fa1[i][t1];if(t>=l && qMx(t+1,r)<a[t]+d) t1=t;}
	for(int i=16;i>=0;--i)
	{t=fa2[i][t2];if(t<=r && qMx(l,t-1)<a[t]+d) t2=t;}
	return res+chk(t1,l,r,d)+(t1!=t2 && chk(t2,l,r,d));
}