专栏文章

solution - P12018

llittlebug
P12018题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min3ddxp
此快照首次捕获于
2025/12/01 19:54
3 个月前
此快照最后确认于
2025/12/01 19:54
3 个月前
查看原文
乱序模拟赛把这个放 D，痛失 AC /ll
画个图出来什么结论都有了啊。
首先注意到一个终点对应的起点一定是一段连续的区间。考虑从左往右递推，只关心每个特殊格子对应的起点区间，就可以证明。
然后从左往右递推一下求出来每个终点的覆盖范围，查询直接倍增就做完了喵。
具体地，在求出每个终点的覆盖范围之后，先求出对于每个区间左端点 ll，对应的最大的 rr，满足 [l,r][l,r] 内所有起点都可以走到同一个终点，然后再倍增处理出从 ll 开始 2j2^j 个区间能到达的最大 rr，就可以 O(log⁡)O(\log) 查询了。
代码：
CPP
// === / 走吧 就算我们无法让大雨停下 还有我 陪你在雨里放肆奔跑啊 / ===

int n,m,a[N],f[N][18],Q;
pii g[N<<1];
vector <int> b[N];
bitset <N<<1> bk;

il void solve()
{
	read(n,m),_::r(a,m);
	
	{
		rep(i,0,n+1) b[i].pb(i+m+1);
		rpe(i,m,1) b[a[i]].pb(i);
		rep(i,0,n+1) bk[b[i].back()]=1;
		
		auto upd=[](pii& a,const pii& b){chmin(a.st,b.st),chmax(a.nd,b.nd);};
		
		rep(i,0,m+n+2) g[i]={inf,-inf};
		rep(i,1,m)
		{
			b[a[i]].pop_back();
			bk[i]&&(upd(g[i],{a[i],a[i]}),1);
			upd(g[b[a[i]-1].back()],g[i]),upd(g[b[a[i]+1].back()],g[i]);
		}
		rep(i,0,n+1) bk[i+m+1]&&(upd(g[i+m+1],{i,i}),1);
	}
	
	{
		rep(i,0,n+1) g[i+m+1].nd>0 && (f[g[i+m+1].st][0]=g[i+m+1].nd+1);
		rep(i,1,n+1) chmin(chmax(f[i][0],f[i-1][0]),n+1);
		rep(j,1,17) rep(i,0,n+1) f[i][j]=f[f[i][j-1]][j-1];
	}
	
	read(Q); int l,r,ans;
	while(Q--)
	{
		read(l,r);
		ans=0;
		rpe(j,17,0) f[l][j]<=r&&(ans+=1<<j,l=f[l][j]);
		write(ans+1,'\n');
	}
}
华风夏韵，洛水天依！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...