题目#

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表写炸了。。。。

代码#

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

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

15
bool cmp(PII A, PII B)
16
{
17
  return A.second > B.second;
18
}
19
const int LOG = 20;
20
struct ST
21
{
22
  int st[N][LOG];
23

24
  void init(int k,int lorr)
25
  {
26
    if(lorr == 0)
27
    {
28
      memset(st, 0x3f, sizeof st);
29
    }
30
    for(int i = 1;i <= n;i++)
31
      st[i][0] = ((!lorr) ? (fl[i][k]) : (fr[i][k]));
32
  }
33
  void prepare(int lorr)
34
  {
35
    for(int j = 1;j < LOG;j++)
36
    {
37
      for(int i = 1;i + (1 << j) - 1 <= n;i++)
38
      {
39
        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]));
40
      }
41
    }
42
  }
43

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

51
int ask(int b, int t)
52
{
53
  int res = 0;
54
  int l = b, r = b;
55
  for(int k = 19;k >= 0;k--)
56
  {
57
    int L = s[k][0].query(l, r, 0);
58
    int R = s[k][1].query(l, r, 1);
59
    if(L <= t && t <= R) continue;
60
//    cout << k << " " << L  << " " << R << endl;
61
    res += (1 << k);
62
    l = L, r = R;
63
  }
64

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

71

72
int main()
73
{
74
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
75

76
  cin >> n >> k;
77

78
  cin >> m;
79
  int u, v;
80
  for(int i = 1;i <= m;i++)
81
  {
82
    cin >> u >> v;
83
    if(u < v)
84
    {
85
      up_route[++upcnt] = make_pair(u, v);
86
    }
87
    else
88
    {
89
      down_route[++downcnt] = make_pair(v, u);
90
    }
91
  }
92
  if(upcnt >= 1)
93
  sort(up_route + 1, up_route + upcnt + 1);
94
  if(downcnt >= 1)
95
  sort(down_route + 1, down_route + downcnt + 1, cmp);
96

97
  for(int i = 1;i <= n;i++)
98
    fl[i][0] = fr[i][0] = i;
99
  if(upcnt >= 1)
100
  for(int i = 1, j = 1;i <= n;i++)
101
  {
102
    while(j <= upcnt && up_route[j].l <= i)
103
    {
104
      while(hh <= tt && up_route[j].r >= up_route[qwq[tt]].r)
105
      {
106
        tt --;
107
      }
108

109
      qwq[++tt] = j;
110
      j++;
111
    }
112

113
    while(hh <= tt && up_route[qwq[hh]].l + k - 1 < i/*!!!*/)
114
    {
115
      hh++;
116
    }
117
    if(hh > tt) continue;/*!!!*/
118
    fr[i][0] = max(fr[i][0], up_route[qwq[hh]].r);
119
  }
120
  memset(qwq, 0, sizeof qwq);
121
  hh = 1, tt = 0;
122
  if(downcnt >= 1)
123
  for(int i = n, j = 1;i >= 1;i--)
124
  {
125
    while(j <= downcnt && down_route[j].r >= i)
126
    {
127
      while(hh <= tt && down_route[j].l <= down_route[qwq[tt]].l)
128
      {
129
        tt --;
130
      }
131

132
      qwq[++tt] = j;
133
      j++;
134
    }
135

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

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

145
  s[0][0].init(0, 0);
146
  s[0][0].prepare(0);
147
  s[0][1].init(0, 1);
148
  s[0][1].prepare(1);
149

150
  for(int k = 1;k < 20;k++)
151
  {
152
    for(int i = 1;i <= n;i++)
153
    {
154
      fl[i][k] = s[k - 1][0].query(fl[i][k - 1], fr[i][k - 1], 0);
155
      fr[i][k] = s[k - 1][1].query(fl[i][k - 1], fr[i][k - 1], 1);
156
    }
157
    s[k][0].init(k, 0);
158
    s[k][0].prepare(0);
159
    s[k][1].init(k, 1);
160
    s[k][1].prepare(1);
161
  }
162
  int Q;
163
  cin >> Q;
164
  int s, t;
165
  while(Q -- )
166
  {
167
    cin >> s >> t;
168
    cout << ask(s, t) << "\n";
169
  }
170

171
  return 0;
172
}