自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:04:11，当前版本为作者最后更新于2024-09-29 18:20:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Problem Link

题目大意

给定 $n$ 棵树，位置在 $a_1\sim a_n$，一棵树能被砍当且仅当 $(a_i-h_i,a_i]$ 或 $[a_i,a_i+h_i)$ 中没有未被砍的树，且 $a_i-h_i/a_i+h_i$ 不能超过出 $[a_1,a_n]$ 的范围。

$q$ 次询问 $l,r$，询问如果只能砍第 $l\sim r$ 棵树，最多能砍几棵树。

数据范围：$n,q\le 5\times 10^5$。

思路分析

对每棵树 $i$ 分别考虑，容易发现一棵树能向左砍，当且仅当 $(a_i-h_i,a_i]$ 中的其他树要么可以向右砍，要么可以在 $[l,i]$ 范围内向左砍。

不难发现 $i$ 能向左看当且仅当 $L_i\ge l$，其中 $L_i$ 表示：如果想让 $i$ 向左砍，至少要砍掉左边多少树，同理能求出 $R_i$。

我们要求的就是有多少 $l\le L_i\le i\le r$ 或者 $l\le i\le R_i\le r$。

考虑二维数点，拆成 $[L_i,i],[i,R_i]$ 两个线段，被包含答案 $+1$，为了去重，包含 $[L_i,R_i]$ 的答案还要 $-1$。

然后考虑如何求 $L_i$：从 $j=i-1$ 开始，如果 $a_i-h_i<a_j$，那么需要砍掉 $j$：

• 如果 $a_j+h_j\le a_i$，直接向右砍，$j\gets j-1$。
• 否则只能向左砍，$j\gets L_j-1$。

那么 $L_i=j+1$，容易发现我们只要求出 $a_j+h_j>a_i$ 的线段并之外的第一个元素，线段树维护。

另一种做法是整体二分，即枚举一个左端点 $l$，从 $l$ 出发尝试砍掉每棵树，用一个栈维护上面的过程，判断每个树能不能向左砍就知道 $L_i\ge l$ 是否成立。

容易发现 $L_i<l,L_i\ge l$ 的两部分点互不影响，然后可以直接递归。

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

代码查询

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e5+5;
int n,q,a[MAXN],h[MAXN],L[MAXN],R[MAXN],ans[MAXN];
vector <int> o[MAXN];
vector <array<int,2>> ql[MAXN],qr[MAXN];
struct FenwickTree {
	int tr[MAXN],s;
	void init() { memset(tr,0,sizeof(tr)); }
	void add(int x) { for(;x;x&=x-1) ++tr[x]; }
	int qry(int x) { for(s=0;x<=n;x+=x&-x) s+=tr[x]; return s; }
}	T;
int f[MAXN],stk[MAXN],tp;
void solve(int l,int r,const vector<int>&id) {
	if(l==r) {
		for(int x:id) f[x]=l;
		return ;
	}
	int mid=(l+r+1)>>1;
	stk[tp=0]=mid-1;
	vector <int> li,ri;
	for(int i:id) {
		if(i<mid) { li.push_back(i); continue; }
		while(tp&&a[stk[tp]]+h[stk[tp]]<=a[i]) --tp;
		if(a[stk[tp]]>a[i]-h[i]) li.push_back(i),stk[++tp]=i;
		else ri.push_back(i);
	}
	solve(l,mid-1,li),solve(mid,r,ri);
}
signed main() {
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i) scanf("%d%d",&a[i],&h[i]);
	vector <int> id(n);
	iota(id.begin(),id.end(),1);
	a[0]=a[1],solve(0,n,id);
	for(int i=1;i<=n;++i) L[i]=f[i];
	reverse(a+1,a+n+1),reverse(h+1,h+n+1);
	for(int i=n;i;--i) a[i]*=-1;
	a[0]=a[1],solve(0,n,id);
	for(int i=1;i<=n;++i) R[n-i+1]=n-f[i]+1;
	for(int i=1,l,r;i<=q;++i) {
		scanf("%d%d",&l,&r),ql[l].push_back({r,i}),qr[r].push_back({l,i});
	}
	for(int i=1;i<=n;++i) o[R[i]].push_back(L[i]);
	for(int i=1;i<=n;++i) {
		T.add(L[i]);
		for(auto z:qr[i]) ans[z[1]]+=T.qry(z[0]);
	}
	T.init();
	for(int i=n;i>=1;--i) {
		T.add(n-R[i]+1);
		for(auto z:ql[i]) ans[z[1]]+=T.qry(n-z[0]+1);
	}
	T.init();
	for(int i=1;i<=n;++i) {
		for(int z:o[i]) T.add(z);
		for(auto z:qr[i]) ans[z[1]]-=T.qry(z[0]);
	}
	for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
	return 0;
}