自动搬运

查看原文

来自洛谷，原作者为

	VainSylphid 美しい音色で世界が鳴った

搬运于2025-08-24 23:05:13，当前版本为作者最后更新于2024-10-17 17:02:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简单题，第一部分做的比critnos的题解弱智但是也能过，第二部分比他的简单一点。

考虑怎么刻画题目给的这个东西，容易发现我们其实是要找到最后离开餐厅的感染者 $Q$，然后把从初始感染者 $P$ 进入餐厅的时刻 $S$ 到最后感染者 $Q$ 离开的时间 $T$ 这段时间内的感染者全部找出来。

那么首先考虑怎么找到最后一个人，这是比较容易的。首先特判掉初始感染者传染不了任何人的情况（$R-L<X$）。一个显然的观察是，随着 $X$ 减小，最后一个感染者离开的时间是单调不降的。不妨对每个人钦定一个唯一的后继，具体的，对于第 $i$ 个人，我们找到一个 $j$ 使得 $R_j > R_i$ 并且 $L_j$ 最小，然后钦定 $j$ 是 $i$ 的后继，这样我们就可以倍增维护向跳需要的最大 $X$ 值。

那么接下来我们需要维护的是有多少个 $[L,R]$ 与 $[S,T]$ 的交不小于 $X$。这是容易的，注意到符合条件的区间一定满足 $S+X\leq R\leq T$ 并且长度不小于 $X$，因为由第一部分可知不存在右端点大于 $T$ 的符合条件区间。这是二维偏序，扫描线即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
	ll L,R;
}t[100005];
ll n,m,p[100005],f[18][100005],g[18][100005],b[400005],tot;
bool cmp(ll A,ll B)
{
	return t[A].R < t[B].R;
}
struct quest{
	ll L,R,X;
}q[100005];
vector<quest> v[400005];
vector<ll> c[400005];
ll d[400005];
void update(ll x)
{
	while(x <= tot)
		d[x]++,x += (x & (-x));
}
ll query(ll x)
{
	ll ret = 0;
	while(x)
		ret += d[x],x -= (x & (-x));
	return ret;
}
ll ans[100005];
int main()
{
	scanf("%lld",&n);
	for(ll i = 1;i <= n;i++)
		scanf("%lld%lld",&t[i].L,&t[i].R),p[i] = i,b[++tot] = t[i].R,b[++tot] = t[i].R - t[i].L;
	sort(p + 1,p + 1 + n,cmp);
	ll pos = n,to = p[n];
	for(ll i = n;i;i--)
	{
		while(pos > 0 && t[p[pos]].R > t[p[i]].R)
		{
			if(t[p[pos]].L < t[to].L)
				to = p[pos];
			pos--;
		}
		f[0][p[i]] = to,g[0][p[i]] = t[p[i]].R - t[to].L;
		for(ll j = 1;j < 18;j++)
			f[j][p[i]] = f[j - 1][f[j - 1][p[i]]],g[j][p[i]] = min(g[j - 1][p[i]],g[j - 1][f[j - 1][p[i]]]);
	}
	scanf("%lld",&m);
	for(ll i = 1;i <= m;i++)
	{
		ll P,X;
		scanf("%lld%lld",&P,&X);
		if(t[P].R - t[P].L < X)
		{
			ans[i] = 1;
			continue;
		}
		ll tmp = P;
		for(ll j = 17;j >= 0;j--)
			if(g[j][tmp] >= X)
				tmp = f[j][tmp];
		q[i] = {t[P].L + X - 1,t[tmp].R,X},b[++tot] = t[P].L + X - 1,b[++tot] = X - 1;
	}
	sort(b + 1,b + 1 + tot);
	tot = unique(b + 1,b + 1 + tot) - b - 1;
	for(ll i = 1;i <= m;i++)
	{
		if(ans[i])
			continue;
		ll t1 = lower_bound(b + 1,b + 1 + tot,q[i].L) - b;
		ll t2 = lower_bound(b + 1,b + 1 + tot,q[i].R) - b;
		ll t3 = lower_bound(b + 1,b + 1 + tot,q[i].X - 1) - b;
		v[t1].push_back({t3,-1,i}),v[t2].push_back({t3,1,i});
	}
	for(ll i = 1;i <= n;i++)
	{
		ll t1 = lower_bound(b + 1,b + 1 + tot,t[i].R) - b;
		ll t2 = lower_bound(b + 1,b + 1 + tot,t[i].R - t[i].L) - b;
		c[t1].push_back(t2);
	}
	ll ccnt = 0;
	for(ll i = 1;i <= tot;i++)
	{
		for(auto j : c[i])
			update(j),ccnt++;
		for(auto j : v[i])
			ans[j.X] += j.R * (ccnt - query(j.L));
	}
	for(ll i = 1;i <= m;i++)
		printf("%lld\n",ans[i]);
	return 0;
}