CF2152F Triple Attack 题解

注意到答案按奇偶位置可以划为两个序列，相邻位置差

>z

。

而任意两个这样的不交序列一定可以可以拼成答案，充要性易证，而选择

(l,l+1)

作为两序列开头是不劣的。

而一个位置贪心的跳时，后继是唯一的，使用树刻画该结构，则易知

(i,i+1)

贪心跳跃首次交在

w=\operatorname{LCA}(i,i+1)

处，此时取一个跳到

w+1

处即可归约到

(w,w+1)

，倍增处理这种跳跃即可，时间复杂度

O((n+q)\log n)

。

为什么我赛时写的这么不牛呢，代码如下（没用 LCA，而是大力分段讨论，非常不美）：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N=250005;
int a[N],fa[N][23],fa2[N][23],c[N][23],p[N],d[N],n,q,z,K,t;
int query(int l,int r)
{
	int u,v,s;
	s=2;
	for(int i=K; i>=0; --i)
		if(fa2[l][i]<=r)
			s+=c[l][i],l=fa2[l][i];
	if(l==r)
		--s;
	else
	{
		u=l,v=l+1;
		for(int i=K; i>=0; --i)
			if(fa[u][i]<=r)
				s+=1<<i,u=fa[u][i];
		for(int i=K; i>=0; --i)
			if(fa[v][i]<=r)
				s+=1<<i,v=fa[v][i];
	}
	return s;
}
void solve()
{
	int u,v,l,r,s;
	cin>>n>>z,K=__lg(n);
	for(int i=1; i<=n; ++i)
		cin>>a[i];
	for(int i=1; i<=n; ++i)
		fa[i][0]=upper_bound(a+1,a+1+n,a[i]+z)-a;
	fa[n+1][0]=n+1;
	for(int j=1; j<=K; ++j)
		for(int i=1; i<=n+1; ++i)
			fa[i][j]=fa[fa[i][j-1]][j-1];
	p[t=1]=1;
	for(int i=1; i<n; ++i)
		if(a[i+1]-a[i]<=z)
		{
			l=i,r=i+1,u=0;
			for(int j=K; j>=0; --j)
				if(fa[l][j]!=fa[r][j])
					l=fa[l][j],r=fa[r][j],u+=1<<j;
			if(fa[l][0]==fa[r][0]&&fa[l][0]<=n)
				c[i][0]=u+1<<1,fa2[i][0]=fa[l][0];
			else
			{
				l=i+1,r=fa[i][0],u=1;
				for(int j=K; j>=0; --j)
					if(fa[l][j]!=fa[r][j])
						l=fa[l][j],r=fa[r][j],u+=1<<j+1;
				if(fa[l][0]==fa[r][0]&&fa[l][0]<=n)
					c[i][0]=u+2,fa2[i][0]=fa[l][0];
				else
					c[i][0]=0,fa2[i][0]=n+1;
			}
		}
		else
			fa2[i][0]=n+1,p[++t]=i+1;
	fa2[n][0]=n+1;
	p[++t]=n+1;
	fa2[n+1][0]=n+1;
	for(int j=1; j<=K; ++j)
		for(int i=1; i<=n+1; ++i)
			fa2[i][j]=fa2[fa2[i][j-1]][j-1],c[i][j]=c[i][j-1]+c[fa2[i][j-1]][j-1];
	for(int i=1; i<t; ++i)
		d[i]=d[i-1]+query(p[i],p[i+1]-1);
	cin>>q;
	while(q--)
	{
		cin>>l>>r;
		u=upper_bound(p+1,p+1+t,l)-p,v=upper_bound(p+1,p+1+t,r)-p-1;
		if(u>v)
			s=query(l,r);
		else
			s=d[v-1]-d[u-1]+query(l,p[u]-1)+query(p[v],r);
		cout<<s<<'\n';
	}
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	int T;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

CF2152F Triple Attack 题解

文章操作

相关推荐

评论

CF2152F Triple Attack 题解