[JOI 2022 Final] 鐵路旅行 2 (Railway Trip 2)

題目#

IOI 鐵路公司在一條鐵軌上運營線路。鐵軌為一條直線，該鐵軌上有 $N$ 個車站，編號為 $1 \sim N$。車站 $i$ 與車站 $i + 1$ 之間由一條鐵軌直接連接。

IOI 鐵路公司正在運營 $M$ 條線路，編號為 $1 \sim M$。線路 $j$ 的起點為 $A_j$，終點為 $B_j$，列車在每一站均會停靠，即如果 $A_j <B_j$，一列 $j$ 號線的列車會按順序在車站 $A_j, A_j + 1, \ldots, B_j$ 停靠。如果 $A_j> B_j$，一列 $j$ 號線的列車會按順序在車站 $A_j, A_j - 1, \ldots, B_j$ 停靠。

JOI 君是一個旅行者。他有 $Q$ 個旅行計劃。在第 $k$ 個旅行計劃中他計劃從車站 $S_k$ 通過乘坐列車前往車站 $T_k$。

然而，JOI 君因長途跋涉而疲憊不堪。他希望他乘坐的列車均有空座以便休息。因此 JOI 君決定，只有當某條線路的起點站是第 $K$ 個或更早的車站時，他才會在該站乘坐該條線路的列車。換句話說，對於線路 $j$，如果 $A_j <B_j$，那麼他只會在車站 $A_j, A_j + 1, \ldots, \min { A_j + K - 1, B_j - 1}$ 乘上線路 $j$ 的列車。如果 $A_j > B_j$，那麼他只會在車站 $A_j, A_j - 1, \ldots, \max { A_j - K + 1, B_j + 1 }$ 乘上線路 $j$ 的列車。

在這些條件下，JOI 君希望儘量減少乘坐火車的次數。

給出 IOI 鐵路公司的線路信息和 JOI 君的計劃，寫一個程序計算對於 JOI 君的每一個計劃，他所需的最小乘車次數。

對於 $100 %$ 的數據，$2 \le N \le {10}^5$，$1 \le K \le N - 1$，$1 \le M \le 2 \times {10}^5$，$1 \le Q \le 5 \times {10}^4$，$1 \le A_j, B_j, S_k, T_k \le N$，$A_j \ne B_j$，$S_k \ne T_k$，$(A_j, B_j) \ne (A_k, B_k)$（$j \ne k$），$(S_k, T_k) \ne (S_l, T_l)$（$k \ne l$）。

題解#

~~為了學習算法寫的這道題，抄的題解~~

暴力做法#

從起點開始深搜，複雜度爆炸

優化一點#

設f[i][j]表示從i點走j次路線所能到達的最遠的地方 (pair，左右端點)

預處理出所有的f[i][j]，枚舉f[i][j - 1]中的所有點 k，看f[k][1]能到達的左右最大值

複雜度 $O (n^2m)$，會炸

再優化一點#

看到這種走走停停的題，考慮能不能倍增

設f[i][j]表示i點走 $2^j$ 次路線所能到達的最遠的地方 (pair，左右端點)

考慮轉移，枚舉f[i][j - 1]的每個位置k，找到f[k][j - 1]能到達的左右最大值

顯然不能暴力枚舉找最大值，可以對於每一個2^j代表的j建立一個 st 表，（因為沒有修改），然後可以做了

結果查詢怎麼辦呢

很像 lca，枚舉f[起點][w]，w從大到小枚舉，如果到得了終點，那麼 w 繼續減，直到到不了為止。最後如果結束的點沒法到終點，輸出 - 1，否則 res+1 即可

鍋#

st 表寫炸了。。。。

代碼#

#include<bits/stdc++.h> 
#define PII pair<int, int>
#define l first
#define r second
using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
PII up_route[M], down_route[M];
int upcnt, downcnt;
int fl[N][20], fr[N][20];
int n, m, k;

int qwq[M], hh = 1, tt = 0;

bool cmp(PII A, PII B)
{
	return A.second > B.second;
}
const int LOG = 20;
struct ST
{
	int st[N][LOG];

	void init(int k,int lorr)
	{
		if(lorr == 0)
		{
			memset(st, 0x3f, sizeof st);
		}
		for(int i = 1;i <= n;i++)
			st[i][0] = ((!lorr) ? (fl[i][k]) : (fr[i][k]));
	}
	void prepare(int lorr)
	{
		for(int j = 1;j < LOG;j++)
		{
			for(int i = 1;i + (1 << j) - 1 <= n;i++)
			{
				st[i][j] = ((!lorr) ? min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]) : max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]));
			}
		}
	}

	int query(int l, int r, int lorr)
	{
		int lllooojjj = log2(r - l + 1);
		return ((!lorr) ? min(st[l][lllooojjj], st[r - (1 << lllooojjj) + 1][lllooojjj]) : max(st[l][lllooojjj], st[r - (1 << lllooojjj) + 1][lllooojjj]));
	}
}s[20][2];//0代表fl，1代表fr 

int ask(int b, int t)
{
	int res = 0;
	int l = b, r = b;
	for(int k = 19;k >= 0;k--)
	{
		int L = s[k][0].query(l, r, 0);
		int R = s[k][1].query(l, r, 1);
		if(L <= t && t <= R) continue;
//		cout << k << " " << L  << " " << R << endl;
		res += (1 << k);
		l = L, r = R;
	}

	int L = s[0][0].query(l, r, 0);
	int R = s[0][1].query(l, r, 1);
	if(L <= t && t <= R) return res + 1;
	return -1;
}


int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> k;

	cin >> m;
	int u, v;
	for(int i = 1;i <= m;i++)
	{
		cin >> u >> v;
		if(u < v)
		{
			up_route[++upcnt] = make_pair(u, v);
		}
		else
		{
			down_route[++downcnt] = make_pair(v, u);
		}
	}
	if(upcnt >= 1)
	sort(up_route + 1, up_route + upcnt + 1);
	if(downcnt >= 1)
	sort(down_route + 1, down_route + downcnt + 1, cmp);

	for(int i = 1;i <= n;i++)
		fl[i][0] = fr[i][0] = i;
	if(upcnt >= 1)
	for(int i = 1, j = 1;i <= n;i++)
	{
		while(j <= upcnt && up_route[j].l <= i)
		{
			while(hh <= tt && up_route[j].r >= up_route[qwq[tt]].r)
			{
				tt --;
			}
	
			qwq[++tt] = j;
			j++;
		}

		while(hh <= tt && up_route[qwq[hh]].l + k - 1 < i/*!!!*/)
		{
			hh++;
		} 
		if(hh > tt) continue;/*!!!*/
		fr[i][0] = max(fr[i][0], up_route[qwq[hh]].r);
	}
	memset(qwq, 0, sizeof qwq); 
	hh = 1, tt = 0;
	if(downcnt >= 1)
	for(int i = n, j = 1;i >= 1;i--)
	{
		while(j <= downcnt && down_route[j].r >= i)
		{
			while(hh <= tt && down_route[j].l <= down_route[qwq[tt]].l)
			{
				tt --;
			}
	
			qwq[++tt] = j;
			j++;
		}

		while(hh <= tt && down_route[qwq[hh]].r - k + 1 > i/*!!!*/)
		{
			hh++;
		}

		if(hh > tt) continue;/*!!!*/
		fl[i][0] = min(fl[i][0], down_route[qwq[hh]].l);
	}

	s[0][0].init(0, 0);
	s[0][0].prepare(0);
	s[0][1].init(0, 1);
	s[0][1].prepare(1);

	for(int k = 1;k < 20;k++)
	{
		for(int i = 1;i <= n;i++)
		{
			fl[i][k] = s[k - 1][0].query(fl[i][k - 1], fr[i][k - 1], 0);
			fr[i][k] = s[k - 1][1].query(fl[i][k - 1], fr[i][k - 1], 1);
		}
		s[k][0].init(k, 0);
		s[k][0].prepare(0);
		s[k][1].init(k, 1);
		s[k][1].prepare(1);
	}
	int Q;
	cin >> Q;
	int s, t;
	while(Q -- )
	{
		cin >> s >> t;
		cout << ask(s, t) << "\n";
	}

	return 0;
}