P6619 [省选联考 2020 A/B 卷] 冰火战士
树状数组倍增板子。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 5;
#define lowbit(i) ((i) & (-(i)))
int a[2][N], n, _x[N], cnt, sum[2];
void add(int a[], int x, int k){for(int i = x; i <= cnt; i += lowbit(i))a[i] += k;
}
int query(int a[], int x){int sum = 0;for(int i = x; i; i -= lowbit(i)) sum += a[i];return sum;
}
struct node{int op, idx, x, y;
}Op[N];
int main(){cin.tie(nullptr)->sync_with_stdio(0);cin >> n;for(int i = 1; i <= n; ++i){cin >> Op[i].op >> Op[i].idx;if(Op[i].op == 1){cin >> Op[i].x >> Op[i].y;_x[++cnt] = Op[i].x;}else{Op[i].op = -1;int idx = Op[i].idx;Op[i].x = Op[idx].x;Op[i].y = Op[idx].y;Op[i].idx = Op[idx].idx;}}sort(_x + 1, _x + 1 + cnt);cnt = unique(_x + 1, _x + 1 + cnt) - _x - 1;for(int i = 1; i <= n; ++i){Op[i].x = lower_bound(_x + 1, _x + 1 + cnt, Op[i].x) - _x;int x = Op[i].x, y = Op[i].y, op = Op[i].op, idx = Op[i].idx;add(a[idx], x + idx, op * y);sum[idx] += op * y;int nw0 = 0, nw1 = sum[1], p = 0;for(int j = 20; j >= 0; --j){int nxtp = p + (1 << j);if(nxtp <= cnt && nw0 + a[0][nxtp] <= nw1 - a[1][nxtp]){nw0 += a[0][nxtp], nw1 -= a[1][nxtp];p = nxtp;}}int ans1 = nw0, ans2 = 0, p2 = 0;if(p < cnt){ans2 = sum[1] - query(a[1], p + 1);int nw = sum[1];for(int j = 20; j >= 0; --j){int nxtp = p2 + (1 << j);if(nxtp <= cnt && nw - a[1][nxtp] >= ans2){nw -= a[1][nxtp], p2 = nxtp;}}}if(max(ans1, ans2) == 0) cout << "Peace\n";else{if(ans1 > ans2) cout << _x[p] << ' ' << 2 * ans1 << '\n';else cout << _x[p2] << ' ' << 2 * ans2 << '\n';}}return 0;
}
P4768 [NOI2018] 归程
Kruskal 重构树板子，注意求的是最大最小瓶颈路还是最小最大瓶颈路（可能这么叫？
Code
using namespace std;
typedef pair<int, int> pii;
const int N = 4e5 + 5;
struct edge{int u, v, w, f, pre;
}e[N * 2];
int n, m, head[N], fa[N], cnt, dis[N], val[N], mn[N], st[N][21];
vector<int> g[N];
void adde(int u, int v, int w, int f){e[++cnt] = {u, v, w, f, head[u]};head[u] = cnt;
}
void dij(){priority_queue<pii, vector<pii>, greater<pii> > q;memset(dis, 0x3f, sizeof(dis));dis[1] = 0;q.emplace(0, 1);while(!q.empty()){auto [dist, u] = q.top();q.pop();if(dist > dis[u]) continue;for(int k = head[u]; k; k = e[k].pre){int v = e[k].v, w = e[k].w;if(dist + w < dis[v]){dis[v] = dist + w;q.emplace(dis[v], v);}}}
}
int getf(int u){ return u == fa[u] ? u : fa[u] = getf(fa[u]); }
void dfs(int u){mn[u] = dis[u];for(int i = 1; i <= 19; ++i) st[u][i] = st[st[u][i - 1]][i - 1];for(int v : g[u]){st[v][0] = u;dfs(v);mn[u] = min(mn[v], mn[u]);}
}
int main(){cin.tie(nullptr)->sync_with_stdio(0);int T;cin >> T;while(T--){memset(head, 0, sizeof(head));memset(g, 0, sizeof(g));memset(mn, 0x3f, sizeof(mn));cnt = 0;cin >> n >> m;for(int i = 1; i <= m; ++i){int u, v, w, f;cin >> u >> v >> w >> f;adde(u, v, w, f), adde(v, u, w, f);}dij();// for(int i = 1; i <= n; ++i) cout << dis[i] << '\n';for(int i = 1; i <= 2 * n; ++i) fa[i] = i;sort(e + 1, e + 1 + cnt, [](edge x, edge y){return x.f > y.f;});int tot = n;for(int i = 1; i <= cnt; ++i){int u = e[i].u, v = e[i].v, f = e[i].f;int fu = getf(u), fv = getf(v);if(fu != fv){fa[fu] = fa[fv] = ++tot;g[tot].emplace_back(fu);g[tot].emplace_back(fv);val[tot] = f;}if(tot - n == n - 1) break;}st[tot][0] = 0;dfs(tot);int lst = 0, q, k, s;cin >> q >> k >> s;while(q--){int v, p;cin >> v >> p;v = (v + lst * k - 1) % n + 1;p = (p + lst * k) % (s + 1);for(int j = 19; j >= 0; --j){if(val[st[v][j]] > p) v = st[v][j];}cout << (lst = mn[v]) << '\n';}}return 0;
}
P9870 [NOIP2023] 双序列拓展
dp 很 trival，然后变成了一个网格图上有障碍点查询联通性的问题。
主要的思想就是总是考虑限制最强的地方，神来之笔，把 \(y_j\) 套上一个 \(\min\) 之后居然就有单调性了，然后就可以双指针做。
感觉第二篇题解是更自然的思路，但写的时候看的是第一篇题解（好像就是把双指针倒过来写了）。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
typedef array<int, N> arr;
arr a, b, pamn, pbmn, pamx, pbmx, samn, samx, sbmn, sbmx, ta, tb;
bool check1(const arr&a, const arr &b, int x, int y){if(x == 1 || y == 1) return 1;if(a[pamn[x - 1]] < b[pbmn[y - 1]]) return check1(a, b, pamn[x - 1], y);else if(a[pamx[x - 1]] < b[pbmx[y - 1]]) return check1(a, b, x, pbmx[y - 1]);return 0;
}
bool check2(const arr&a, const arr &b, int x, int y, int enx, int eny){if(x == enx || y == eny) return 1;if(a[samn[x + 1]] < b[sbmn[y + 1]]) return check2(a, b, samn[x + 1], y, enx, eny);else if(a[samx[x + 1]] < b[sbmx[y + 1]]) return check2(a, b, x, sbmx[y + 1], enx, eny);return 0;
}
bool solve(const arr &a, const arr &b, int n, int m){auto get = [](const arr &x, int nw, int i, int fl){if(x[nw] * fl > x[i] * fl) return i;return nw;};pamn[1] = pamx[1] = pbmn[1] = pbmx[1] = 1;for(int i = 2; i <= n; ++i) pamn[i] = get(a, pamn[i - 1], i, 1), pamx[i] = get(a, pamx[i - 1], i, -1);for(int i = 2; i <= m; ++i) pbmn[i] = get(b, pbmn[i - 1], i, 1), pbmx[i] = get(b, pbmx[i - 1], i, -1);samn[n] = samx[n] = n, sbmn[m] = sbmx[m] = m;for(int i = n - 1; i >= 1; --i) samn[i] = get(a, samn[i + 1], i, 1), samx[i] = get(a, samx[i + 1], i, -1);for(int i = m - 1; i >= 1; --i) sbmn[i] = get(b, sbmn[i + 1], i, 1), sbmx[i] = get(b, sbmx[i + 1], i, -1);// for(int i = 1; i <= n; ++i) cout << pamn[i] << ' ' << samn[i] << ' ' << pamx[i] << ' ' << samx[i] << '\n';// for(int i = 1; i <= m; ++i) cout << pbmn[i] << ' ' << sbmn[i] << ' ' << pbmx[i] << ' ' << sbmx[i] << '\n';if(a[pamx[n]] >= b[pbmx[m]] || a[pamn[n]] >= b[pbmn[m]]) return 0;return check1(a, b, pamn[n], pbmx[m]) && check2(a, b, pamn[n], pbmx[m], n, m);
}
int main(){cin.tie(nullptr)->sync_with_stdio(0);int c, q, n, m;cin >> c >> n >> m >> q;for(int i = 1; i <= n; ++i) cin >> a[i];for(int i = 1; i <= m; ++i) cin >> b[i];cout << (solve(a, b, n, m) || solve(b, a, m, n) ? '1' : '0');while(q--){int kx, ky;cin >> kx >> ky;ta = a, tb = b;while(kx--){int p, v; cin >> p >> v;ta[p] = v;}while(ky--){int p, v; cin >> p >> v;tb[p] = v;}// for(int i = 1; i <= n; ++i) cout << ta[i] << ' ';// for(int j = 1; j <= m; ++j) cout << tb[j] << ' ';// cout << '\n';cout << (solve(ta, tb, n, m) || solve(tb, ta, m, n) ? '1' : '0');}return 0;
}
P7737 [NOI2021] 庆典
挺综合的一道题。
一开始看到这个 "对于三座城市 \(x\)，\(y\)，\(z\)，若 \(x\Rightarrow z\) 且 \(y\Rightarrow z\)，那么有 \(x\Rightarrow y\) 或 \(y\Rightarrow x\)" 性质的时候很疑惑，作用是在缩成 DAG 之后还可以进一步缩成树，注意下。
树上拓扑序就好处理多了，限制可以轻松地表示为在不在 \(u\) 的子树内。
考虑询问，发现暴力每次都跑一遍 dfs 求可不可达很亏，实际上只需要用建虚树的办法把关键点找出来建图跑就行，这样跑一次就是 \(O(k)\) 的了。
建虚树本身就是很有用的过程。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int n, m, q, k;
vector<int> g[N], e[N], tmp[N];
int dfn[N], low[N], scc[N], cnt, tsp, st[N], tp, f[N][21], lg[N], siz[N], a[N], r, dis[N];
bitset<N> in, vis, vise, bk;
struct edge{int u, v, w, pre;
}s[N], _s[N];
int sh[N], tot, _sh[N], _tot;
struct node{int u, v;
}add[5];
void adde(int u, int v, int w){s[++tot] = {u, v, w, sh[u]};sh[u] = tot;_s[++_tot] = {v, u, w, _sh[v]};_sh[v] = _tot;vise[tot] = 0;
}void tarjan(int u){dfn[u] = low[u] = ++tsp;in[st[++tp] = u] = 1;for(int v : g[u]){if(!dfn[v]){tarjan(v);low[u] = min(low[u], low[v]);}else if(in[v]) low[u] = min(low[u], dfn[v]);}if(low[u] == dfn[u]){++cnt;while(1){int x = st[tp];in[x] = 0, scc[x] = cnt, siz[cnt]++;--tp;if(x == u) break; }}
}
void dfs(int u, int fa){if(in[u]) return;in[u] = 1;if(fa) e[fa].emplace_back(u);for(int v : tmp[u]) dfs(v, u);
}int get(int u, int v){return (dfn[u] < dfn[v] ? u : v);
}
void init(int u, int fa){dis[u] = dis[fa] + siz[u];f[dfn[u] = ++tsp][0] = fa;for(int v : e[u]) init(v, u);
}
int Lca(int u, int v){if(u == v) return u;if(dfn[u] > dfn[v]) swap(u, v);u = dfn[u] + 1, v = dfn[v];int d = lg[v - u + 1];return get(f[u][d], f[v - (1 << d) + 1][d]);
}void build(){sort(a + 1, a + 1 + r, [](int x, int y){return dfn[x] < dfn[y];});r = unique(a + 1, a + 1 + r) - a - 1;_tot = tot = tp = 0;st[++tp] = cnt;sh[cnt] = _sh[cnt] = 0;auto len = [](int x, int y){ return dis[f[dfn[y]][0]] - dis[x]; };for(int i = 1; i <= r; ++i){if(a[i] == cnt) continue;int l = Lca(a[i], st[tp]);if(l != st[tp]){while(dfn[l] < dfn[st[tp - 1]]){adde(st[tp - 1], st[tp], len(st[tp - 1], st[tp]));--tp;}if(l != st[tp - 1]) sh[l] = _sh[l] = 0, adde(l, st[tp], len(l, st[tp])), st[tp] = l;else adde(st[tp - 1], st[tp], len(st[tp - 1], st[tp])), --tp;}sh[a[i]] = _sh[a[i]] = 0;st[++tp] = a[i];}for(int i = 1; i < tp; ++i) adde(st[i], st[i + 1], len(st[i], st[i + 1]));
}
void clear(int u){vis[u] = bk[u] = 0;for(int k = sh[u]; k; k = s[k].pre){clear(s[k].v);}
}
int ans = 0;
void get(int u){if(vis[u]) return;vis[u] = 1;for(int k = sh[u]; k; k = s[k].pre) vise[k] = 1, get(s[k].v);
}
void rev(int u){if(bk[u]) return;bk[u] = 1;if(vis[u]) ans += siz[u];for(int k = _sh[u]; k; k = _s[k].pre){if(vise[k]) ans += _s[k].w;rev(_s[k].v);}
}
int main(){cin.tie(nullptr)->sync_with_stdio(0);cin >> n >> m >> q >> k;for(int i = 0; (1 << i) <= n; ++i) lg[(1 << i)] = i;for(int i = 1; i <= m; ++i){int u, v;cin >> u >> v;g[u].emplace_back(v);}for(int i = 1; i <= n; ++i){if(!lg[i]) lg[i] = lg[i - 1];if(!dfn[i]) tarjan(i);}in.reset();for(int i = 1; i <= n; ++i){for(int v : g[i]){if(scc[i] != scc[v]) tmp[scc[i]].emplace_back(scc[v]);}}for(int i = 1; i <= cnt; ++i) sort(tmp[i].begin(), tmp[i].end(), greater<int>());dfs(cnt, 0);memset(dfn, 0, sizeof(dfn));tsp = 0;init(cnt, 0);for(int j = 1; (1 << j) <= cnt; ++j){for(int i = 1; i + (1 << j) - 1 <= cnt; ++i){f[i][j] = get(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}}while(q--){int s, t;cin >> s >> t;r = 0;a[++r] = scc[s], a[++r] = scc[t];for(int i = 1; i <= k; ++i){int u, v; cin >> u >> v;u = scc[u], v = scc[v];add[i] = {u, v};a[++r] = u, a[++r] = v;}build();clear(cnt);for(int i = 1; i <= k; ++i){if(add[i].u != add[i].v) adde(add[i].u, add[i].v, 0);}ans = 0;get(scc[s]);rev(scc[t]);cout << ans << '\n';}return 0;
}