注：以下的有些解法不一定是标解，甚至可能麻烦了好几倍。
LOJ3271. 「JOISC 2020 Day1」建筑装饰 4
题意
给定长度为 $2n$ 的序列 $A_{1..2n}$ 和 $B_{1..2n}$。对于每个 $iin[1,2n]$，从 $A_i,B_i$ 中选出一个数作为 $C_i$。要求 $C_i$ 不下降，且选 $A$ 和选 $B$ 的位置各有 $n$ 个。输出任意一种方案。
$1leq nleq 5 imes 10^5$
题解
设 $dp(i, 0 / 1, j)$ 表示前 $i$ 个数字，当前选了 $A / B$，总共有 $j$ 个选了 $A$，是否可能。可以发现对于同一个 $i$，合法的 $j$ 是一段区间，所以 dp 时只需要记录这个区间即可。时间复杂度 $O(n)$。
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1000005; 4 struct Intv { 5 int l, r; 6 inline Intv() { l = r = -1; } 7 inline Intv(int fuckl, int fuckr) { l = fuckl; r = fuckr; } 8 inline Intv operator + (const Intv &oth) const { 9 if (l == -1) return oth; 10 if (oth.l == -1) return *this; 11 return Intv(min(l, oth.l), max(r, oth.r)); 12 } 13 inline bool Inside(int x) const { 14 return l <= x && x <= r; 15 } 16 } f[N][2]; 17 int n, A[N], B[N]; 18 char S[N]; 19 inline void fucker(int i, int j) { 20 S[2 * n + 1] = 0; 21 int cc = n; 22 while (i > 1) { 23 if (j == 0) { 24 S[i] = 'A'; 25 cc--; 26 if (A[i - 1] <= A[i] && f[i - 1][0].Inside(cc)) { 27 j = 0; 28 } else { 29 j = 1; 30 } 31 } else { 32 S[i] = 'B'; 33 if (A[i - 1] <= B[i] && f[i - 1][0].Inside(cc)) { 34 j = 0; 35 } else { 36 j = 1; 37 } 38 } 39 i--; 40 } 41 S[1] = j + 'A'; 42 puts(S + 1); 43 } 44 int main() { 45 scanf("%d", &n); 46 for (int i = 1; i <= n * 2; i++) scanf("%d", &A[i]); 47 for (int i = 1; i <= n * 2; i++) scanf("%d", &B[i]); 48 f[1][0] = Intv(1, 1); 49 f[1][1] = Intv(0, 0); 50 for (int i = 2; i <= n * 2; i++) { 51 if (A[i - 1] <= A[i]) f[i][0] = f[i][0] + f[i - 1][0]; 52 if (B[i - 1] <= A[i]) f[i][0] = f[i][0] + f[i - 1][1]; 53 if (f[i][0].l != -1) f[i][0].l++, f[i][0].r++; 54 if (A[i - 1] <= B[i]) f[i][1] = f[i][1] + f[i - 1][0]; 55 if (B[i - 1] <= B[i]) f[i][1] = f[i][1] + f[i - 1][1]; 56 } 57 if (f[n * 2][0].Inside(n)) { 58 fucker(n * 2, 0); 59 } else if (f[n * 2][1].Inside(n)) { 60 fucker(n * 2, 1); 61 } else puts("-1"); 62 return 0; 63 }
LOJ3272. 「JOISC 2020 Day1」汉堡肉
题意
在一个 $10^9 imes 10^9$ 的平面上有 $n$ 个矩形，坐标都已经给定。给定一个整数 $K$，你要在平面上选 $K$ 个点（可以重复），使得每个矩形都至少与一个选的点有交。输出任意一种方案。数据保证有解。
$1leq nleq 2 imes 10^5, 1leq Kleq 4$
题解
设所有长方形的右边界最小值为 $min_{xr}$，左边界最大值为 $max_{xl}$，同理定义 $min_{yr}, max_{yl}$。
可以证明如果有解那么一定可以使得：存在一个点的横坐标为 $min_{xr}$，证明可以考虑调整法。
同理证明另外三个值。
上面的结论告诉我们：一定存在解，使得这四个值都存在于解的某个点中。
那么当 $Kleq 3$ 时，根据抽屉原理，一定有一个点同时占领了这四个值中的两个，直接暴力枚举四种情况，递归进行搜索即可。这一部分时间复杂度 $O(n imes 4^K)$。
（注：当 $max_{xl}leq min_{xr}$ 或 $max_{yl}leq min_{yr}$ 时，会简化为一维的情况。此时并不一定这四个值都出现，但这个搜索依然可以得到解。）
当 $K=4$ 时，除了上面的这个搜索，还有一种情况。就是四个点分别在这四个值框出的矩形的四条边上。
如果一个矩形与这四条边中的至少三条有公共点，那么可以忽略这个矩形——因为它一定完整包含了一条边。
剩下的矩形最多只会与两条边有公共点，考虑 2SAT 建图。对于两个矩形，如果它们在同一条边上所需的区间没有交点，那么它们一定不能同时选择这条边，这就是限制条件。
可以排序后加入前缀 / 后缀辅助点优化 2SAT 建图。由于题目保证有解，所以这个 2SAT 也肯定有解。得到 2SAT 的解后把每条边的区间求个交就是最终的答案了。
这一部分的时间复杂度瓶颈在于排序，为 $O(nlog n)$。总的时间复杂度为 $O(n(4^K+log n))$。
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 //Fast IO start 4 namespace io { 5 const int BUFSIZE = 1 << 20; 6 char ibuf[BUFSIZE], *is = ibuf, *it = ibuf; 7 char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE - 1; 8 inline void read_char(char &c) { 9 if (is == it) { 10 it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); 11 if (is == it) *it++ = EOF; 12 } 13 c = *is++; 14 } 15 template <class T> 16 inline void read_int(T &x) { 17 T f = 1; 18 char c; 19 read_char(c); 20 while (!isdigit(c)) { 21 if (c == '-') { 22 f = -1; 23 } 24 read_char(c); 25 } 26 x = 0; 27 while (isdigit(c)) { 28 x = x * 10 + c - '0'; 29 read_char(c); 30 } 31 x *= f; 32 } 33 inline void flush() { 34 fwrite(obuf, 1, os - obuf, stdout); 35 os = obuf; 36 } 37 inline void print_char(char c) { 38 *os++ = c; 39 if (os == ot) { 40 flush(); 41 } 42 } 43 template <class T> 44 inline void print_int(T x) { 45 static char q[40]; 46 if (!x) { 47 print_char('0'); 48 } else { 49 if (x < 0) { 50 print_char('-'); 51 x = -x; 52 } 53 int top = 0; 54 while (x) { 55 q[top++] = x % 10 + '0'; 56 x /= 10; 57 } 58 while (top--) { 59 print_char(q[top]); 60 } 61 } 62 } 63 struct flusher_t { 64 inline ~flusher_t() { 65 flush(); 66 } 67 } flusher; 68 } 69 using io::read_char; 70 using io::read_int; 71 using io::print_char; 72 using io::print_int; 73 //Fast IO end 74 const int N = 200005; 75 struct Node { 76 int xl, yl, xr, yr; 77 }; 78 int n, K, vis[N]; 79 Node a[N]; 80 pair<int, int> ans[5]; 81 void go(int dep) { 82 int mn_xr = 1e9, mx_xl = 1, mn_yr = 1e9, mx_yl = 1; 83 for (int i = 1; i <= n; i++) if (!vis[i]) { 84 mx_xl = max(mx_xl, a[i].xl); 85 mn_xr = min(mn_xr, a[i].xr); 86 mx_yl = max(mx_yl, a[i].yl); 87 mn_yr = min(mn_yr, a[i].yr); 88 } 89 if (dep == 1) { 90 if (mx_xl <= mn_xr && mx_yl <= mn_yr) { 91 ans[1] = make_pair(mx_xl, mx_yl); 92 for (int i = 1; i <= K; i++) printf("%d %d ", ans[i].first, ans[i].second); 93 exit(0); 94 } 95 return; 96 } 97 for (int tx = 0; tx < 2; tx++) { 98 int x = (tx ? mx_xl : mn_xr); 99 for (int ty = 0; ty < 2; ty++) { 100 int y = (ty ? mx_yl : mn_yr); 101 ans[dep] = make_pair(x, y); 102 for (int i = 1; i <= n; i++) if (a[i].xl <= x && x <= a[i].xr && a[i].yl <= y && y <= a[i].yr) 103 vis[i]++; 104 go(dep - 1); 105 for (int i = 1; i <= n; i++) if (a[i].xl <= x && x <= a[i].xr && a[i].yl <= y && y <= a[i].yr) 106 vis[i]--; 107 } 108 } 109 } 110 const int V = N * 6; 111 vector<int> G[V], h[N]; 112 inline void add_edge(int u, int v) { G[u].push_back(v); } 113 int tot, id[N][2], pre[4][N], suf[4][N], dfn[V], low[V], dfc, stk[V], tp, instk[V], bel[V], scc; 114 vector<tuple<int, int, int> > sl[4], sr[4]; 115 void Tarjan(int u) { 116 dfn[u] = low[u] = ++dfc; 117 stk[++tp] = u; 118 instk[u] = 1; 119 for (int v : G[u]) { 120 if (!dfn[v]) { 121 Tarjan(v); 122 low[u] = min(low[u], low[v]); 123 } else if (instk[v]) { 124 low[u] = min(low[u], dfn[v]); 125 } 126 } 127 if (dfn[u] == low[u]) { 128 ++scc; 129 int w; 130 do { 131 w = stk[tp--]; 132 instk[w] = 0; 133 bel[w] = scc; 134 } while (w != u); 135 } 136 } 137 void solve4() { 138 int mn_xr = 1e9, mx_xl = 1, mn_yr = 1e9, mx_yl = 1; 139 for (int i = 1; i <= n; i++) { 140 mx_xl = max(mx_xl, a[i].xl); 141 mn_xr = min(mn_xr, a[i].xr); 142 mx_yl = max(mx_yl, a[i].yl); 143 mn_yr = min(mn_yr, a[i].yr); 144 } 145 assert(mn_xr <= mx_xl && mn_yr <= mx_yl); 146 tot = 0; 147 for (int i = 1; i <= n; i++) { 148 vector<int> vs; 149 if (a[i].xl <= mn_xr && mn_xr <= a[i].xr) vs.push_back(0); 150 if (a[i].xl <= mx_xl && mx_xl <= a[i].xr) vs.push_back(1); 151 if (a[i].yl <= mn_yr && mn_yr <= a[i].yr) vs.push_back(2); 152 if (a[i].yl <= mx_yl && mx_yl <= a[i].yr) vs.push_back(3); 153 assert(vs.size()); 154 if ((int)vs.size() >= 3) continue; 155 id[i][0] = ++tot; 156 id[i][1] = ++tot; 157 if ((int)vs.size() == 1) { 158 add_edge(id[i][1], id[i][0]); 159 } 160 for (int j = 0; j < (int)vs.size(); j++) { 161 sl[vs[j]].emplace_back(vs[j] < 2 ? max(mn_yr, a[i].yl) : max(mn_xr, a[i].xl), id[i][j], id[i][j ^ 1]); 162 sr[vs[j]].emplace_back(vs[j] < 2 ? min(mx_yl, a[i].yr) : min(mx_xl, a[i].xr), id[i][j], id[i][j ^ 1]); 163 } 164 h[i] = vs; 165 } 166 for (int v = 0; v < 4; v++) { 167 sort(sl[v].begin(), sl[v].end()); 168 sort(sr[v].begin(), sr[v].end()); 169 for (int i = 0; i < (int)sr[v].size(); i++) { 170 pre[v][i + 1] = ++tot; 171 if (i) add_edge(pre[v][i + 1], pre[v][i]); 172 add_edge(pre[v][i + 1], get<2>(sr[v][i])); 173 } 174 for (int i = 0, j = 0; i < (int)sl[v].size(); i++) { 175 while (j < (int)sr[v].size() && get<0>(sr[v][j]) < get<0>(sl[v][i])) j++; 176 if (j) add_edge(get<1>(sl[v][i]), pre[v][j]); 177 } 178 for (int i = (int)sl[v].size() - 1; ~i; i--) { 179 suf[v][i] = ++tot; 180 if (i < (int)sl[v].size() - 1) add_edge(suf[v][i], suf[v][i + 1]); 181 add_edge(suf[v][i], get<2>(sl[v][i])); 182 } 183 for (int i = (int)sr[v].size() - 1, j = (int)sl[v].size(); ~i; i--) { 184 while (j && get<0>(sl[v][j - 1]) > get<0>(sr[v][i])) j--; 185 if (j < (int)sl[v].size()) add_edge(get<1>(sr[v][i]), suf[v][j]); 186 } 187 } 188 dfc = tp = 0; 189 for (int i = 1; i <= tot; i++) { 190 if (!dfn[i]) Tarjan(i); 191 } 192 int L[5], R[5]; 193 L[0] = L[1] = mn_yr; 194 R[0] = R[1] = mx_yl; 195 L[2] = L[3] = mn_xr; 196 R[2] = R[3] = mx_xl; 197 for (int i = 1; i <= n; i++) { 198 if (!id[i][0]) continue; 199 assert(bel[id[i][0]] != bel[id[i][1]]); 200 int j = h[i][(bel[id[i][0]] < bel[id[i][1]]) ? 0 : 1]; 201 L[j] = max(L[j], j < 2 ? a[i].yl : a[i].xl); 202 R[j] = min(R[j], j < 2 ? a[i].yr : a[i].xr); 203 } 204 assert(L[0] <= R[0] && L[1] <= R[1] && L[2] <= R[2] && L[3] <= R[3]); 205 printf("%d %d ", mn_xr, L[0]); 206 printf("%d %d ", mx_xl, L[1]); 207 printf("%d %d ", L[2], mn_yr); 208 printf("%d %d ", L[3], mx_yl); 209 exit(0); 210 } 211 int main() { 212 read_int(n); 213 read_int(K); 214 for (int i = 1; i <= n; i++) { 215 read_int(a[i].xl); 216 read_int(a[i].yl); 217 read_int(a[i].xr); 218 read_int(a[i].yr); 219 } 220 go(K); 221 if (K == 4) { 222 solve4(); 223 } 224 assert(false); 225 return 0; 226 }
LOJ3273. 「JOISC 2020 Day1」扫除
题意
有一个边长为 $n$ 的等腰直角三角形房间，顶点为 $(0,0), (0,n), (n,0)$。初始时，房间内有 $m$ 堆灰尘，坐标都已经给定，同一点处可能有多堆灰尘。我们可以用扫帚进行清扫，扫帚可以看作是一条线段。我们只能用如下方式使用扫帚：
- 把扫帚放在房间内，使得扫帚的一个端点为原点，并且扫帚平行于 $y$ 轴。然后，沿着 $x$ 轴正方向水平移动扫帚，直到不能移动为止（即顶到房间的边了）。在移动过程中，保持扫帚与 $y$ 轴平行，并且一个端点始终在 $x$ 轴上。如果扫帚长度为 $l$，则在 $(x,y)$ 的灰尘（$x<n-l, yleq l$）将会移动到 $(n-l, y)$。这个过程称为过程 H。
- 把扫帚放在房间内，使得扫帚的一个端点为原点，并且扫帚平行于 $x$ 轴。然后，沿着 $y$ 轴正方向水平移动扫帚，直到不能移动为止（即顶到房间的边了）。在移动过程中，保持扫帚与 $x$ 轴平行，并且一个端点始终在 $y$ 轴上。如果扫帚长度为 $l$，则在 $(x,y)$ 的灰尘（$xleq l, y<n-l$）将会移动到 $(x, n-l)$。这个过程称为过程 V。
房间内将会发生 $q$ 次事件，每次事件 $j$ 都是以下四种中的一个：
- 询问第 $P_j$ 堆灰尘的坐标
- 使用长度为 $L_j$ 的扫帚，进行了过程 H
- 使用长度为 $L_j$ 的扫帚，进行了过程 V
- 一堆新的灰尘出现在了 $(x_j, y_j)$ 位置。编号就是下一个没用过的数。
对于每次询问操作，正确求出灰尘的坐标。
$1leq nleq 10^9, 1leq mleq 5 imes 10^5, 1leq qleq 10^6$
题解
把初始的那 $m$ 堆灰尘看作插入操作，与之后的 $q$ 次事件放在一起处理。
我们考虑对操作序列分治。假设现在在处理操作区间 $[l,r]$，中间点为 $mid$。那么我们考虑在这一层处理在 $[l,mid]$ 内插入的点在 $[mid+1,r]$ 内的询问。在 $[l,r]$ 处理结束时，要保证 $[l,r]$ 内插入的点都处在 $r$ 事件结束时的位置。显然，我们要先递归进入下一层，再处理本层的那些询问。因为这样，在处理本层询问的时候，$[l,mid]$ 内插入的点已经处于 $mid$ 结束时的位置了，可以一起往后执行 $[mid+1,r]$ 的事件。
因为我们分治了，所以处理事件时，点集是固定的，不会插入点了。我们考虑把等腰直角三角形内，灰尘的边界和内部分开来维护，因为一旦点从内部变成了边界，那么就一直是边界了。下面是一张便于理解的图：
其中红色的就是边界，绿色的是扫帚。可以发现，边界上的 $x,y$ 值都是单调的。在使用扫帚时，我们会把边界上的一个区间的点的 $x$ 值或 $y$ 值与 $n-l$ 取 $max$，也会把一个矩形内的点全部移到边界上。
那么边界上的点，由于要插入，所以用平衡树（例如非旋转 Treap）来维护。
而内部的点，如果没变成边界，位置就不会变，如果变成了边界，就会从内部删掉，并加入平衡树。所以用线段树维护即可。
显然，每次平衡树操作的复杂度都是 $O(log (m+q))$ 的。而线段树的操作要均摊分析，由于每个点在每一层最多会被删除一次，所以每个点最多会被删除 $O(log (m+q))$ 次，一次删除的复杂度是 $O(log (m+q))$。
最终分析下来，时间复杂度是 $O((m+q)log^2(m+q))$。
实现细节（如果要用非旋转 Treap 可以看一看）：由于这个边界和操作的特殊性，我们在维护平衡树时不一定要记录子树大小，记录当前点的坐标即可。以及，为了回答边界上的点的坐标的询问，我们需要记录树上每个点的父节点，在 Split 和 Merge 时要及时更新父节点。
本题另有对等腰直角三角形分治的做法，具体可以见 zyy 神仙的题解。
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 //Fast IO start 4 namespace io { 5 const int BUFSIZE = 1 << 20; 6 char ibuf[BUFSIZE], *is = ibuf, *it = ibuf; 7 char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE - 1; 8 inline void read_char(char &c) { 9 if (is == it) { 10 it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); 11 if (is == it) *it++ = EOF; 12 } 13 c = *is++; 14 } 15 template <class T> 16 inline void read_int(T &x) { 17 T f = 1; 18 char c; 19 read_char(c); 20 while (!isdigit(c)) { 21 if (c == '-') { 22 f = -1; 23 } 24 read_char(c); 25 } 26 x = 0; 27 while (isdigit(c)) { 28 x = x * 10 + c - '0'; 29 read_char(c); 30 } 31 x *= f; 32 } 33 inline void flush() { 34 fwrite(obuf, 1, os - obuf, stdout); 35 os = obuf; 36 } 37 inline void print_char(char c) { 38 *os++ = c; 39 if (os == ot) { 40 flush(); 41 } 42 } 43 template <class T> 44 inline void print_int(T x) { 45 static char q[40]; 46 if (!x) { 47 print_char('0'); 48 } else { 49 if (x < 0) { 50 print_char('-'); 51 x = -x; 52 } 53 int top = 0; 54 while (x) { 55 q[top++] = x % 10 + '0'; 56 x /= 10; 57 } 58 while (top--) { 59 print_char(q[top]); 60 } 61 } 62 } 63 struct flusher_t { 64 inline ~flusher_t() { 65 flush(); 66 } 67 } flusher; 68 } 69 using io::read_char; 70 using io::read_int; 71 using io::print_char; 72 using io::print_int; 73 //Fast IO end 74 const int N = 1500005; 75 mt19937 gen(1145141); 76 int n, m, clk; 77 pair<int, int> pts[N], ans[N]; 78 int qt[N], qc[N], tag[N], del[N]; 79 pair<pair<int, int>, int> tp[N]; 80 namespace SegTree { 81 pair<int, int> tr[N * 4]; 82 void build(int i, int l, int r) { 83 if (l == r) { 84 tr[i] = make_pair(tp[l].second, l); 85 return; 86 } 87 int mid = (l + r) >> 1; 88 build(i << 1, l, mid); 89 build(i << 1 | 1, mid + 1, r); 90 tr[i] = (pts[tr[i << 1].first].second < pts[tr[i << 1 | 1].first].second ? tr[i << 1] : tr[i << 1 | 1]); 91 } 92 pair<int, int> query(int i, int l, int r, int lf, int rg) { 93 if (lf <= l && r <= rg) return tr[i]; 94 int mid = (l + r) >> 1; 95 if (rg <= mid) return query(i << 1, l, mid, lf, rg); 96 else if (lf > mid) return query(i << 1 | 1, mid + 1, r, lf, rg); 97 pair<int, int> r1 = query(i << 1, l, mid, lf, rg), r2 = query(i << 1 | 1, mid + 1, r, lf, rg); 98 return ((pts[r1.first].second < pts[r2.first].second) ? r1 : r2); 99 } 100 void update(int i, int l, int r, int pos) { 101 if (l == r) { 102 tr[i].first = 0; 103 return; 104 } 105 int mid = (l + r) >> 1; 106 if (pos <= mid) update(i << 1, l, mid, pos); 107 else update(i << 1 | 1, mid + 1, r, pos); 108 tr[i] = (pts[tr[i << 1].first].second < pts[tr[i << 1 | 1].first].second ? tr[i << 1] : tr[i << 1 | 1]); 109 } 110 } 111 namespace Treap { 112 struct Node { 113 int lson, rson, par, rnd, x, y, tagx, tagy; 114 inline void upd(int tx, int ty) { 115 x = max(x, tx); 116 tagx = max(tagx, tx); 117 y = max(y, ty); 118 tagy = max(tagy, ty); 119 } 120 inline void pushdown(); 121 } tr[N]; 122 int tot, root; 123 inline void Init() { 124 tot = root = 0; 125 tr[0].lson = tr[0].rson = tr[0].par = tr[0].rnd = tr[0].x = tr[0].y = tr[0].tagx = tr[0].tagy = 0; 126 } 127 inline int NewNode(int x, int y) { 128 int p = ++tot; 129 tr[p].lson = tr[p].rson = tr[p].par = tr[p].tagx = tr[p].tagy = 0; 130 tr[p].rnd = gen(); 131 tr[p].x = x, tr[p].y = y; 132 return p; 133 } 134 inline void Node::pushdown() { 135 if (tagx || tagy) { 136 if (lson) tr[lson].upd(tagx, tagy); 137 if (rson) tr[rson].upd(tagx, tagy); 138 tagx = tagy = 0; 139 } 140 } 141 inline pair<int, int> Split_y(int p, int y) { 142 if (!p) return make_pair(0, 0); 143 tr[p].pushdown(); 144 if (tr[p].y <= y) { 145 pair<int, int> q = Split_y(tr[p].lson, y); 146 tr[p].lson = q.second; 147 if (tr[p].lson) tr[tr[p].lson].par = p; 148 q.second = p; 149 tr[p].par = 0; 150 return q; 151 } else { 152 pair<int, int> q = Split_y(tr[p].rson, y); 153 tr[p].rson = q.first; 154 if (tr[p].rson) tr[tr[p].rson].par = p; 155 q.first = p; 156 tr[p].par = 0; 157 return q; 158 } 159 } 160 inline pair<int, int> Split_x(int p, int x) { 161 if (!p) return make_pair(0, 0); 162 tr[p].pushdown(); 163 if (tr[p].x > x) { 164 pair<int, int> q = Split_x(tr[p].lson, x); 165 tr[p].lson = q.second; 166 if (tr[p].lson) tr[tr[p].lson].par = p; 167 q.second = p; 168 tr[p].par = 0; 169 return q; 170 } else { 171 pair<int, int> q = Split_x(tr[p].rson, x); 172 tr[p].rson = q.first; 173 if (tr[p].rson) tr[tr[p].rson].par = p; 174 q.first = p; 175 tr[p].par = 0; 176 return q; 177 } 178 } 179 int Merge(int p1, int p2) { 180 if (!p1 || !p2) return p1 | p2; 181 if (tr[p1].rnd < tr[p2].rnd) { 182 tr[p1].pushdown(); 183 tr[p1].rson = Merge(tr[p1].rson, p2); 184 if (tr[p1].rson) tr[tr[p1].rson].par = p1; 185 return p1; 186 } else { 187 tr[p2].pushdown(); 188 tr[p2].lson = Merge(p1, tr[p2].lson); 189 if (tr[p2].lson) tr[tr[p2].lson].par = p2; 190 return p2; 191 } 192 } 193 int Insert(int x, int y) { 194 int p = NewNode(x, y); 195 int a, b, c; 196 tie(b, c) = Split_x(root, x); 197 tie(a, b) = Split_y(b, y - 1); 198 root = Merge(Merge(a, p), Merge(b, c)); 199 return p; 200 } 201 inline pair<int, int> query(int p) { 202 int x = tr[p].x, y = tr[p].y; 203 while (p) { 204 x = max(x, tr[p].tagx); 205 y = max(y, tr[p].tagy); 206 p = tr[p].par; 207 } 208 return make_pair(x, y); 209 } 210 } 211 int nid[N]; 212 void solve(int l, int r) { 213 if (l == r) return; 214 int mid = (l + r) >> 1; 215 solve(l, mid); 216 solve(mid + 1, r); 217 int tot = 0; 218 clk++; 219 for (int i = l; i <= mid; i++) { 220 if (qt[i] == 4) { 221 tp[++tot] = make_pair(pts[qc[i]], qc[i]); 222 tag[qc[i]] = clk; 223 del[qc[i]] = 0; 224 } 225 } 226 if (!tot) return; 227 sort(tp + 1, tp + 1 + tot); 228 SegTree::build(1, 1, tot); 229 Treap::Init(); 230 for (int i = mid + 1; i <= r; i++) { 231 if (qt[i] == 4 || (qt[i] == 1 && tag[qc[i]] != clk)) continue; 232 if (qt[i] == 1) { 233 ans[i] = (del[qc[i]] ? Treap::query(nid[qc[i]]) : pts[qc[i]]); 234 } else if (qt[i] == 2) { 235 int p, q; 236 tie(p, q) = Treap::Split_y(Treap::root, qc[i]); 237 if (q) Treap::tr[q].upd(n - qc[i], 0); 238 Treap::root = Treap::Merge(p, q); 239 int xr = lower_bound(tp + 1, tp + 1 + tot, make_pair(make_pair(n - qc[i], n + 5), 0)) - tp - 1; 240 if (!xr) continue; 241 pair<int, int> pr; 242 while (true) { 243 pr = SegTree::query(1, 1, tot, 1, xr); 244 if (pts[pr.first].second > qc[i]) break; 245 nid[pr.first] = Treap::Insert(n - qc[i], pts[pr.first].second); 246 del[pr.first] = 1; 247 SegTree::update(1, 1, tot, pr.second); 248 } 249 } else if (qt[i] == 3) { 250 int p, q; 251 tie(p, q) = Treap::Split_x(Treap::root, qc[i]); 252 if (p) Treap::tr[p].upd(0, n - qc[i]); 253 Treap::root = Treap::Merge(p, q); 254 int xr = lower_bound(tp + 1, tp + 1 + tot, make_pair(make_pair(qc[i], n + 5), 0)) - tp - 1; 255 if (!xr) continue; 256 pair<int, int> pr; 257 while (true) { 258 pr = SegTree::query(1, 1, tot, 1, xr); 259 if (pts[pr.first].second > n - qc[i]) break; 260 nid[pr.first] = Treap::Insert(pts[pr.first].first, n - qc[i]); 261 del[pr.first] = 1; 262 SegTree::update(1, 1, tot, pr.second); 263 } 264 } 265 } 266 for (int i = l; i <= mid; i++) { 267 if (qt[i] == 4 && del[qc[i]]) { 268 pts[qc[i]] = Treap::query(nid[qc[i]]); 269 } 270 } 271 } 272 int main() { 273 int q, cnt; 274 read_int(n); 275 read_int(m); 276 read_int(q); 277 for (int i = 1; i <= m; i++) { 278 read_int(pts[i].first); 279 read_int(pts[i].second); 280 qt[i] = 4; 281 qc[i] = i; 282 } 283 cnt = m; 284 for (int i = m + 1; i <= m + q; i++) { 285 read_int(qt[i]); 286 if (qt[i] <= 3) read_int(qc[i]); 287 else { 288 qc[i] = ++cnt; 289 read_int(pts[cnt].first); 290 read_int(pts[cnt].second); 291 } 292 } 293 m += q; 294 clk = 0; 295 pts[0].second = n + 5; 296 solve(1, m); 297 for (int i = 1; i <= m; i++) { 298 if (qt[i] == 1) printf("%d %d ", ans[i].first, ans[i].second); 299 } 300 return 0; 301 }
LOJ3274. 「JOISC 2020 Day2」变色龙之恋
题意
这是一道交互题。
有 $2n$ 只变色龙，其中 $n$ 只是性别 X，另外 $n$ 只是性别 Y。
每只变色龙都有一个原色。已知所有性别 X 的变色龙的原色互不相同，且对于每只性别 X 的变色龙，都存在唯一的原色与之相同的性别为 Y 的变色龙。
春天到了，每只变色龙都爱上了一只与之性别不同且与之颜色不同的变色龙，且不存在两只变色龙爱上同一只变色龙的情况。
你可以召集一些变色龙进行会议。对于一只参加会议的变色龙 $s$，设其喜欢的变色龙为 $t$。$s$ 的肤色由以下方式决定：
如果 $t$ 参加了这场会议，那么 $s$ 的肤色为 $t$ 的原色，否则 $s$ 的肤色为 $s$ 的原色。
一只变色龙的颜色可以在不同的会议间发生改变。
对于你组织的会议，你可以得到场上所有变色龙的肤色的种类数。
请在 $20000$ 次会议内，确定每一对具有相同原色的变色龙。
$2leq nleq 500$
题解
如果我们对于每一对点 $(u,v)$ 都询问一遍，那么回答为 $1$ 只有以下三种可能：
- $u,v$ 同色
- $u$ 喜欢 $v$ 且 $v$ 不喜欢 $u$
- $v$ 喜欢 $u$ 且 $u$ 不喜欢 $v$
那么，我们把所有回答为 $1$ 的 $(u,v)$ 之间都连一条无向边。显然，一个点的度数要么为 $1$ 要么为 $3$。如果度数为 $1$ 那么已经确认颜色了。如果度数为 $3$ 的话，设 $a,b$ 同色、$a$ 喜欢 $c$、$d$ 喜欢 $a$，我们考虑问 ${a}$ 并 ${b,c,d}$ 中的大小为 $2$ 的子集。那么当我们问的是 ${a,b,d}$ 时，回答是 $1$，问其他的回答都是 $2$，以此可以确定 $a$ 喜欢的人。全部这样跑就可以确定相同的颜色了。
这样的瓶颈在于前面的确定边，询问次数是 $O(n^2)$ 的。
优化考虑这张图是二分图的性质。我们按顺序确定 $1..2n$ 与前面的点连的边。当进入一个点 $i$ 时，我们把 $1..i-1$ 这些点二染色，弄出二分图。
注意到如果 $S$ 是独立集，$u otin S$，那么 $Scup {u}$ 是独立集 当且仅当 询问 $Scup {u}$ 的回答为 $|S|+1$。
因此我们可以考虑二分确定边，这样确定一个点的复杂度为 $O(log n)$。（另外，为了减小询问时的常数，可以考虑按一个随机顺序询问）
确定边后执行暴力做法的后半段即可确定相同的颜色了。
总的询问复杂度为 $O(nlog n)$。
代码
1 #include "chameleon.h" 2 #include <bits/stdc++.h> 3 using namespace std; 4 namespace { 5 const int N = 1005; 6 mt19937 gen(1145141); 7 int id[N], col[N], vis[N], love[N], fr[N]; 8 vector<int> G[N], cs[2]; 9 void dfs(int u, int c) { 10 cs[col[u] = c].push_back(u); 11 for (int v : G[u]) if (col[v] == -1) dfs(v, c ^ 1); 12 } 13 bool has_e(int c, int l, int r, int u) { 14 vector<int> vec; 15 vec.push_back(u); 16 for (int i = l; i <= r; i++) if (!vis[cs[c][i]]) vec.push_back(cs[c][i]); 17 return Query(vec) < (int)vec.size(); 18 } 19 int dc(int c, int l, int r, int u) { 20 if (l == r) return cs[c][l]; 21 int mid = (l + r) >> 1; 22 if (has_e(c, l, mid, u)) return dc(c, l, mid, u); 23 else return dc(c, mid + 1, r, u); 24 } 25 } 26 void Solve(int n) { 27 for (int i = 1; i <= 2 * n; i++) id[i] = i, love[i] = fr[i] = 0; 28 shuffle(id + 1, id + 1 + 2 * n, gen); 29 for (int i = 1; i <= 2 * n; i++) { 30 int u = id[i]; 31 for (int j = 1; j < i; j++) col[id[j]] = -1, vis[id[j]] = 0; 32 cs[0].clear(), cs[1].clear(); 33 for (int j = 1; j < i; j++) if (col[id[j]] == -1) dfs(id[j], 0); 34 for (int c = 0; c < 2; c++) { 35 while (has_e(c, 0, (int)cs[c].size() - 1, u)) { 36 int v = dc(c, 0, (int)cs[c].size() - 1, u); 37 G[u].push_back(v); 38 G[v].push_back(u); 39 vis[v] = 1; 40 } 41 } 42 } 43 for (int i = 1; i <= 2 * n; i++) if ((int)G[i].size() == 3) { 44 int id; 45 if (Query({i, G[i][0], G[i][1]}) == 1) id = 2; 46 else if (Query({i, G[i][0], G[i][2]}) == 1) id = 1; 47 else id = 0; 48 love[i] = G[i][id]; 49 fr[G[i][id]] = i; 50 } 51 for (int i = 1; i <= 2 * n; i++) { 52 int id; 53 if (G[i][0] != love[i] && G[i][0] != fr[i]) id = 0; 54 else if (G[i][1] != love[i] && G[i][1] != fr[i]) id = 1; 55 else id = 2; 56 if (i < G[i][id]) Answer(i, G[i][id]); 57 } 58 }
LOJ3275. 「JOISC 2020 Day2」有趣的 Joitter 交友
题意
有一张 $n$ 个点的有向图，初始没有边，现在会有 $m$ 条边依次加进图中。每加进一条边时，系统会自动进行如下步骤，直到不能操作为止：
- 选择一个点 $x$，选择一个点 $y$，使得 $x ightarrow y$ 有边。选择一个点 $z$，要求 $z eq x$，$x ightarrow z$ 没有边，且 $y,z$ 之间有二元环。然后让 $x ightarrow z$ 连一条边。
每加进去一条边，都要算出这张图中现在有多少条边。（当然，重边只能算一次，且题目保证无自环）
$2leq nleq 10^5, 1leq mleq 3 imes 10^5$
题解
可以发现如果 $u, v$ 之间有二元环，$v, w$ 之间有二元环，那么 $u, w$ 之间也有二元环，即二元环的关系是传递的，可以看作“二元环连通块”。而且对于一条边 $(u, v)$，$u$ 会向 $v$ 所在的二元环连通块全部连一条边。那么维护好所有的二元环连通块即可很方便地计算答案。合并两个二元环连通块时，需要用启发式合并。
时间复杂度 $O(mlog^2 n)$。
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 //Fast IO start 4 namespace io { 5 const int BUFSIZE = 1 << 20; 6 char ibuf[BUFSIZE], *is = ibuf, *it = ibuf; 7 char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE - 1; 8 inline void read_char(char &c) { 9 if (is == it) { 10 it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); 11 if (is == it) *it++ = EOF; 12 } 13 c = *is++; 14 } 15 template <class T> 16 inline void read_int(T &x) { 17 T f = 1; 18 char c; 19 read_char(c); 20 while (!isdigit(c)) { 21 if (c == '-') { 22 f = -1; 23 } 24 read_char(c); 25 } 26 x = 0; 27 while (isdigit(c)) { 28 x = x * 10 + c - '0'; 29 read_char(c); 30 } 31 x *= f; 32 } 33 inline void flush() { 34 fwrite(obuf, 1, os - obuf, stdout); 35 os = obuf; 36 } 37 inline void print_char(char c) { 38 *os++ = c; 39 if (os == ot) { 40 flush(); 41 } 42 } 43 template <class T> 44 inline void print_int(T x) { 45 static char q[40]; 46 if (!x) { 47 print_char('0'); 48 } else { 49 if (x < 0) { 50 print_char('-'); 51 x = -x; 52 } 53 int top = 0; 54 while (x) { 55 q[top++] = x % 10 + '0'; 56 x /= 10; 57 } 58 while (top--) { 59 print_char(q[top]); 60 } 61 } 62 } 63 struct flusher_t { 64 inline ~flusher_t() { 65 flush(); 66 } 67 } flusher; 68 } 69 using io::read_char; 70 using io::read_int; 71 using io::print_char; 72 using io::print_int; 73 //Fast IO end 74 const int N = 100005; 75 int n, m, dsu[N], sz[N]; 76 long long ans; 77 map<int, set<int> > Gto[N]; 78 set<int> Gfr[N]; 79 int sfr[N]; 80 int Find(int x) { 81 return x == dsu[x] ? x : dsu[x] = Find(dsu[x]); 82 } 83 void Merge(set<int> &st1, set<int> &st2) { 84 if (st1.size() < st2.size()) st1.swap(st2); 85 for (auto &x : st2) st1.insert(x); 86 st2.clear(); 87 } 88 void Union(int x, int y) { 89 x = Find(x); y = Find(y); 90 if (x == y) return; 91 if (sz[x] < sz[y]) swap(x, y); 92 dsu[y] = x; 93 ans -= 1ll * Gto[x][y].size() * sz[y]; 94 ans -= 1ll * Gto[y][x].size() * sz[x]; 95 sfr[x] -= Gto[y][x].size(); 96 sfr[y] -= Gto[x][y].size(); 97 Gto[x].erase(y); 98 Gto[y].erase(x); 99 Gfr[x].erase(y); 100 Gfr[y].erase(x); 101 ans += 2ll * sz[x] * sz[y]; 102 ans -= 1ll * sfr[x] * sz[x]; 103 ans -= 1ll * sfr[y] * sz[y]; 104 sz[x] += sz[y]; 105 set<int> may; 106 for (map<int, set<int> >::iterator it = Gto[y].begin(); it != Gto[y].end(); ++it) { 107 may.insert(it -> first); 108 Merge(Gto[x][it -> first], it -> second); 109 Gfr[it -> first].erase(y); 110 Gfr[it -> first].insert(x); 111 } 112 Gto[y].clear(); 113 for (set<int>::iterator it = Gfr[y].begin(); it != Gfr[y].end(); ++it) { 114 may.insert(*it); 115 Gfr[x].insert(*it); 116 sfr[x] -= Gto[*it][x].size(); 117 Merge(Gto[*it][x], Gto[*it][y]); 118 sfr[x] += Gto[*it][x].size(); 119 Gto[*it].erase(y); 120 } 121 Gfr[y].clear(); 122 ans += 1ll * sfr[x] * sz[x]; 123 for (auto &z : may) { 124 if (Find(x) != Find(z)) { 125 if (Gfr[x].count(z) && Gfr[z].count(x)) Union(x, z); 126 } 127 } 128 } 129 void Gao(int u, int v) { 130 if (Find(u) == Find(v)) return; 131 map<int, set<int> >::iterator fuckit = Gto[Find(u)].find(Find(v)); 132 if (fuckit != Gto[Find(u)].end() && (fuckit -> second).count(u)) return; 133 Gto[Find(u)][Find(v)].insert(u); 134 Gfr[Find(v)].insert(Find(u)); 135 sfr[Find(v)]++; 136 ans += sz[Find(v)]; 137 if (Gto[Find(v)].find(Find(u)) != Gto[Find(v)].end()) Union(u, v); 138 } 139 int main() { 140 read_int(n); 141 read_int(m); 142 for (int i = 1; i <= n; i++) dsu[i] = i, sz[i] = 1; 143 ans = 0; 144 for (int i = 1; i <= m; i++) { 145 int u, v; 146 read_int(u); 147 read_int(v); 148 Gao(u, v); 149 print_int(ans); 150 print_char(' '); 151 } 152 return 0; 153 }
LOJ3276. 「JOISC 2020 Day2」遗迹
题意
很久很久以前，有 $2n$ 根石柱，编号为 $1..2n$。对于任意 $kin[1,n]$，恰好有两根石柱高度为 $k$。
随后发生了 $n$ 次地震。每次地震会把所有未被保护的石柱的高度减 $1$，而被保护的石柱高度不变。在这 $n$ 次地震后，只剩下 $n$ 根石柱了，即只有 $n$ 根石柱的高度至少为 $1$。
每次地震发生前，古人类按照如下方式保护石柱：对于任意 $kin[1,n]$，只保护恰好一根高度为 $k$ 的石柱，如有多个则保护编号最大的那个。
现在已知 $n$ 次地震后剩下的石柱的编号，求出初始时 $2n$ 根石柱的高度组合种数模 $10^9+7$。
$1leq nleq 600$
题解
（为了方便起见，我们先约定两个相同高度的数是不同的，最后再把答案除以 $2^n$）
如果给定了初始序列 $a$，如何得到最终剩下的石柱，可以用如下代码实现：
1 for (int i = 2 * n; i; i--) { 2 int found = 0; 3 for (int j = a[i]; j; j--) { 4 if (!vis[j]) { 5 found = 1; 6 vis[j] = 1; 7 break; 8 } 9 } 10 // found 为 1 则 i 是剩下的石柱，且最终高度为 j，为 0 则 i 是不剩下的石柱，即最终高度为 0 的石柱 11 }
那么我们考虑 $i$ 从大到小扫。可以发现，一个石柱的初始高度 $h$ 会变成 $0$，当且仅当 $1..h$ 已经被 $vis$ 过了。
所以我们只关心到目前为止，最长的全部 $vis$ 过的前缀有多长。那么石柱会剩下当且仅当其初始高度大于这个最长前缀。
设 $f(i, j)$ 表示从 $2n$ 扫到 $i$，当前最长的全部 $vis$ 过的前缀为 $j$，只考虑 不剩下的石柱 和 最终高度 $leq j$ 的石柱 的贡献，目前的方案数。初始值就是 $f(2n+1, 0)=1$。
下设 $s0$ 表示 $i+1$ 到 $2n$ 的不剩下的石柱个数，$s1$ 同理表示剩下的石柱的个数。
转移的话，如果第 $i$ 个石柱最终不剩下，那么它的初始高度肯定是 $leq j$ 的，则它的初始高度选法有 $j-s0$ 种。（高度 $leq j$ 的有 $2j$ 个数，去掉剩下的石柱的 $j$ 种，再去掉之前不剩下的石柱的 $s0$ 种，就是 $j-s0$ 了）
如果第 $i$ 个石柱最终剩下，那么有两种可能：
一种是它并没有让 $j$ 增加，根据定义，不增加更多贡献。
另一种是它让 $j$ 变大了，我们枚举它变成了 $k(k>j)$。那么 $f(i+1, j)$ 对 $f(i, k)$ 的贡献是 $f(i+1, j) imesinom{s1-j}{k-j-1} imes ways(k-j-1) imes (k-j+1)$。
其中 $ways(i)$ 的意思是：有 $i$ 根石柱，要给它们安排 $1..i$ 中的初始高度，每种高度数量不超过 $2$，且它们最终高度是 $1..i$ 的方案数。我们马上会给出它的求法。
现在先理解一下这个贡献：先是 $f(i+1, j)$ 表示之前的贡献，$inom{s1-j}{k-j-1}$ 表示之前高度 $>j+1$ 的石柱中，选出一些来作为新的前缀，$ways(k-j-1)$ 表示选出的这些的石柱的初始高度安排的方案数，$(k-j+1)$ 表示第 $i$ 根石柱的初始高度选法。（把之前的石柱和第 $i$ 根石柱分开来搞，是因为第 $i$ 根石柱的最终高度必须是 $j+1$）
再来看一下 $ways(i)$ 的求法。我们要知道结论：设 $ps_j$ 表示初始高度 $leq j$ 的石柱个数，那么这些石柱的最终高度是 $1..i$ 当且仅当 对于任意 $jleq i$，有 $ps_jleq j$（即每个前缀都不能容下更多的数），且 $ps_i=i$（即数的个数必须是 $i$）。
于是我们考虑 $g(i, j)$ 表示考虑了高度 $1..i$，$ps_i$ 为 $j$ 的合法方案数。初始值为 $g(0,0)=1$。转移只需枚举下一个数有几个即可。注意由于最开始我们规定两个相同高度的数是不同的，因此在某些情况下要让贡献乘 $2$，具体见代码。
则 $ways(i)=g(i,i)$。
最终的答案就是 $f(1, n)$。别忘了除以 $2^n$。
求 $g$ 的时间复杂度为 $O(n^2)$，求 $f$ 的时间复杂度为 $O(n^3)$，总的时间复杂度为 $O(n^3)$。
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1205; 4 const int mod = 1000000007; 5 int n, has[N], binom[N][N], f[N][N], g[N][N], ways[N]; 6 int main() { 7 scanf("%d", &n); 8 for (int i = binom[0][0] = 1; i <= n; i++) { 9 for (int j = binom[i][0] = 1; j <= i; j++) { 10 binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % mod; 11 } 12 } 13 g[0][0] = 1; 14 for (int i = 1; i <= n; i++) { 15 for (int j = 0; j < i; j++) if (g[i - 1][j]) { 16 for (int k = 0; k <= 2; k++) if (j + k <= i) { 17 g[i][j + k] = (g[i][j + k] + (k ? 2ll : 1ll) * g[i - 1][j] * binom[j + k][k]) % mod; 18 } 19 } 20 } 21 for (int i = 0; i <= n; i++) { 22 ways[i] = g[i][i]; 23 } 24 for (int i = 1; i <= n; i++) { 25 int x; 26 scanf("%d", &x); 27 has[x] = 1; 28 } 29 f[2 * n + 1][0] = 1; 30 int s0 = 0, s1 = 0; 31 for (int i = 2 * n; i; i--) { 32 if (!has[i]) { 33 for (int j = 0; j <= n; j++) if (f[i + 1][j]) { 34 f[i][j] = 1ll * f[i + 1][j] * max(0, j - s0) % mod; 35 } 36 s0++; 37 } else { 38 for (int j = 0; j <= n; j++) f[i][j] = f[i + 1][j]; 39 for (int j = 0; j <= n; j++) if (f[i + 1][j]) { 40 for (int k = j + 1; k <= n; k++) { 41 f[i][k] = (f[i][k] + 1ll * f[i + 1][j] * binom[s1 - j][k - j - 1] % mod * ways[k - j - 1] % mod * (k - j + 1)) % mod; 42 } 43 } 44 s1++; 45 } 46 } 47 int ans = f[1][n]; 48 for (int i = 1; i <= n; i++) ans = ((ans & 1) ? ans + mod : ans) >> 1; 49 printf("%d ", ans); 50 return 0; 51 }
LOJ3277. 「JOISC 2020 Day3」星座 3
题意
有一张 $n imes n$ 的星空图，将左起第 $x$ 列，下起第 $y$ 行的像素点称为 $(x,y)$。画面里有白色的楼，黄色的星星，黑色的天空。第 $i$ 列从最下方起 $A_i$ 行都是白色的楼。有 $m$ 个星星，位置也已经给定。其他的所有像素点都是黑色的天空。
一个长方形区域能被称为星座，当且仅当它里面不含白色的点，且至少存在两个星星。
我们可以把一些星星涂成黑色，使得没有星座存在。但把每个星星 $j$ 涂成黑色有 $C_j$ 的代价。求最小使用多少代价可以满足条件。
$1leq n,mleq 2 imes 10^5$
题解
对于所有不包含白色的长方形，我们只考虑极大的。即建出楼的笛卡尔树，树上每个点会对应一个极大的长方形。
然后，可以发现，如果我们选择一个星星，并把它保留，那么树上会有一条祖孙链都不能保留其他星星了，但其他的地方不会影响。
因此我们考虑 $f_i$ 表示以 $i$ 为子树的最大保留代价，转移的时候枚举这个点内是否保留星星以及保留哪一个，BIT 维护即可。
答案就是所有代价的和 减去 最大保留代价。
时间复杂度 $O(nlog n)$。
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 200005; 4 struct Node { 5 int x, y, w; 6 }; 7 vector<Node> pts[N]; 8 pair<int, int> tr[N * 4]; 9 void build(int i, int l, int r) { 10 if (l == r) { 11 if (pts[l].size()) tr[i] = make_pair(pts[l].back().y, l); 12 else tr[i] = make_pair(-1, l); 13 return; 14 } 15 int mid = (l + r) >> 1; 16 build(i << 1, l, mid); 17 build(i << 1 | 1, mid + 1, r); 18 tr[i] = max(tr[i << 1], tr[i << 1 | 1]); 19 } 20 pair<int, int> Query(int i, int l, int r, int lf, int rg) { 21 if (lf <= l && r <= rg) return tr[i]; 22 int mid = (l + r) >> 1; 23 if (rg <= mid) return Query(i << 1, l, mid, lf, rg); 24 else if (lf > mid) return Query(i << 1 | 1, mid + 1, r, lf, rg); 25 else return max(Query(i << 1, l, mid, lf, rg), Query(i << 1 | 1, mid + 1, r, lf, rg)); 26 } 27 void Modify(int i, int l, int r, int pos) { 28 if (l == r) { 29 if (pts[l].size()) tr[i] = make_pair(pts[l].back().y, l); 30 else tr[i] = make_pair(-1, l); 31 return; 32 } 33 int mid = (l + r) >> 1; 34 if (pos <= mid) Modify(i << 1, l, mid, pos); 35 else Modify(i << 1 | 1, mid + 1, r, pos); 36 tr[i] = max(tr[i << 1], tr[i << 1 | 1]); 37 } 38 int n, m, A[N], lg2[N], ST[18][N]; 39 inline int Qmax(int l, int r) { 40 int i = lg2[r - l + 1]; 41 if (A[ST[i][l]] >= A[ST[i][r - (1 << i) + 1]]) 42 return ST[i][l]; 43 else 44 return ST[i][r - (1 << i) + 1]; 45 } 46 int K, mxi[N], repL[N], repR[N], dR[N], bel[N]; 47 vector<int> G[N]; 48 vector<Node> np[N]; 49 struct BIT { 50 int n; 51 long long bit[N]; 52 inline void Init(int _n) { 53 n = _n; 54 for (int i = 1; i <= n; i++) bit[i] = 0; 55 } 56 inline void add(int i, long long x) { 57 while (i <= n) { 58 bit[i] += x; 59 i += i & -i; 60 } 61 } 62 inline long long sum(int i) { 63 long long res = 0; 64 while (i > 0) { 65 res += bit[i]; 66 i -= i & -i; 67 } 68 return res; 69 } 70 } bit1; 71 long long dp[N]; 72 void dfs2(int u) { 73 dp[u] = 0; 74 for (int v : G[u]) dfs2(v), dp[u] += dp[v]; 75 for (int v : G[u]) { 76 bit1.add(v, dp[u] - dp[v]); 77 bit1.add(dR[v] + 1, dp[v] - dp[u]); 78 } 79 bit1.add(u, dp[u]); 80 bit1.add(u + 1, -dp[u]); 81 for (auto &P : np[u]) { 82 int v = bel[P.x]; 83 dp[u] = max(dp[u], bit1.sum(v) + P.w); 84 } 85 //printf("u %d dp %lld ", u, dp[u]); 86 } 87 int dfs1(int l, int r) { 88 int i = Qmax(l, r); 89 int cur = ++K; 90 //printf("cur %d %d %d ", cur, l, r); 91 bel[i] = cur; 92 mxi[cur] = i; 93 repL[cur] = l; 94 repR[cur] = r; 95 pair<int, int> P; 96 while ((P = Query(1, 1, n, l, r)).first > A[i]) { 97 np[cur].push_back(pts[P.second].back()); 98 //printf("P %d %d ", P.first, P.second); 99 pts[P.second].pop_back(); 100 Modify(1, 1, n, P.second); 101 } 102 int nl, nr; 103 nl = l; 104 nr = i - 1; 105 if (nl <= nr) G[cur].push_back(dfs1(nl, nr)); 106 nl = i + 1; 107 nr = r; 108 if (nl <= nr) G[cur].push_back(dfs1(nl, nr)); 109 dR[cur] = K; 110 return cur; 111 } 112 int main() { 113 scanf("%d", &n); 114 for (int i = 1; i <= n; i++) scanf("%d", &A[i]), ST[0][i] = i; 115 lg2[0] = -1; 116 for (int i = 1; i <= n; i++) lg2[i] = lg2[i - 1] + ((i & (i - 1)) ? 0 : 1); 117 for (int i = 1; i < 18; i++) { 118 for (int j = 1; j <= n - (1 << i) + 1; j++) { 119 if (A[ST[i - 1][j]] >= A[ST[i - 1][j + (1 << (i - 1))]]) 120 ST[i][j] = ST[i - 1][j]; 121 else 122 ST[i][j] = ST[i - 1][j + (1 << (i - 1))]; 123 } 124 } 125 scanf("%d", &m); 126 long long totsum = 0; 127 for (int i = 1; i <= m; i++) { 128 Node pt; 129 scanf("%d%d%d", &pt.x, &pt.y, &pt.w); 130 pts[pt.x].push_back(pt); 131 totsum += pt.w; 132 } 133 for (int i = 1; i <= n; i++) sort(pts[i].begin(), pts[i].end(), [](Node a, Node b) { 134 return a.y < b.y; 135 }); 136 build(1, 1, n); 137 K = 0; 138 dfs1(1, n); 139 bit1.Init(K); 140 dfs2(1); 141 printf("%lld ", totsum - dp[1]); 142 return 0; 143 }
LOJ3278. 「JOISC 2020 Day3」收获
题意
有 $n$ 个员工，$m$ 棵树种在湖岸。湖的周长为 $L$。一开始员工都站在湖岸的一些不同的位置处，所有树都种在湖岸的一些不同的位置处（初始没有树和人重合），这些位置已经给定。
每棵树最多会长出一个苹果，收获后 $C$ 秒就会再长出个新的。在时刻 $0$，所有树上都有一个苹果。员工从时刻 $0$ 开始从各自的地点以 $1$ 的速度顺时针前进。一旦遇到成熟的苹果就将其摘下（摘取时间不计），如果到达时刚长出苹果也要摘。
现在有 $Q$ 次询问，每次询问在时刻 $T$ 结束时员工 $V$ 摘到的苹果数。
$1leq n,mleq 2 imes 10^5, n+mleq Lleq 10^9, 1leq Cleq 10^9, 1leq Qleq 2 imes 10^5, Tleq 10^{18}$
题解
看作是树在逆时针移动，人不动。
那么可以发现，在树遇到第一个人之后，走至少 $C$ 的位置后遇到的下一个人是接下来摘苹果的那一个。由于 $C$ 是不变的，因此每个人对应的下一个摘苹果的人也是确定的，可以构成一棵基环树森林。
考虑询问。对于树的部分，每个询问只需要求出在 $V$ 的子树内的、到达 $V$ 的时候时间 $leq T$ 的苹果树个数。这是个二维数点。
对于环的部分，相当于我们要在所有能够在时间 $T$ 内到达环的苹果树中求贡献，贡献形如 $lfloorfrac{X-Y}{Z} floor$，其中 $X,Z$ 的值只与环或者环上的点有关（$Z$ 就是环长），$Y$ 的值只与苹果树的信息有关。这种整除的贡献，可以考虑把模 $Z$ 的余数部分去掉变成直接除法，另外应该还要分大于和小于 $X mod Z$ 考虑。由于我们只考虑能够在时间 $T$ 内到达环的苹果树，不难想到用可持久化线段树维护这个东西。
由于这个除法的被除数有爆 long long 的可能，因此需要在一些地方用 __int128。
时间复杂度 $O(nlog n)$。
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 //Fast IO start 4 namespace io { 5 const int BUFSIZE = 1 << 20; 6 char ibuf[BUFSIZE], *is = ibuf, *it = ibuf; 7 char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE - 1; 8 inline void read_char(char &c) { 9 if (is == it) { 10 it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); 11 if (is == it) *it++ = EOF; 12 } 13 c = *is++; 14 } 15 template <class T> 16 inline void read_int(T &x) { 17 T f = 1; 18 char c; 19 read_char(c); 20 while (!isdigit(c)) { 21 if (c == '-') { 22 f = -1; 23 } 24 read_char(c); 25 } 26 x = 0; 27 while (isdigit(c)) { 28 x = x * 10 + c - '0'; 29 read_char(c); 30 } 31 x *= f; 32 } 33 inline void flush() { 34 fwrite(obuf, 1, os - obuf, stdout); 35 os = obuf; 36 } 37 inline void print_char(char c) { 38 *os++ = c; 39 if (os == ot) { 40 flush(); 41 } 42 } 43 template <class T> 44 inline void print_int(T x) { 45 static char q[40]; 46 if (!x) { 47 print_char('0'); 48 } else { 49 if (x < 0) { 50 print_char('-'); 51 x = -x; 52 } 53 int top = 0; 54 while (x) { 55 q[top++] = x % 10 + '0'; 56 x /= 10; 57 } 58 while (top--) { 59 print_char(q[top]); 60 } 61 } 62 } 63 struct flusher_t { 64 inline ~flusher_t() { 65 flush(); 66 } 67 } flusher; 68 } 69 using io::read_char; 70 using io::read_int; 71 using io::print_char; 72 using io::print_int; 73 //Fast IO end 74 const int N = 200005; 75 struct BIT { 76 int n; 77 long long bit[N]; 78 inline void Init(int _n) { 79 n = _n; 80 for (int i = 1; i <= n; i++) bit[i] = 0; 81 } 82 inline void add(int i, long long x) { 83 while (i <= n) { 84 bit[i] += x; 85 i += i & -i; 86 } 87 } 88 inline long long sum(int i) { 89 long long res = 0; 90 while (i > 0) { 91 res += bit[i]; 92 i -= i & -i; 93 } 94 return res; 95 } 96 } bit; 97 int n, m, Q, par[N], g[N], fr_rt[N]; 98 long long L, C, parlen[N], dep[N], f[N], A[N * 2], B[N], ans[N], ps[N]; 99 int dsu[N]; 100 int Find(int x) { 101 return x == dsu[x] ? x : dsu[x] = Find(dsu[x]); 102 } 103 vector<pair<long long, int> > buck[N]; 104 vector<int> tt[N]; 105 vector<int> roots; 106 vector<int> G[N]; 107 inline void Pre_calc() { 108 for (int i = n + 1, j = 1; i <= n * 2; i++) { 109 while (j < i && A[i] - A[j + 1] >= C % L) j++; 110 par[i - n] = j <= n ? j : j - n; 111 parlen[i - n] = (C / L) * L + A[i] - A[j]; 112 } 113 int i = 1, j = 1; 114 while (i <= n && j <= m) { 115 if (A[i] < B[j]) { 116 i++; 117 } else { 118 g[j] = (i > 1 ? i - 1 : n); 119 f[j] = (B[j] - A[g[j]] + L) % L; 120 j++; 121 } 122 } 123 while (j <= m) { 124 g[j] = n; 125 f[j] = (B[j] - A[g[j]] + L) % L; 126 j++; 127 } 128 for (int i = 1; i <= n; i++) { 129 dsu[i] = i; 130 } 131 for (int i = 1; i <= n; i++) { 132 if (Find(i) != Find(par[i])) { 133 dsu[Find(i)] = Find(par[i]); 134 G[par[i]].push_back(i); 135 } else { 136 roots.push_back(i); 137 } 138 } 139 } 140 int dfc, dL[N], dR[N]; 141 void dfs(int u, long long depth) { 142 dL[u] = ++dfc; 143 dep[u] = depth; 144 for (int v : G[u]) fr_rt[v] = fr_rt[u], dfs(v, depth + parlen[v]); 145 dR[u] = dfc; 146 } 147 struct Point { 148 long long x; 149 int y; 150 int id; 151 }; 152 vector<Point> pts; 153 struct Node { 154 int lson, rson, cnt; 155 __int128 sum; 156 inline Node() { lson = rson = cnt = 0; sum = 0; } 157 } tr[N * 19]; 158 int tr_rt[N], cnt_tr; 159 void Ins(int &x, int y, int l, int r, int pos, long long v) { 160 x = ++cnt_tr; 161 tr[x] = tr[y]; 162 tr[x].cnt++; 163 tr[x].sum += v; 164 if (l == r) return; 165 int mid = (l + r) >> 1; 166 if (pos <= mid) Ins(tr[x].lson, tr[y].lson, l, mid, pos, v); 167 else Ins(tr[x].rson, tr[y].rson, mid + 1, r, pos, v); 168 } 169 pair<__int128, int> getsum(int x, int l, int r, int lf, int rg) { 170 if (!x) return make_pair(0, 0); 171 if (lf <= l && r <= rg) return make_pair(tr[x].sum, tr[x].cnt); 172 int mid = (l + r) >> 1; 173 pair<__int128, int> P1(0, 0), P2(0, 0); 174 if (lf <= mid) P1 = getsum(tr[x].lson, l, mid, lf, rg); 175 if (rg > mid) P2 = getsum(tr[x].rson, mid + 1, r, lf, rg); 176 return make_pair(P1.first + P2.first, P1.second + P2.second); 177 } 178 int main() { 179 //freopen("input.txt", "r", stdin); 180 read_int(n); 181 read_int(m); 182 read_int(L); 183 read_int(C); 184 for (int i = 1; i <= n; i++) read_int(A[i]), A[i + n] = A[i] + L; 185 for (int i = 1; i <= m; i++) read_int(B[i]); 186 Pre_calc(); 187 dfc = 0; 188 for (int rt : roots) fr_rt[rt] = rt, dfs(rt, 0); 189 for (int j = 1; j <= m; j++) { 190 pts.push_back((Point){f[j] + dep[g[j]], dL[g[j]], 0}); 191 tt[fr_rt[g[j]]].push_back(j); 192 } 193 read_int(Q); 194 for (int i = 1; i <= Q; i++) { 195 int u; 196 long long T; 197 read_int(u); 198 read_int(T); 199 buck[u].push_back(make_pair(T, i)); 200 pts.push_back((Point){dep[u] + T, u, i}); 201 ans[i] = 0; 202 } 203 sort(pts.begin(), pts.end(), [](Point a, Point b) { 204 if (a.x != b.x) return a.x < b.x; 205 return a.id < b.id; 206 }); 207 bit.Init(n); 208 for (auto &P : pts) { 209 if (!P.id) { 210 bit.add(P.y, 1); 211 } else { 212 int u = P.y; 213 ans[P.id] += bit.sum(dR[u]) - bit.sum(dL[u] - 1); 214 } 215 } 216 for (int rt : roots) { 217 vector<int> us; 218 int u = par[rt]; 219 long long len = parlen[rt]; 220 while (u != rt) { 221 us.push_back(u); 222 ps[u] = len; 223 len += parlen[u]; 224 u = par[u]; 225 } 226 us.push_back(rt); 227 ps[rt] = len; 228 vector<long long> vals, mods; 229 for (int j : tt[rt]) { 230 long long val = dep[g[j]] + f[j], rem = val % len; 231 vals.push_back(val); 232 mods.push_back(rem); 233 } 234 sort(vals.begin(), vals.end()); 235 sort(mods.begin(), mods.end()); 236 mods.resize(unique(mods.begin(), mods.end()) - mods.begin()); 237 int cnt = 0; 238 tr_rt[0] = 0; 239 cnt_tr = 0; 240 for (long long val : vals) { 241 int pos = lower_bound(mods.begin(), mods.end(), val % len) - mods.begin() + 1; 242 cnt++; 243 Ins(tr_rt[cnt], tr_rt[cnt - 1], 1, (int)mods.size(), pos, val - val % len); 244 } 245 for (int u : us) { 246 for (auto Que : buck[u]) { 247 long long T = Que.first - ps[u] + len; 248 int r = upper_bound(vals.begin(), vals.end(), Que.first - ps[u]) - vals.begin(); 249 int pos = upper_bound(mods.begin(), mods.end(), T % len) - mods.begin(); 250 if (pos >= 1) { 251 pair<__int128, int> P = getsum(tr_rt[r], 1, (int)mods.size(), 1, pos); 252 __int128 s = P.first; 253 int cc = P.second; 254 __int128 tmp = T - T % len; 255 tmp = tmp * cc; 256 tmp -= s; 257 tmp /= len; 258 ans[Que.second] += (long long)tmp; 259 } 260 if (pos <= (int)mods.size()) { 261 pair<__int128, int> P = getsum(tr_rt[r], 1, (int)mods.size(), pos + 1, (int)mods.size()); 262 __int128 s = P.first; 263 int cc = P.second; 264 __int128 tmp = T - T % len - len; 265 tmp = tmp * cc; 266 tmp -= s; 267 tmp /= len; 268 ans[Que.second] += (long long)tmp; 269 } 270 } 271 } 272 for (int i = 1; i <= cnt_tr; i++) tr[i] = Node(); 273 } 274 for (int i = 1; i <= Q; i++) print_int(ans[i]), print_char(' '); 275 return 0; 276 }
LOJ3279. 「JOISC 2020 Day3」迷路的猫
（LOJ 暂不支持评测通信题，可以在 UOJ 上测）
题意
这是一道通信题。
有一张 $n$ 个点 $m$ 条边的连通无向图，给了代码 A。点和边的编号都从 $0$ 开始。现在代码 A 可以给这 $m$ 条边做标记，一共有 $A$ 种标记：$0..A-1$。每条边都要做其中一个标记。
然后，代码 B 会被系统放在其中一个非零的点中。但 B 是个路痴，并不知道这是哪一个点，它只能知道对于每种标记 $i$，与这个点相连的边有 $y[i]$ 条是标记 $i$。B 会选择一个标记并走进这个标记的其中一条边中。（具体走的边由系统指定，不一定是均匀随机的。）另外，如果已经走了至少一步，B 可以直接弄清楚哪条边是刚刚走的，即这条边不需要通过标记来辨认（方便起见，我们不会把这条边放在 $y[i]$ 的统计中去）。所以 B 除了选择一个标记走以外，也可以选择刚刚走过的那条边，并走回去。B 的目标是走到点 $0$。
当然，由于标记种类很少，所以我们允许 B 走一些弯路。设从 $0$ 到 B 的起点 $S$ 的最短路为 $d$，那么你要保证 B 在走不超过 $d+B$ 步后能够走到点 $0$。其中 $B$ 是个给定的非负整数。
请实现代码 A 和 B，让 A 对边做标记，让 B 在标记的图上走，使得满足上述条件。
对于所有数据，有 $2leq nleq 20000, 1leq mleq 20000$，图保证连通，无重边自环。
子任务有两类，如下（我们都取两类中的最严格限制）：
- $A=3, B=0$（$15$ 分）
- $A=2, B=6, m=n-1$（$85$ 分）
题解
对于第一类子任务。我们只能走最短路。
考虑求出这张图的 BFS 树，显然，所有边要么是连接相邻两层的点（异层边），要么是连接同层的点（同层边）。
如果没有同层边，那么我们只要对于每一层的边做同一种标记，按 $0,1,2$ 循环标记即可。因为这样的话，在某一个点上，即使有两种存在的标记，我们也可以确定哪一个是往上走的。
那么如果有了同层边，其实也很简单，只要做它下面的那一层的边的标记即可。如下图所示。
这样我们依旧可以确定哪一条边是向上的。
对于第二类子任务，只有两种标记，但图是一个树，而且允许多走六步。
我们先考虑把树划分为若干条链，如果一个点有至少两个儿子，那么称之为分叉点。我们希望标记能够满足：
- 对于每个分叉点，到父亲的边和到儿子的边的标记不同。
- 每一条链上都是 $110010$ 的循环位移。
那么对于代码 B，它先走三步，如果中途走到非链的部分就直接确定了方向。否则，它还在链上，而且可以确定周围长度为 $5$ 的子串的样子，这样的话，一定可以确定它是在往上走还是往下走，这样也确定了方向，而且最多多走 $6$ 步。
细节有点多，写的时候要注意。
代码
代码 A（Anthony.cpp）：
1 #include "Anthony.h" 2 #include <bits/stdc++.h> 3 using namespace std; 4 vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) { 5 vector<int> dist(n, -1); 6 vector<vector<int> > G(n); 7 for (int i = 0; i < m; i++) { 8 G[U[i]].push_back(V[i]); 9 G[V[i]].push_back(U[i]); 10 } 11 dist[0] = 0; 12 queue<int> que; 13 que.push(0); 14 while (!que.empty()) { 15 int u = que.front(); que.pop(); 16 for (int v : G[u]) { 17 if (dist[v] == -1) { 18 dist[v] = dist[u] + 1; 19 que.push(v); 20 } 21 } 22 } 23 vector<int> ret(m); 24 if (A >= 3) { 25 for (int i = 0; i < m; i++) { 26 ret[i] = min(dist[U[i]], dist[V[i]]) % 3; 27 } 28 } else { 29 const int arr[6] = {1, 1, 0, 0, 1, 0}; 30 for (int i = 0; i < n; i++) G[i].clear(); 31 for (int i = 0; i < m; i++) { 32 if (dist[U[i]] > dist[V[i]]) swap(U[i], V[i]); 33 G[U[i]].push_back(i); 34 } 35 function<void(int, int)> dfs = [&](int u, int fr) { 36 if ((int)G[u].size() == 1) { 37 int p; 38 if (fr == -1 || ret[fr] == 0) { 39 p = 0; 40 } else { 41 p = 2; 42 } 43 while ((int)G[u].size() == 1) { 44 int i = G[u][0]; 45 int v = V[i]; 46 u = v; 47 fr = i; 48 ret[fr] = arr[p]; 49 p = (p + 1) % 6; 50 } 51 } 52 int c = (fr == -1 ? 1 : ret[fr] ^ 1); 53 for (int i : G[u]) { 54 int v = V[i]; 55 ret[i] = c; 56 dfs(v, i); 57 } 58 }; 59 dfs(0, -1); 60 } 61 return ret; 62 }
代码 B（Catherine.cpp）：
1 #include "Catherine.h" 2 #include <bits/stdc++.h> 3 using namespace std; 4 namespace { 5 const int arr[6] = {1, 1, 0, 0, 1, 0}; 6 int A, on, fir, last; 7 vector<int> vec; 8 vector<int> cs; 9 inline bool bad(vector<int> v) { 10 vector<int> al; 11 for (int i = 0; i < 6; i++) al.push_back(arr[i]); 12 for (int i = 0; i < 6; i++) al.push_back(arr[i]); 13 for (int i = 0; i < 8; i++) { 14 int flag = 1; 15 for (int j = 0; j < 5; j++) if (al[i + j] != v[j]) { 16 flag = 0; 17 break; 18 } 19 if (flag) return true; 20 } 21 return false; 22 } 23 } 24 void Init(int _A, int B) { 25 A = _A; 26 on = 0; 27 fir = 1; 28 last = -1; 29 } 30 int Move(vector<int> y) { 31 if (A >= 3) { 32 int cc = 0; 33 for (int i = 0; i < 3; i++) cc += (y[i] != 0 ? 1 : 0); 34 if (cc == 1) { 35 if (y[0]) return 0; 36 else if (y[1]) return 1; 37 else return 2; 38 } else { 39 if (y[0] && y[1]) return 0; 40 else if (y[1] && y[2]) return 1; 41 else return 2; 42 } 43 } else { 44 if (on) { 45 if (y[0] == 1 && y[1] != 1) return last = 0; 46 else if (y[0] != 1 && y[1] == 1) return last = 1; 47 else return last ^= 1; 48 } 49 if (fir) { 50 fir = 0; 51 if (y[0] != 1 && y[1] != 1) { 52 if (y[0]) last = 0; 53 else last = 1; 54 y[last]--; 55 cs = y; 56 vec.push_back(last); 57 return last; 58 } 59 if (y[0] == 1) last = 0; 60 else last = 1; 61 if (y[last ^ 1] != 1) { 62 on = 1; 63 return last; 64 } 65 y[last]--; 66 cs = y; 67 vec.push_back(last); 68 return last; 69 } 70 if (y[0] != 1 && y[1] != 1) { 71 on = 1; 72 return -1; 73 } 74 if (y[0] == 1 && y[1] == 1) { 75 on = 1; 76 return last ^= 1; 77 } 78 if (y[0] > 1) { 79 on = 1; 80 return last = 1; 81 } 82 if (y[1] > 1) { 83 on = 1; 84 return last = 0; 85 } 86 if (vec.size() < 3) { 87 if (y[0]) last = 0; 88 else last = 1; 89 vec.push_back(last); 90 return last; 91 } 92 vector<int> v; 93 v.push_back(cs[0] ? 0 : 1); 94 for (int i = 0; i < 3; i++) { 95 v.push_back(vec[i]); 96 } 97 v.push_back(y[0] ? 0 : 1); 98 on = 1; 99 if (bad(v)) { 100 return -1; 101 } else { 102 return last = v.back(); 103 } 104 } 105 }
LOJ3280. 「JOISC 2020 Day4」首都城市
题意
给定一棵 $n$ 个节点的树，每个节点 $i$ 会属于某一座城市 $C_i$。一共有 $k$ 座城市，保证每一座都有管辖的节点（即每一座城市都非空）。
现在想要在这 $k$ 座城市中选出一个作为首都。为了安全，要求首都城市管辖的节点的导出子图必须是一个连通块。
不过可能并没有这样的城市，因此国王打算合并一些城市，使得存在至少一座满足上述条件的城市。
每次只能合并两座城市，而且合并一次会花费 $1$ 的代价。求达到目标的最小代价。
$1leq kleq nleq 2 imes 10^5$
题解
对于每座城市，如果它作为了最终首都的一部分，那么它有可能要依赖某些其他的城市（即选了它就必须选一些其他的城市）。
具体来说，把这座城市的点集的虚树建出来，那么虚树的边上的所有点所在的城市都是要依赖的。（事实上并不需要建出虚树那么麻烦，其实把所有点的 LCA 取出来，然后把每个点到 LCA 的路径取出来即可。）
这样依赖的边数可能会很多，因此使用数据结构优化建图。我们考虑使用倍增来优化，这样每条路径会连 $O(log n)$ 条依赖关系的边。建出的依赖图中，共有 $O(nlog n)$ 个点和 $O(nlog n)$ 条边，可以接受。
然后对这个依赖图进行强连通缩点，得到一个 DAG，其中 DAG 上每个点会带权（带的就是里面包含的城市个数）。那么在这个 DAG 中，不依赖其他点的点就是答案的备选（否则肯定不是最优的），从中选取权值最小的那个即可。
时间复杂度 $O(nlog n)$。
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 //Fast IO start 4 namespace io { 5 const int BUFSIZE = 1 << 20; 6 char ibuf[BUFSIZE], *is = ibuf, *it = ibuf; 7 char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE - 1; 8 inline void read_char(char &c) { 9 if (is == it) { 10 it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); 11 if (is == it) *it++ = EOF; 12 } 13 c = *is++; 14 } 15 template <class T> 16 inline void read_int(T &x) { 17 T f = 1; 18 char c; 19 read_char(c); 20 while (!isdigit(c)) { 21 if (c == '-') { 22 f = -1; 23 } 24 read_char(c); 25 } 26 x = 0; 27 while (isdigit(c)) { 28 x = x * 10 + c - '0'; 29 read_char(c); 30 } 31 x *= f; 32 } 33 inline void flush() { 34 fwrite(obuf, 1, os - obuf, stdout); 35 os = obuf; 36 } 37 inline void print_char(char c) { 38 *os++ = c; 39 if (os == ot) { 40 flush(); 41 } 42 } 43 template <class T> 44 inline void print_int(T x) { 45 static char q[40]; 46 if (!x) { 47 print_char('0'); 48 } else { 49 if (x < 0) { 50 print_char('-'); 51 x = -x; 52 } 53 int top = 0; 54 while (x) { 55 q[top++] = x % 10 + '0'; 56 x /= 10; 57 } 58 while (top--) { 59 print_char(q[top]); 60 } 61 } 62 } 63 struct flusher_t { 64 inline ~flusher_t() { 65 flush(); 66 } 67 } flusher; 68 } 69 using io::read_char; 70 using io::read_int; 71 using io::print_char; 72 using io::print_int; 73 //Fast IO end 74 const int N = 200002; 75 int n, k, tot, dfc, C[N], dfn[N * 20], low[N * 20], dep[N], pa[18][N], id[18][N]; 76 vector<int> G[N], buck[N], H[N * 20]; 77 inline void add_edge(int u, int v) { 78 H[u].push_back(v); 79 } 80 inline int LCA(int u, int v) { 81 if (dep[u] < dep[v]) swap(u, v); 82 for (int i = 0; i < 18; i++) if ((dep[u] - dep[v]) >> i & 1) u = pa[i][u]; 83 if (u == v) return u; 84 for (int i = 17; ~i; i--) if (pa[i][u] != pa[i][v]) u = pa[i][u], v = pa[i][v]; 85 return pa[0][u]; 86 } 87 void dfs(int u, int lst, int depth) { 88 dfn[u] = ++dfc; 89 pa[0][u] = lst; 90 id[0][u] = ++tot; 91 add_edge(id[0][u], u); 92 if (lst) add_edge(id[0][u], lst); 93 dep[u] = depth; 94 for (int v : G[u]) if (v != lst) { 95 dfs(v, u, depth + 1); 96 } 97 } 98 inline void gao(int u, int v, int z) { 99 for (int i = 0; i < 18; i++) if ((dep[v] - dep[u]) >> i & 1) { 100 add_edge(z, id[i][v]); 101 v = pa[i][v]; 102 } 103 } 104 int stk[N * 20], tp, instk[N * 20], sw[N * 20], bel[N * 20], scc, deg[N * 20]; 105 void Tarjan(int u) { 106 dfn[u] = low[u] = ++dfc; 107 stk[++tp] = u; 108 instk[u] = 1; 109 for (int v : H[u]) { 110 if (!dfn[v]) { 111 Tarjan(v); 112 low[u] = min(low[u], low[v]); 113 } else if (instk[v]) { 114 low[u] = min(low[u], dfn[v]); 115 } 116 } 117 if (dfn[u] == low[u]) { 118 sw[++scc] = 0; 119 int w; 120 do { 121 w = stk[tp--]; 122 bel[w] = scc; 123 instk[w] = 0; 124 if (w > tot) sw[scc]++; 125 } while (w != u); 126 } 127 } 128 int main() { 129 read_int(n); 130 read_int(k); 131 for (int i = 1; i < n; i++) { 132 int u, v; 133 read_int(u); 134 read_int(v); 135 G[u].push_back(v); 136 G[v].push_back(u); 137 } 138 for (int i = 1; i <= n; i++) { 139 read_int(C[i]); 140 buck[C[i]].push_back(i); 141 } 142 tot = n; 143 dfc = 0; 144 dfs(1, 0, 0); 145 for (int i = 1; i < 18; i++) { 146 for (int u = 1; u <= n; u++) { 147 pa[i][u] = pa[i - 1][pa[i - 1][u]]; 148 id[i][u] = ++tot; 149 add_edge(id[i][u], id[i - 1][u]); 150 if (pa[i - 1][u]) add_edge(id[i][u], id[i - 1][pa[i - 1][u]]); 151 } 152 } 153 for (int i = 1; i <= n; i++) { 154 add_edge(i, tot + C[i]); 155 } 156 for (int i = 1; i <= k; i++) { 157 sort(buck[i].begin(), buck[i].end(), [](int u, int v) { 158 return dfn[u] < dfn[v]; 159 }); 160 tp = 0; 161 for (int u : buck[i]) { 162 if (!tp) { stk[++tp] = u; continue; } 163 int lca = LCA(u, stk[tp]); 164 while (dfn[lca] < dfn[stk[tp]]) { 165 if (dfn[lca] >= dfn[stk[tp - 1]]) { 166 gao(lca, stk[tp], i + tot); 167 if (stk[--tp] != lca) stk[++tp] = lca; 168 break; 169 } 170 gao(stk[tp - 1], stk[tp], i + tot); 171 tp--; 172 } 173 stk[++tp] = u; 174 } 175 while (tp > 1) gao(stk[tp - 1], stk[tp], i + tot), tp--; 176 } 177 memset(dfn, 0, sizeof(dfn)); 178 scc = 0; 179 for (int i = 1; i <= tot + k; i++) { 180 if (!dfn[i]) { 181 dfc = tp = 0; 182 Tarjan(i); 183 } 184 } 185 for (int i = 1; i <= tot + k; i++) { 186 for (int j : H[i]) { 187 if (bel[i] != bel[j]) { 188 deg[bel[i]]++; 189 } 190 } 191 } 192 int ans = 0x3f3f3f3f; 193 for (int i = 1; i <= scc; i++) { 194 if (!deg[i]) { 195 ans = min(ans, sw[i]); 196 } 197 } 198 ans--; 199 assert(ans < k && ans >= 0); 200 print_int(ans); 201 print_char(' '); 202 return 0; 203 }
LOJ3281. 「JOISC 2020 Day4」传奇团子师傅
题意
这是一道提交答案题。
你有若干个团子和竹签，团子被放在一个 $n$ 行 $m$ 列的格子里，每个格子恰好有一个团子。团子有三种颜色：P, W, G。
你每次会选择三个连续的团子，并把它们串在竹签上。这三个团子必须是沿着竖直方向或水平方向或对角方向连续的。一串团子是漂亮的当且仅当三个团子的颜色依次为 P-W-G 或 G-W-P。每个团子最多只能串在一根竹签上。你想要得到尽可能多串漂亮的团子。
一共有六个测试点，会给出评分参数，具体见 OJ。当你的答案中漂亮的团子数量 $geq Z$ 时，这个测试点就算满分。
题解
（这题的模拟退火的一些内容参考了神仙 PinkRabbit 在 CF 上的评论）
把所有可能的团子串都取出来，如果两个团子串不可能同时出现（即它们所用的团子有重复），那么就在它们之间连一条边。这样我们构建出一张图。
我们就是要找这张图的一个大小尽可能大的独立集。
考虑模拟退火。初始所有点都没选进独立集，每次随机一个不在独立集内的点 $u$，然后试图把它加进独立集。当然加的同时要从集合中去掉与它相邻的点。
就像常见的模拟退火一样，如果新的解优于旧的解或者以一定的概率接受一个较劣的解，那么就把新的解保留。
不过对于同一个温度，可能需要多随机几个 $u$。而且由于解的大小比较大，温度的变化率要非常非常接近 $1$，例如 $0.999999$。当然，温度的初始值不一定要那么大（毕竟你算一个新的解的时间就够长的了）。
然后跑模拟退火就行了，很快就可以把前 $4$ 个点过掉。然而我第 $5,6$ 个点都差一点点（把分数四舍五入就到 $100$ 了的那种），非常自闭。后来我又把代码魔改了一通，使得它能够在一个差一点点的解的基础上继续退火。后来换了几个种子终于把这两个点过掉了，而且答案正好是 $Z$。（并不知道神仙粉兔是如何退火出来更优的解的）
在跑退火的时候，有时我想要直接用 Ctrl-C 强制让它停下来，但这样就不会输出当前跑出的最优方案了。我的解决方法是定义一个 struct，并给它定义一个析构函数。这样在程序终止的时候，它会自动执行输出方案的部分。
代码
（这份代码是我在跑第 $5$ 个测试点的时候用的，它会读入一个较优的解，然后在这个解的基础上进行退火。仅供参考）
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1}; 4 const int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1}; 5 const int val[8] = {3, 1, 2, 0, 0, 2, 1, 3}; 6 const int V = 1000005; 7 int n, m, tot, id[505][505][4]; 8 char a[505][505]; 9 vector<int> G[V]; 10 inline void add_edge(int u, int v) { 11 G[u].push_back(v); 12 } 13 inline void Construct() { 14 /* 15 - 0 16 | 1 17 / 2 18 3 19 */ 20 tot = 0; 21 for (int i = 1; i <= n; i++) { 22 for (int j = 1; j <= m; j++) if (a[i][j] == 'W') { 23 if ((a[i][j - 1] == 'P' && a[i][j + 1] == 'G') || (a[i][j - 1] == 'G' && a[i][j + 1] == 'P')) { 24 id[i][j][0] = ++tot; 25 } 26 if ((a[i - 1][j] == 'P' && a[i + 1][j] == 'G') || (a[i - 1][j] == 'G' && a[i + 1][j] == 'P')) { 27 id[i][j][1] = ++tot; 28 } 29 if ((a[i + 1][j - 1] == 'P' && a[i - 1][j + 1] == 'G') || (a[i + 1][j - 1] == 'G' && a[i - 1][j + 1] == 'P')) { 30 id[i][j][2] = ++tot; 31 } 32 if ((a[i - 1][j - 1] == 'P' && a[i + 1][j + 1] == 'G') || (a[i - 1][j - 1] == 'G' && a[i + 1][j + 1] == 'P')) { 33 id[i][j][3] = ++tot; 34 } 35 for (int k = 0; k < 4; k++) { 36 for (int l = 0; l < 4; l++) if (k != l && id[i][j][k] && id[i][j][l]) { 37 add_edge(id[i][j][k], id[i][j][l]); 38 } 39 } 40 } 41 } 42 for (int i = 1; i <= n; i++) { 43 for (int j = 1; j <= m; j++) if (a[i][j] == 'W') { 44 if (id[i][j][0]) { 45 for (int k = 0; k < 8; k++) { 46 int x = i + dx[k], y = j - 1 + dy[k]; 47 if (x >= 1 && x <= n && y >= 1 && y <= m && (x != i || y != j) && id[x][y][val[k]]) { 48 add_edge(id[i][j][0], id[x][y][val[k]]); 49 } 50 } 51 for (int k = 0; k < 8; k++) { 52 int x = i + dx[k], y = j + 1 + dy[k]; 53 if (x >= 1 && x <= n && y >= 1 && y <= m && (x != i || y != j) && id[x][y][val[k]]) { 54 add_edge(id[i][j][0], id[x][y][val[k]]); 55 } 56 } 57 } 58 if (id[i][j][1]) { 59 for (int k = 0; k < 8; k++) { 60 int x = i - 1 + dx[k], y = j + dy[k]; 61 if (x >= 1 && x <= n && y >= 1 && y <= m && (x != i || y != j) && id[x][y][val[k]]) { 62 add_edge(id[i][j][1], id[x][y][val[k]]); 63 } 64 } 65 for (int k = 0; k < 8; k++) { 66 int x = i + 1 + dx[k], y = j + dy[k]; 67 if (x >= 1 && x <= n && y >= 1 && y <= m && (x != i || y != j) && id[x][y][val[k]]) { 68 add_edge(id[i][j][1], id[x][y][val[k]]); 69 } 70 } 71 } 72 if (id[i][j][2]) { 73 for (int k = 0; k < 8; k++) { 74 int x = i + 1 + dx[k], y = j - 1 + dy[k]; 75 if (x >= 1 && x <= n && y >= 1 && y <= m && (x != i || y != j) && id[x][y][val[k]]) { 76 add_edge(id[i][j][2], id[x][y][val[k]]); 77 } 78 } 79 for (int k = 0; k < 8; k++) { 80 int x = i - 1 + dx[k], y = j + 1 + dy[k]; 81 if (x >= 1 && x <= n && y >= 1 && y <= m && (x != i || y != j) && id[x][y][val[k]]) { 82 add_edge(id[i][j][2], id[x][y][val[k]]); 83 } 84 } 85 } 86 if (id[i][j][3]) { 87 for (int k = 0; k < 8; k++) { 88 int x = i - 1 + dx[k], y = j - 1 + dy[k]; 89 if (x >= 1 && x <= n && y >= 1 && y <= m && (x != i || y != j) && id[x][y][val[k]]) { 90 add_edge(id[i][j][3], id[x][y][val[k]]); 91 } 92 } 93 for (int k = 0; k < 8; k++) { 94 int x = i + 1 + dx[k], y = j + 1 + dy[k]; 95 if (x >= 1 && x <= n && y >= 1 && y <= m && (x != i || y != j) && id[x][y][val[k]]) { 96 add_edge(id[i][j][3], id[x][y][val[k]]); 97 } 98 } 99 } 100 } 101 } 102 } 103 //mt19937 gen(1145141); 104 mt19937 gen(666233555); 105 inline double Rand01() { 106 return (double)gen() / 4294967296; 107 } 108 int Sta[V], Ans[V]; 109 int Cnt, Anscnt; 110 int tr[V * 4]; 111 void build(int i, int l, int r) { 112 if (l == r) { 113 tr[i] = 1 - Sta[l]; 114 return; 115 } 116 int mid = (l + r) >> 1; 117 build(i << 1, l, mid); 118 build(i << 1 | 1, mid + 1, r); 119 tr[i] = tr[i << 1] + tr[i << 1 | 1]; 120 } 121 void modify(int i, int l, int r, int pos, int val) { 122 tr[i] += val; 123 if (l == r) return; 124 int mid = (l + r) >> 1; 125 if (pos <= mid) modify(i << 1, l, mid, pos, val); 126 else modify(i << 1 | 1, mid + 1, r, pos, val); 127 } 128 int query(int i, int l, int r, int pos) { 129 if (l == r) return l; 130 int mid = (l + r) >> 1; 131 if (tr[i << 1] >= pos) return query(i << 1, l, mid, pos); 132 else return query(i << 1 | 1, mid + 1, r, pos - tr[i << 1]); 133 } 134 int Bad[V]; 135 struct Ender_t { 136 inline ~Ender_t() { 137 fprintf(stderr, "%d ", Anscnt); 138 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i][j] == 'W') { 139 if (id[i][j][0] && Ans[id[i][j][0]]) a[i][j] = '-'; 140 if (id[i][j][1] && Ans[id[i][j][1]]) a[i][j] = '|'; 141 if (id[i][j][2] && Ans[id[i][j][2]]) a[i][j] = '/'; 142 if (id[i][j][3] && Ans[id[i][j][3]]) a[i][j] = '\'; 143 } 144 for (int i = 1; i <= n; i++) puts(a[i] + 1); 145 } 146 } Ender; 147 char b[505][505]; 148 int main() { 149 freopen("input_05.txt", "r", stdin); 150 freopen("tmp.txt", "w", stdout); 151 scanf("%d%d", &n, &m); 152 memset(a, 0, sizeof(a)); 153 for (int i = 1; i <= n; i++) { 154 scanf(" %s", a[i] + 1); 155 } 156 Construct(); 157 fprintf(stderr, "%d ", tot); 158 memset(Sta, 0, sizeof(Sta)); 159 memset(Ans, 0, sizeof(Ans)); 160 freopen("output_05.txt", "r", stdin); 161 for (int i = 1; i <= n; i++) scanf(" %s", b[i] + 1); 162 for (int i = 1; i <= n; i++) { 163 for (int j = 1; j <= m; j++) { 164 if (b[i][j] == '-') Sta[id[i][j][0]] = 1; 165 if (b[i][j] == '|') Sta[id[i][j][1]] = 1; 166 if (b[i][j] == '/') Sta[id[i][j][2]] = 1; 167 if (b[i][j] == '\') Sta[id[i][j][3]] = 1; 168 } 169 } 170 build(1, 1, tot); 171 memcpy(Ans + 1, Sta + 1, tot << 2); 172 Cnt = Anscnt = tot - tr[1]; 173 const int B = 48620; 174 while (Anscnt < B) { 175 fprintf(stderr, "--- Best %d Current %d ", Anscnt, Cnt); 176 Bad[Anscnt]++; 177 if (Bad[Anscnt] % 5 == 4) { 178 memcpy(Sta + 1, Ans + 1, tot << 2); 179 Cnt = Anscnt; 180 build(1, 1, tot); 181 } 182 double T = 1000; 183 while (T > 1e-6) { 184 int t = 5; 185 while (t--) { 186 int u = query(1, 1, tot, uniform_int_distribution<int>(1, tot - Cnt)(gen)); 187 int delta = 1; 188 for (int v : G[u]) if (Sta[v]) delta--; 189 int nCnt = Cnt + delta; 190 if (nCnt > Cnt || Rand01() < exp(-1.0 * (Cnt - nCnt) / T)) { 191 Sta[u] = 1; 192 modify(1, 1, tot, u, -1); 193 for (int v : G[u]) if (Sta[v]) Sta[v] = 0, modify(1, 1, tot, v, 1); 194 Cnt = nCnt; 195 if (Anscnt < Cnt) { 196 Anscnt = Cnt; 197 memcpy(Ans + 1, Sta + 1, tot << 2); 198 if (Anscnt >= B) break; 199 } 200 } 201 } 202 if (Anscnt >= B) break; 203 T *= 0.9999996; 204 } 205 } 206 return 0; 207 }
LOJ3282. 「JOISC 2020 Day4」治疗计划
题意
（这个题面很切合当下的时代背景（苦笑））
某城市有 $n$ 个人，分别住在位置 $1..n$。最近，某种病毒肆虐了这座城市，且这 $n$ 个人全部感染了这种病毒。
现在有 $m$ 种治疗方案，第 $i$ 种是：在第 $T_i$ 天的晚上，把区间 $[L_i, R_i]$ 内的人全部治疗好（如果本来就是健康的人就没有影响），治疗的代价是 $C_i$。（同一天可以进行多次治疗方案）
但是，这种病毒传染性很强。具体来说，如果在第 $i$ 天的早上，位置 $x$ 的人感染了病毒，那么在这天的中午，位置 $x-1$ 和 $x+1$ 就会被传染（如果对应位置不存在就不传染）。一个人可以多次感染。
所以，消灭这种病毒的唯一方法就是让这 $n$ 个人都是健康的。求达到这一目标的最小代价，如果无解输出 $-1$。
$1leq nleq 10^9, 1leq mleq 10^5, 1leq T_ileq 10^9$
题解
这题要的是最优解，我们首先观察出来一些性质：如果在某次治疗时，存在健康人的极长区间被这次治疗完全包含，那么这个健康人区间对应的治疗是无用的，可以去掉。
这个性质比较显然。它有一个也很显然的推论：最优解中，在某次治疗时，如果治疗区间内部存在健康人区间，那么这个区间要么会向左延伸到治疗区间以外，要么会向右延伸到治疗区间以外。
所以，当加入一个治疗方案时，它会把至多两个健康人区间合并在一起。
而我们可以发现，健康人区间的边界只会与某个治疗方案有关（左右边界所属的治疗方案可能不同）。我们按时间顺序扫过来，记录健康人区间的边界所属的治疗方案，就可以判断区间的合并了。我们的最终目标就是要在某个时刻让健康人区间的左右端点分别为 $1, n$。
进一步地，判断合并的区间其实不需要按照时间顺序。只要以任何顺序加入治疗方案，不断合并区间，最终合并出来 $[1,n]$ 即可。
所以我们甚至可以从左到右扫区间。那么这样我们考虑这样一个最短路（dp）建图。所有左端点为 $1$ 的治疗方案 $i$ 是起点，距离就是其代价 $C_i$。
从点 $i$ 到点 $j$ 有边，当且仅当：
- $T_j geq T_i$ 且 $R_i-T_j+T_i geq L_j-1$，或者
- $T_j < T_i$ 且 $L_j+T_i-T_j leq R_i+1$
边权就是 $C_j$。
跑完最短路后，对于所有右端点为 $n$ 的治疗方案，将他们的最短路取个 $min$ 就是答案了。
考虑优化，显然可以按 $T_i$ 的顺序建出两棵可持久化线段树，然后在可持久化线段树上连边、跑最短路即可。
时间复杂度 $O(mlog^2 m)$。
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int M = 100005; 4 int n, m, T[M], L[M], R[M], C[M], id[M]; 5 priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > que; 6 vector<int> v1, v2; 7 vector<pair<int, int> > G[M * 37]; 8 long long dist[M * 37]; 9 inline void add_edge(int u, int v, int w) { 10 G[u].emplace_back(v, w); 11 } 12 struct Node { 13 int lson, rson; 14 } tr[M * 18 * 2]; 15 int tot, root2[M], root1[M]; 16 void Ins(int &x, int y, int l, int r, int pos, int id) { 17 x = ++tot; 18 tr[x] = tr[y]; 19 if (y) add_edge(x + m, y + m, 0); 20 if (l == r) { 21 add_edge(x + m, id, C[id]); 22 return; 23 } 24 int mid = (l + r) >> 1; 25 if (pos <= mid) Ins(tr[x].lson, tr[y].lson, l, mid, pos, id), add_edge(x + m, tr[x].lson + m, 0); 26 else Ins(tr[x].rson, tr[y].rson, mid + 1, r, pos, id), add_edge(x + m, tr[x].rson + m, 0); 27 } 28 void Add(int x, int l, int r, int lf, int rg, int id) { 29 if (!x) return; 30 if (lf <= l && r <= rg) { 31 add_edge(id, x + m, 0); 32 return; 33 } 34 int mid = (l + r) >> 1; 35 if (lf <= mid) Add(tr[x].lson, l, mid, lf, rg, id); 36 if (rg > mid) Add(tr[x].rson, mid + 1, r, lf, rg, id); 37 } 38 int main() { 39 scanf("%d%d", &n, &m); 40 for (int i = 1; i <= m; i++) { 41 scanf("%d%d%d%d", &T[i], &L[i], &R[i], &C[i]); 42 v1.push_back(L[i] + T[i] - 1); 43 v2.push_back(L[i] - T[i] - 1); 44 id[i] = i; 45 } 46 sort(id + 1, id + 1 + m, [](int i, int j) { 47 return T[i] < T[j]; 48 }); 49 sort(v1.begin(), v1.end()); 50 v1.resize(unique(v1.begin(), v1.end()) - v1.begin()); 51 sort(v2.begin(), v2.end()); 52 v2.resize(unique(v2.begin(), v2.end()) - v2.begin()); 53 root2[0] = 0; 54 for (int i = 1; i <= m; i++) { 55 int j = id[i]; 56 int p = lower_bound(v2.begin(), v2.end(), L[j] - T[j] - 1) - v2.begin() + 1; 57 Ins(root2[i], root2[i - 1], 1, m, p, j); 58 } 59 root1[m + 1] = 0; 60 for (int i = m; i; i--) { 61 int j = id[i]; 62 int p = lower_bound(v1.begin(), v1.end(), L[j] + T[j] - 1) - v1.begin() + 1; 63 Ins(root1[i], root1[i + 1], 1, m, p, j); 64 } 65 for (int i = 1, k = 1; i <= m; i++) { 66 while (k <= m && T[id[i]] >= T[id[k]]) k++; 67 int j = id[i]; 68 int p = upper_bound(v2.begin(), v2.end(), R[j] - T[j]) - v2.begin(); 69 if (1 <= p) Add(root2[k - 1], 1, m, 1, p, j); 70 } 71 for (int i = m, k = m; i; i--) { 72 while (k > 0 && T[id[i]] <= T[id[k]]) k--; 73 int j = id[i]; 74 int p = upper_bound(v1.begin(), v1.end(), R[j] + T[j]) - v1.begin(); 75 if (1 <= p) Add(root1[k + 1], 1, m, 1, p, j); 76 } 77 memset(dist, 0x3f, sizeof(dist)); 78 for (int i = 1; i <= m; i++) { 79 if (L[i] == 1) { 80 dist[i] = C[i]; 81 que.push(make_pair(dist[i], i)); 82 } 83 } 84 while (!que.empty()) { 85 auto P = que.top(); que.pop(); 86 int u = P.second; 87 if (dist[u] != P.first) continue; 88 for (auto &e : G[u]) { 89 int v = e.first; 90 if (dist[v] > dist[u] + e.second) { 91 dist[v] = dist[u] + e.second; 92 que.push(make_pair(dist[v], v)); 93 } 94 } 95 } 96 long long ans = 1ll << 55; 97 for (int i = 1; i <= m; i++) { 98 if (R[i] == n) ans = min(ans, dist[i]); 99 } 100 if (ans >= (1ll << 55)) ans = -1; 101 printf("%lld ", ans); 102 return 0; 103 }