Codeforces 793 F Julia the snail
Description
有 $M$ 個傳送器，第 $i$ 個可以把你從 $l_i$ 傳送到 $r_i$，其中 $l_i, r_i$ 介在 $1, N$ 之間。
你除了傳送以外的移動方式只有向數線的左邊走（把 $x$ 變小）
接著有 $Q$ 筆詢問問，每筆詢問給 $x, y$，
問你從 $x$ 開始走，在不超出 $[x, y]$ 這個區間的前提下可以走最右邊是多右邊。
$r_i$ 全部相異（雖然我感覺好像沒用）
Solution
想了很久之後看官解發現是 $\mathcal{O}(\sqrt{n})$ 氣死
留言說有一個 log 的解但他不願透露
網路上查到很多類似吉如一線段樹的解但我覺得他們都沒什麼說服力
先從 naive 的想法開始說明。
這邊的說明都是用左閉右閉的。
如果把所有被 $[x, y]$ 包含的 $[l_i, r_i]$ 拿出來，那他們會把整個區間分成一些連通塊的感覺。
具體來說，會有一些分界線 $z$，
使得我們可以把 $[l_i, r_i]$ 分成兩部分，一部分完全落在 $[x, z]$ 而另一部分完全落在 $[z+1, y]$。
注意到 $z = y$ 一定是一個合法的分界線（？）
可以知道從 $x$ 開始走最遠可以走到的境界一定就是最左邊的分界線（一定不可能走超過最左的分界線，而如果把被完全包含的 $[l_i, r_i]$ 拿掉就會剩下 $l_i, r_i$ 一起遞增的一堆區間，並且每個 $l_i$ 都落在前一個區間裡面）
令人驚訝的是，我們可以直接用線段樹維護區間的最左邊的分界線。
我們首先離線回答問題，掃描線依序從左界大到小把 $[l_i, r_i]$ 加進資料結構並順便回答詢問，
每個 $[l_i, r_i]$ 放進去的時候按照右界排序。
這樣對於一個詢問來說我們就可以詢問資結裡面的一個前綴得到所有完全包含在 $[x, y]$ 裡面的所有 $[l_i, r_i]$。
對於一堆右界介在 $[L, R]$ 的區間 $[l_i, r_i]$，我們想知道他們造成的最左分界線是哪裡。
現在我們已經知道右界介在 $[L, M]$ 的一堆區間他們造成的最左分界線 $z_L$，以及右界介在 $[M+1, R]$ 的一堆區間他們造成的最左分界線 $z_R$。另外我們還知道他們各自都還有往左延伸一段到多遠（分別是對應的區間集合中的左界最小值）。
如果 $z_L$ 有被右界介在 $[M+1, R]$ 的區間的左界蓋到，那表示右界介在 $[L, M]$ 的區間造成的所有分界線都會被這個左界蓋到，也就是說右界介在 $[L, R]$ 的區間構成的最左分界線就是 $z_R$。否則 $z_L$ 沒有被蓋到，他仍然是一個分界線，而且他也一定是最左的分界線。
感覺畫圖更能理解但我懶得作圖了。
AC code
code 感覺是 0-base 左閉右開但隨便（
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
| // An AC a day keeps the doctor away.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(args...) qqbx(#args, args)
#define orange(args...) danb(#args, args)
using std::cerr;
template <typename ...T> void qqbx(const char *s, T ...args) {
int cnt = sizeof...(T);
((cerr << "\e[1;32m(" << s << ") = ("), ..., (cerr << args << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I> void danb(const char *s, I L, I R) {
cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L) cerr << (f++ ? ", " : "") << *L;
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
using namespace std;
const int inf = 1e9;
struct Node {
int best_i;
int mn;
Node() : best_i(inf), mn(inf) {}
};
Node operator+(const Node &lhs, const Node &rhs) {
Node res;
res.mn = min(lhs.mn, rhs.mn);
if (lhs.best_i < rhs.mn) {
res.best_i = lhs.best_i;
} else {
res.best_i = rhs.best_i;
}
return res;
}
struct Segtree {
int n;
vector<Node> st;
Segtree(int t_n) : n(t_n), st(t_n * 2) {
for (int i = 0; i < n; i++) {
st[i + n].mn = i;
st[i + n].best_i = i;
}
for (int i = n - 1; i > 0; i--) {
st[i] = st[i << 1] + st[i << 1 | 1];
}
}
void modify(int p, Node nd) {
p += n;
st[p] = nd;
while (p >>= 1) {
st[p] = st[p << 1] + st[p << 1 | 1];
}
}
Node query(int l, int r) {
Node resl, resr;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) resl = resl + st[l++];
if (r & 1) resr = st[--r] + resr;
}
return resl + resr;
}
void dump() {
vector<int> s;
for (int i = 0; i < n; i++) {
s.push_back(st[i + n].mn + 1);
}
orange(all(s));
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> seg(n);
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
--l, --r;
seg[l].emplace_back(r);
}
int q;
cin >> q;
vector<int> ans(q);
vector<vector<pair<int,int>>> qs(n);
for (int i = 0; i < q; i++) {
int x, y;
cin >> x >> y;
--x, --y;
qs[x].emplace_back(y, i);
}
Segtree sgt(n); // iota
for (int i = n - 1; i >= 0; i--) {
for (int r: seg[i]) {
Node nd;
nd.mn = i;
nd.best_i = r;
sgt.modify(r, nd);
}
for (auto [r, qid]: qs[i]) {
auto ret = sgt.query(i, r + 1);
ans[qid] = ret.best_i;
}
}
for (int i = 0; i < q; i++)
cout << ans[i] + 1 << '\n';
return 0;
}
|
美如畫。
暑假太閒太 nerd 跑來更新部落格，最近不知道該怎麼辦才好。
另外常常感覺自己分享了一些知識之後就不能出題目好麻煩（從來學不會出題目）