题解：P11554 [ROIR 2016] 假期旅行 (Day 1)

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
const int Log=20;

int n,m,k,q;

vector<pair<int,int>> vec[maxn];
int up[maxn][Log];

int ask(int s,int t){
	int ans=0;
	for(int i=19;i>=0;i--)
		if(up[s][i]<t) ans+=(1<<i),s=up[s][i];
	if(up[s][0]>=t) return ans+1;
	return -1;
}

#define fi first
#define se second
signed main(){
	freopen("trip.in","r",stdin);
	freopen("trip.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,s,t,id;i<=m;i++){
		scanf("%d%d%d",&s,&t,&id);
		vec[id].push_back({s,t});
	}	
	
	for(int i=1;i<=k;i++){
		sort(vec[i].begin(),vec[i].end());
		int u=1;
		for(auto& v:vec[i]){
			if(v.fi>u) up[u][0]=max(up[u][0],v.fi);
			u=max(u,v.se);
		}
		if(u<=n) up[u][0]=n;
	}
	
	for(int i=1;i<=n;i++) up[i][0]=max(up[i][0],up[i-1][0]);
	for(int i=1;i<20;i++)
		for(int j=1;j<=n;j++)
			up[j][i]=up[up[j][i-1]][i-1];
			
	scanf("%d",&q);
	while(q--){
		int s,t;
		scanf("%d%d",&s,&t);
		printf("%d\n",ask(s,t));
	}
	return 0;
}