問題#
IOI 鉄道会社は、1 本の鉄道で路線を運営しています。鉄道は直線で、$N$ の駅があり、番号は $1 \sim N$ です。駅 $i$ と駅 $i + 1$ の間は、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 君の計画を与えられたとき、彼の各計画に対して必要な最小乗車回数を計算するプログラムを書いてください。
$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 回の路線を走ることで到達できる最遠の場所（ペア、左右端点）を表します。
すべての f[i][j] を前処理し、f[i][j - 1] のすべての点 k を列挙し、f[k][1] で到達できる左右の最大値を確認します。
複雑度は $O (n^2m)$ で、爆発します。
さらに最適化#
このような行ったり止まったりの問題を見たら、倍増できないか考えます。
f[i][j] を定義し、i 点から $2^j$ 回の路線を走ることで到達できる最遠の場所（ペア、左右端点）を表します。
遷移を考え、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;
}