题意

$n$ 个格子， $m$ 种走路方式，第 $i$ 个方式可以从 $l_i$ 走到 $r_i$ 花费代价 1。往左走不花代价。 $q$ 次询问，每次询问禁用一种方式，问 $s$ 到 $t$ 的最少花费（无解输出 -1)。

$n,m,q\leq2\times10^5$ 。

题解

每次只禁用一个的基本思想就是提前维护最优和次优。

倍增维护 $f_{i,j,0/1}$ 表示第 $i$ 个格子走 $2^j$ 代价最右 / 次右能到哪。

代码

const int N = 2e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int l[N], r[N];
	struct jmp {
		int to, id;
	};
	struct node {
		jmp mx1, mx2;
		void upd(jmp a) {
			if (a.to > mx1.to) mx2 = mx1, mx1 = a; 
			else if (a.id != mx1.id && a.to > mx2.to) mx2 = a;
		}
	} a[N];
	int f[N][20][2];
	int main () {
		n = Read(), m = Read();
		for (int i = 1; i <= m; i++) {
			l[i] = Read(), r[i] = Read();
			a[l[i]].upd((jmp){r[i], i});
		}
		for (int i = 1; i <= n; i++) {
			a[i].upd(a[i-1].mx1);
			a[i].upd(a[i-1].mx2);
			f[i][0][0] = a[i].mx1.to;
			f[i][0][1] = a[i].mx2.to;
		}
		for (int j = 1; j <= 17; j++) {
			for (int i = 1; i <= n; i++) {
				int t = a[f[i][j-1][1]].mx1.id==a[i].mx1.id;
				f[i][j][0] = f[f[i][j-1][0]][j-1][0];
				f[i][j][1] = f[f[i][j-1][1]][j-1][t];
			}
		}
		for (int q = Read(); q--;) {
			int id = Read(), s = Read(), t = Read();
			int ans = 0;
			if (t < l[id]) id = 0;
			if (s < l[id]) {
				for (int i = 17; i >= 0; i--) 
					if (f[s][i][0] < l[id]) ans += (1 << i), s = f[s][i][0];
				ans++, s = f[s][0][0];
			}
			if (s >= t) {
				printf("%d\n", ans);
				continue;
			}
			for (int i = 17; i >= 0; i--) 
				if (f[s][i][a[s].mx1.id==id] < t) ans += (1 << i), s = f[s][i][a[s].mx1.id==id];
			ans++, s = f[s][0][a[s].mx1.id==id];
			if (s < t) puts("-1");
			else printf("%d\n", ans);
		}
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}