专栏文章

题解：P7719 「EZEC-10」多彩的线段

CC1942huangjiaxu管理员
P7719题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqke1xo
此快照首次捕获于
2025/12/04 06:14
3 个月前
此快照最后确认于
2025/12/04 06:14
3 个月前
查看原文
对于询问，贪心的从左到右扫一遍，每次选出当前左端点往右覆盖最长的线段。
对于每个 i∈[1,n]i\in [1,n]，预处理出 did_i 表示以 ii 为左端点的最长线段长度，那么询问就是不断执行 a=a+daa=a+d_a，直到 a≥ba\ge b 为止。
我们把 ii 向 i+dii+d_i 连边，这样 nn 个点就构成了一棵以 nn 为根的有根树，询问就是求 aa 的第一个 ≥b\ge b 的祖先。
先考虑怎么求出 did_i，对于每种颜色 (li,ri,ki)(l_i,r_i,k_i)，相当于 ∀j∈[1,ki]\forall j\in [1,k_i]，i∈[l,r−j]i\in[l,r-j] 的 di≥jd_i\ge j。可以把每种颜色拆成一个区间和 kik_i 个单点（为了方便预处理直接拆成 kik_i 个区间）。
设 K=max⁡(ki)K=\max(k_i)，由于 di≤K≤10d_i\le K\le 10 因此可以对于每种长度 jj 求出 O(m)O(m) 个区间的并集，并集中的 di≥jd_i\ge j。
同时可以发现，jj 的并集一定包含 j+1j+1 的并集，因此可以用 jj 的并集，减去 j+1j+1 的并集，得到 di=jd_i=j 的区间，使用双指针可以做到线性。
这部分预处理的时间复杂度为 O(mKlog⁡m)O(mK\log m)，瓶颈在于给区间排序。
但是 nn 很大，不能暴力建树，考虑进行缩点。
如果一条链满足，链中每个点到它父亲的距离一样，就可以进行缩点，仅保留链底，链顶，以及相邻两点的距离，这样我们仍然可以求出每个点在树上的深度。
如果一段区间 [l,r][l,r] 满足 ∀i∈[l,r],di=j\forall i\in [l,r],d_i=j，那么可以仅保留开头和末尾的 jj 个点，中间的点都可以缩起来。
我们称保留下来的点为关键点，通过之前的预处理可以发现，长度为 nn 的序列可以划分为 O(m)O(m) 个 did_i 相同的区间和 O(mK)O(mK) 个单点，因此关键点数是 O(mK)O(mK) 的。
求出关键点后，考虑如何建树，我们需要找到每个关键点缩点后的父亲。因为原树每条边的长度 ≤K\le K，并且不存在边 (a,b)(a,b) 和 (c,d)(c,d)，使得 a<c<d<ba\lt c\lt d\lt b，因为这样 cc 一定可以到达 bb。因此，每个关键点的缩点后的父亲在关键点序列中到它的距离也 ≤K\le K，直接暴力枚举即可，复杂度 O(mK2)O(mK^2)。
对于询问 (a,b)(a,b)，需要找到 aa 所在链的链底，二分找到 ≤a\le a 的第一个关键点，同样到链底的距离 ≤K\le K。然后找到 ≤b\le b 的第一个关键点祖先即可算出距离，这里我写倍增被卡常了，换成求出 DFS 序后 O(K)O(K) 枚举就行了。
时间复杂度 O(mK(log⁡m+K)+q(log⁡m+K)O(mK(\log m+K)+q(\log m+K))，空间复杂度 O(mK)O(mK)。
参考代码：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5;
#define fi first
#define se second
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
template<class rd>
void read(rd &x){
	char c=getchar();
	for(;c<48||c>57;c=getchar());
	for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48);
}
int ty,n,m,q,d[N],p[N],dp[N],ct,Ans,in[N],out[N];
vector<int>e[N];
vector<pair<int,int> >vc[12],tt;
void dfs(int x){
	in[x]=++in[0];
	for(auto v:e[x])dfs(v);
	out[x]=in[0];
}
int main(){
	read(ty),read(n),read(m),read(q);
	for(int i=1,l,r,k;i<=m;++i){
		read(l),read(r),read(k);
		for(int j=1;j<=k;++j)vc[j].emplace_back(l,r-j);
	}
	for(int j=10;j;--j){
		sort(vc[j].begin(),vc[j].end());
		vector<pair<int,int> >tmp;
		for(int i=0;i<vc[j].size();++i){
			auto [l,r]=vc[j][i];
			while(i+1<vc[j].size()&&vc[j][i+1].fi<=r+1)++i,r=max(r,vc[j][i].se);
			tmp.emplace_back(l,r);
		}
		vc[j]=tmp;
		for(int i=0,o=0;i<vc[j].size();++i){
			auto [l,r]=vc[j][i];
			while(l<=r){
				while(o<vc[j+1].size()&&vc[j+1][o].fi<l)++o;
				if(o<vc[j+1].size()){
					if(vc[j+1][o].fi>r){
						tt.emplace_back(l,j);
						break;
					}
					if(vc[j+1][o].fi>l)tt.emplace_back(l,j);
					l=vc[j+1][o].se+1;
				}else{
					tt.emplace_back(l,j);
					break;
				}
			}
		}
	}
	sort(tt.begin(),tt.end());
	tt.emplace_back(n,0);
	for(int i=0;i+1<tt.size();++i){
		int lim=tt[i].fi+tt[i].se;
		if(i&&tt[i-1].se>tt[i].se)++lim;
		lim=min(lim,tt[i+1].fi);
		for(int j=tt[i].fi;j<lim;++j)
			++ct,p[ct]=j,d[ct]=tt[i].se;
	}
	p[++ct]=n;
	for(int i=ct-1;i;--i)
		for(int j=i+1;;++j)if((p[j]-p[i])%d[i]==0){
			e[j].emplace_back(i),dp[i]=dp[j]+(p[j]-p[i])/d[i];
			break;
		}
	dfs(ct);
	for(int i=1,a,b;i<=q;++i){
		read(a),read(b);
		if(ty)a^=Ans,b^=Ans;
		int u=upper_bound(p+1,p+ct+1,a)-p-1,v=upper_bound(p+1,p+ct+1,b)-p-1;
		while((a-p[u])%d[u]!=0)--u;
		Ans=-(a-p[u])/d[u];
		while(in[u]<in[v]||in[u]>out[v])--v;
		Ans+=dp[u]-dp[v];
		if(b!=p[v])Ans+=(b-p[v]-1)/d[v]+1;
		printf("%d\n",Ans);
	}
	return 0;
}

评论

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

正在加载评论...