解题过程(时间复杂度优化)

暴力

数据范围N<=1e5,Q<=1e5,暴力复杂度最差为$O(QN)$，就是对于每一个询问都从a到b跑一边，看需要多少天。

暴力后就可以根据分数进行下一步优化(但XCPC赛制并不允许查看分数，所以这是个事后诸葛亮......)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[100010],q,l,s[100010];
ll solve(ll x,ll y)
{
	ll day=0,t=0;
	for(ll i=x+1;i<=y;i++)
	{
		t+=a[i]-a[i-1];
		if(t>l)day++,t=0,i--;
	}
	if(t>0)day++;
	return day;
}
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
	scanf("%lld%lld",&l,&q);
	while(q--)
	{
		ll x,y;scanf("%lld%lld",&x,&y);
		if(x>y)swap(x,y);
		printf("%lld\n",solve(x,y));
	}
	return 0;
}

优化

然后我们就会得到这个76分的代码，注意到分数超过3/4，所以复杂度再优化半层即可......

暴力时间复杂度为$O(QN)$，其中Q是输入输出必须跑的一环，故无法改变，所以我们只能在N上做文章

N往下自然就是logN了，那我们要如何实现呢？？？

方法

再次分析题目，题目要求我们是每天尽量多赶路，但不能超过距离限制且要到达一个有酒店的点。

这时这一条坐标轴是不是就成了一条链，我们要在相同时间内尽量走得更远？

那就可以使用st表来暴力维护每个点向右走$2^k$天最远能到哪个酒店，然后就暴力跳。(虽然题目没有保证a<b，但我们swap一下就可以了)

这样一来，$O(QN)$就十分自然地降成$O(QlogN)$了，然后就能AC了...

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],st[N][21],n,L,q,x,y;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	scanf("%d%d",&L,&q);
	for(int l=1,r=1;l<=n;l++)
	{
		while(r<n&&a[r+1]-a[l]<=L)r++;
		st[l][0]=r;
	}
	for(int i=1;i<=20;i++)for(int j=1;j<=n;j++)st[j][i]=st[st[j][i-1]][i-1];
	while(q--)
	{
		scanf("%d%d",&x,&y);int ans=0;
		if(x>y)swap(x,y);
		for(int i=20;i>=0;i--)if(st[x][i]<y)x=st[x][i],ans+=(1<<i);
		printf("%d\n",ans+1);
	} 
	return 0;
}

tip

比赛时用了一个前缀和的思路来算，从酒店1开始处理，且中途没有改变起点，那自然是WA的，只有18分......

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[100010],q,l,s[100010],k[100010];
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
	scanf("%lld%lld",&l,&q);
	s[1]=0;k[1]=0;
	for(ll i=2;i<=n;i++)
	{
		k[i]=k[i-1]+a[i]-a[i-1];s[i]=s[i-1];
		//printf("%lld %lld\n",k[i],s[i]);
		if(k[i]==l)s[i]++,k[i]=0;
		else if(k[i]>l)s[i-1]++,i--,k[i]=0;
		//printf("%lld %lld\n\n",k[i],s[i]);
	}
	//for(ll i=1;i<=n;i++)printf("%lld\n",s[i]);
	while(q--)
	{
		ll x,y;scanf("%lld%lld",&x,&y);
		if(x>y)swap(x,y);
		if(s[y]==s[x])puts("1");
		else printf("%lld\n",s[y]-s[x]);
	}
	return 0;
}

十分钟切掉的送分题，这题我以前好像做过。

其实没啥好讲的。只需要注意到从左到右和从右到左其实没什么区别。

直接 st 表暴力维护每个点往右 $2^k$ 天最远能到哪个酒店，然后就暴力跳。时间复杂度 $O(Q \log N)$。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],st[N][21];
signed main()
{
	int n,L;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	cin>>L;
	for(int l=1,r=1;l<=n;l++)
	{
		while(r<n&&a[r+1]-a[l]<=L)r++;
		st[l][0]=r;
	}
	for(int i=1;i<=20;i++)for(int j=1;j<=n;j++)st[j][i]=st[st[j][i-1]][i-1];
	int q;cin>>q;
	while(q--)
	{
		int x,y;cin>>x>>y;int ans=0;if(x>y)swap(x,y);
		for(int i=20;i>=0;i--)if(st[x][i]<y)x=st[x][i],ans+=(1<<i);
		cout<<ans+1<<'\n';
	} 
	return 0;
}

注意到现有的题解都没有关于 st 表正确性的说明，此处来补充一下。

st 表当中，我们取 $st_{i,j}$ 表示从第 $i$ 个酒店出发 最远 能走到哪里，也就是说，我们每天都会贪心的走到最远的酒店。

我们考虑从 $i$ 酒店开始最远能走到 $j$ 酒店，我们假定走到 $j-1$ 这一个酒店，此时我们剩下的距离是足够走到 $j$ 的，但在下一天开始时，这些距离就被清空，不再能产生贡献。也就是说，我们不仅舍弃了当下的贡献，还对后面没有任何帮助，所以这么走一定不会更优。所以我们每天一定都是走到最远的地方。

一天一天地跳显然超时，我们可以倍增预处理出从每个点跳$2^k$天能跳到哪里，倍增跳跃的同时记录天数，时间复杂度$O(Q log_2 N)$

预处理倍增数字$st[i][j]$应先枚举$j$，后枚举$i$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], st[N][25];
int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i]; 
    int L, q; cin >> L >> q;

    for (int i = 1; i <= n; i++)
        st[i][0] = upper_bound(a + 1, a + n + 1, a[i] + L) - a - 1;
    for (int j = 1; j <= 20; j++)
        for (int i = 1; i <= n; i++)
            st[i][j] = st[st[i][j - 1]][j - 1];

    while (q--)
    {
        int x, y, ans = 0; cin >> x >> y;
        if (x > y) swap(x, y);
        for (int i = 20; i >= 0; i--) if (st[x][i] < y)
            x = st[x][i], ans += (1 << i);
        
        cout << ans + 1 << "\n";
    }

    return 0;
}