自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 22:32:28，当前版本为作者最后更新于2025-01-08 13:16:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

对于询问，贪心的从左到右扫一遍，每次选出当前左端点往右覆盖最长的线段。

对于每个 $i\in [1,n]$，预处理出 $d_i$ 表示以 $i$ 为左端点的最长线段长度，那么询问就是不断执行 $a=a+d_a$，直到 $a\ge b$ 为止。

我们把 $i$ 向 $i+d_i$ 连边，这样 $n$ 个点就构成了一棵以 $n$ 为根的有根树，询问就是求 $a$ 的第一个 $\ge b$ 的祖先。

先考虑怎么求出 $d_i$，对于每种颜色 $(l_i,r_i,k_i)$，相当于 $\forall j\in [1,k_i]$，$i\in[l,r-j]$ 的 $d_i\ge j$。可以把每种颜色拆成一个区间和 $k_i$ 个单点（为了方便预处理直接拆成 $k_i$ 个区间）。

设 $K=\max(k_i)$，由于 $d_i\le K\le 10$ 因此可以对于每种长度 $j$ 求出 $O(m)$ 个区间的并集，并集中的 $d_i\ge j$。

同时可以发现，$j$ 的并集一定包含 $j+1$ 的并集，因此可以用 $j$ 的并集，减去 $j+1$ 的并集，得到 $d_i=j$ 的区间，使用双指针可以做到线性。

这部分预处理的时间复杂度为 $O(mK\log m)$，瓶颈在于给区间排序。

但是 $n$ 很大，不能暴力建树，考虑进行缩点。

如果一条链满足，链中每个点到它父亲的距离一样，就可以进行缩点，仅保留链底，链顶，以及相邻两点的距离，这样我们仍然可以求出每个点在树上的深度。

如果一段区间 $[l,r]$ 满足 $\forall i\in [l,r],d_i=j$，那么可以仅保留开头和末尾的 $j$ 个点，中间的点都可以缩起来。

我们称保留下来的点为关键点，通过之前的预处理可以发现，长度为 $n$ 的序列可以划分为 $O(m)$ 个 $d_i$ 相同的区间和 $O(mK)$ 个单点，因此关键点数是 $O(mK)$ 的。

求出关键点后，考虑如何建树，我们需要找到每个关键点缩点后的父亲。因为原树每条边的长度 $\le K$，并且不存在边 $(a,b)$ 和 $(c,d)$，使得 $a\lt c\lt d\lt b$，因为这样 $c$ 一定可以到达 $b$。因此，每个关键点的缩点后的父亲在关键点序列中到它的距离也 $\le K$，直接暴力枚举即可，复杂度 $O(mK^2)$。

对于询问 $(a,b)$，需要找到 $a$ 所在链的链底，二分找到 $\le a$ 的第一个关键点，同样到链底的距离 $\le K$。然后找到 $\le b$ 的第一个关键点祖先即可算出距离，这里我写倍增被卡常了，换成求出 DFS 序后 $O(K)$ 枚举就行了。

时间复杂度 $O(mK(\log m+K)+q(\log m+K)$)，空间复杂度 $O(mK)$。

参考代码：

#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;
}