做题合集
3月
3.18
QOJ - 3047 Wind of Change
给你两棵 \(n\) 个点的树 \(T_1,T_2\)，边带权，要求对每个结点 \(u\) 求出 \(\min\limits_{v \ne u}\left(dist_1(u,v)+dist_2(u,v)\right)\)，其中 \(dist_1(u,v)\) 和 \(dist_2(u,v)\) 分别表示在两棵树上 \(u,v\) 之间的距离。
\(2 \le n \le 2.5 \times 10^5\)。
胡了一个点分治+虚树上dp，还是比较好想的。就是在一棵树上点分治，每次分治考虑当前分出的一堆点，它们中两个点的距离和就是到分治中心的距离和加上在第二棵树上的距离和，再把第二棵树上的距离和拆成深度和加上二倍的lca深度。
然后把当前分治出的每个点的点权设为其在第一棵树上到分治中心的距离加上在第二棵树上的深度，还没有确定的就是在第二棵树上的lca深度了。
这个玩意在第二棵树里建出这些点的虚树然后预处理一下做个dp就行，时间复杂度是 \(\mathcal{O}(n \log^2 n)\) 的。
std是对两个树都点分治，然后枚举其中的一个点，枚举它和另外一个点在两个点分树上的lca然后做，也是两只 \(\log\)。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 2.5e5 + 10;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
struct Tree;
Tree *Treea, *Treeb;
struct Tree {
int n; long long ans[N];
vector<pair<int, int>> G[N];
inline void input(int _n) {
n = _n;
for(int i = 1; i <= n; i ++)
ans[i] = INF;
for(int i = 1; i < n; i ++) {
int a, b, c; cin >> a >> b >> c;
G[a].push_back({b, c}), G[b].push_back({a, c});
}
}
int fa[N], dep[N], init_siz[N], son[N], top[N], dfn[N], dfs_clock;
long long D[N];
void init_dfs(int u, int f) {
fa[u] = f, dep[u] = dep[f] + 1, init_siz[u] = 1, son[u] = 0;
for(auto pr : G[u]) {
int v = pr.first;
if(v == f) continue;
D[v] = D[u] + pr.second, init_dfs(v, u);
init_siz[u] += init_siz[v];
if(init_siz[v] > init_siz[son[u]]) son[u] = v;
}
}
void init_hld(int u, int topf) {
top[u] = topf, dfn[u] = ++dfs_clock;
if(!son[u]) return;
init_hld(son[u], topf);
for(auto pr : G[u]) {
int v = pr.first;
if(v == son[u] || v == fa[u]) continue;
init_hld(v, v);
}
}
inline void init() {init_dfs(1, 0), init_hld(1, 1); }
inline int lca(int a, int b) {
while(top[a] != top[b]) {
if(dep[top[a]] < dep[top[b]]) swap(a, b);
a = fa[top[a]];
}
return dep[a] < dep[b] ? a : b;
}
inline long long dist(int a, int b) {return D[a] + D[b] - 2 * D[lca(a, b)]; }
// 虚树上dp
vector<int> vG[N];
long long g[N], ming[N];
void vTree_pre_dfs(int u) {
ming[u] = g[u];
for(auto v : vG[u]) {
vTree_pre_dfs(v);
ming[u] = min(ming[u], ming[v]);
}
}
void vTree_dfs(int u, long long val) {
pair<long long, long long> mn = {INF, INF};
for(auto v : vG[u]) {
if(ming[v] < mn.first) mn.second = mn.first, mn.first = ming[v];
else if(ming[v] < mn.second) mn.second = ming[v];
}
ans[u] = min(ans[u], min(val, mn.first - 2 * D[u]) + g[u]);
if(g[u] < mn.first) mn.second = mn.first, mn.first = g[u];
else if(g[u] < mn.second) mn.second = g[u];
for(auto v : vG[u]) {
if(ming[v] == mn.first) vTree_dfs(v, min(val, mn.second - 2 * D[u]));
else vTree_dfs(v, min(val, mn.first - 2 * D[u]));
}
}
void calc(vector<pair<int, long long>> &vec) {
for(int i = 0; i < vec.size(); i ++)
vec[i].second += D[vec[i].first];
// 建虚树
sort(vec.begin(), vec.end(), [&](pair<int, long long> x, pair<int, long long> y) {
return dfn[x.first] < dfn[y.first];
});
set<int> used;
for(auto pr : vec) used.insert(pr.first);
int tot = vec.size();
for(int i = 1; i < tot; i ++) {
int L = lca(vec[i - 1].first, vec[i].first);
if(used.count(L)) continue;
used.insert(L), vec.push_back({L, INF});
}
sort(vec.begin(), vec.end(), [&](pair<int, long long> x, pair<int, long long> y) {
return dfn[x.first] < dfn[y.first];
});
for(int i = 0; i < vec.size(); i ++)
g[vec[i].first] = vec[i].second;
for(int i = 1; i < vec.size(); i ++)
vG[lca(vec[i - 1].first, vec[i].first)].emplace_back(vec[i].first);
vTree_pre_dfs(vec[0].first), vTree_dfs(vec[0].first, INF);
for(int i = 0; i < vec.size(); i ++)
vG[vec[i].first].clear(), g[vec[i].first] = 0;
}
// 点分治
bool vis[N]; int siz[N], mx_siz[N], SIZE, root;
void find_root_dfs(int u, int fa) {
siz[u] = 1, mx_siz[u] = 0;
for(auto pr : G[u]) { int v = pr.first;
if(v == fa || vis[v]) continue;
find_root_dfs(v, u), siz[u] += siz[v];
mx_siz[u] = max(mx_siz[u], siz[v]);
}
mx_siz[u] = max(mx_siz[u], SIZE - siz[u]);
if(root == -1 || mx_siz[root] > mx_siz[u]) root = u;
}
inline int find_root(int x, int _SIZE) {
SIZE = _SIZE, root = -1, find_root_dfs(x, 0);
return root;
}
void get_siz_dfs(int u, int fa) {
SIZE ++;
for(auto pr : G[u])
if(!vis[pr.first] && pr.first != fa) get_siz_dfs(pr.first, u);
}
inline int get_siz(int x) {
SIZE = 0;
get_siz_dfs(x, -1);
return SIZE;
}
void vec_dfs(int u, int fa, vector<pair<int, long long>> &vec) {
vec.push_back({u, 0});
for(auto pr : G[u]) {
if(vis[pr.first] || pr.first == fa) continue;
vec_dfs(pr.first, u, vec);
}
}
void solve(int u) {
// cerr << u << ' ';
vis[u] = true;
vector<pair<int, long long>> vec;
vec.push_back({u, 0});
for(auto pr : G[u]) {
int v = pr.first; if(vis[v]) continue;
vec_dfs(v, u, vec);
}
for(int i = 0; i < vec.size(); i ++)
vec[i].second = dist(u, vec[i].first);
Treeb->calc(vec);
for(auto pr : G[u]) { int v = pr.first;
if(vis[v]) continue;
solve(find_root(v, get_siz(v)));
}
}
} T[2];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n; cin >> n;
T[0].input(n), T[1].input(n);
T[0].init(), T[1].init();
Treea = &T[0], Treeb = &T[1];
T[0].solve(T[0].find_root(1, n));
for(int i = 1; i <= n; i ++)
cout << T[1].ans[i] << '\n';
return 0;
}
【AGC017C】 Snuke and Spells
\(N\) 个球排在一起，每个球上有一个数 \(A_i\)。接下来会进行若干轮删除。设现在还有 \(k\) 个球，则 \(A_i=k\) 的球会被删除。
最终可能球不会被删完，你需要求出最少修改几个球上的数后可以让球全部被删完。
同时还有 \(M\) 次修改，每次修改第 \(X_i\) 个球的数为 \(Y_i\)，你需要求出每次修改后上述问题的答案。
\(1 \le N,M \le 2 \times 10^5\)，\(1 \le A_i,X_i,Y_i \le N\)
有点神秘的。
开个桶记一下每个值有多少个，设成 \(c_x\)，然后将它看作是在数轴上的 \(x\) 处向下挂了一个长 \(c_x\) 的绳子，最后将所有绳子向左拉到水平，合法当且仅当恰好覆盖了 \([1,n]\)。
所以每次的答案显然就是没有被覆盖的位置数量了，单点修改只会有 \(\mathcal{O}(1)\) 个位置的被覆盖状态会变化，随便做一下就行，时间复杂度 \(\mathcal{O}(n+m)\)。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, A[N], c[N], global_val[2 * N];
int *val = global_val + N;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++) {
cin >> A[i];
c[A[i]] ++;
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= c[i]; j ++)
val[i - j] ++;
}
int ans = 0;
for(int i = 0; i < n; i ++)
ans += !val[i];
while(m --) {
int x, y; cin >> x >> y;
val[A[x] - c[A[x]]] --;
ans += (A[x] - c[A[x]] >= 0) && !(val[A[x] - c[A[x]]]);
c[A[x]] --;
ans -= (y - c[y] - 1 >= 0) && (!val[y - c[y] - 1]);
c[y] ++, val[y - c[y]] ++;
A[x] = y;
cout << ans << '\n';
}
return 0;
}
有个强化版是 洛谷P5324 【BJOI2019】 删数，加了一个全局加减 \(1\) 的操作，套个线段树就行，懒得写。
梦熊3.17模拟T1
有一张 \(n\) 个点 \(m\) 条无向边的图，保证没有自环和重边。将每条无向边拆成两条有向边，然后将这 \(n\) 个点重新组成若干个环（环是有向的，不能是自环，但可以是两个点的环），对于每个点，如果它连出的边和连向它的边都是原图中的边，就会有一个 \(+1\) 的贡献，如果两个边都不是原图中的边，就会有一个 \(-1\) 的贡献，否则没有贡献。
问最大的贡献和，\(2 \le n \le 5000\)，\(0 \le m \le 5000\)。
哎呦怎么还有人这题都80/100啊/ll
简单转化一下就会发现，将每个点的贡献强制变为 \(-1\)，之后每一条在原图出现的边都会有一个 \(+2\) 的贡献就可以把贡献塞到边上了。
然后将每个点拆成两个点，左部点向右部点连边跑一个最大匹配就结束了。但是可能这样的匹配最终会出现一个孤立点，不合法。
最终匹配出的图一定是一堆环+一堆链+一堆孤立点，匹配不合法当且仅当匹配出了一堆环+一个孤立点，否则总是可以将孤立点和链连起来的。
实际上就是看一下这个点在原图中有没有边，假如有边，总是可以更改一下匹配方案让这个孤立点得到一个匹配，否则就只能强行把它塞到一个环里了，答案会再减 \(2\)。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, INF = 0x3f3f3f3f;
int n, m;
struct Dinic {
struct edge {
int from, to, cap, flow;
edge(int u, int v, int c, int f): from(u), to(v), cap(c), flow(f) {}
};
vector<edge> edges; vector<int> G[N];
bool link[N][2];
inline void clear(int n) {
edges.clear();
for(int i = 0; i <= n; i ++)
G[i].clear(), link[i][0] = link[i][1] = false;
}
int S, T;
inline void AddEdge(int u, int v, int c) {
static int m;
edges.emplace_back(edge(u, v, c, 0)), edges.emplace_back(edge(v, u, 0, 0));
m = edges.size(); G[u].emplace_back(m - 2), G[v].emplace_back(m - 1);
}
int dist[N], cur[N];
inline bool BFS() {
memset(dist, 0, sizeof dist);
dist[S] = 1; queue<int> Q; Q.push(S);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(auto i : G[u])
if(edges[i].flow != edges[i].cap && !dist[edges[i].to])
dist[edges[i].to] = dist[u] + 1, Q.push(edges[i].to);
}
return dist[T];
}
int dfs(int u, int F) {
if(u == T || !F) return F;
int flow = 0;
for(int &i = cur[u]; i < G[u].size(); i ++) {
edge &e = edges[G[u][i]];
if(dist[e.to] != dist[e.from] + 1 || e.flow == e.cap) continue;
int f = dfs(e.to, min(F, e.cap - e.flow));
flow += f, F -= f, e.flow += f, edges[G[u][i] ^ 1].flow -= f;
if(!F) break;
}
return flow;
}
inline int MaxFlow(int S, int T) {
this->S = S, this->T = T;
int ans = 0;
while(BFS()) {
memset(cur, 0, sizeof cur);
ans += dfs(S, INF);
}
return ans;
}
inline int check(int n) {
for(auto &e : edges) {
if(e.flow != 1) continue;
if(e.from == S) link[e.to][0] = true;
else if(e.to == T) link[e.from - n][1] = true;
}
int c[2] = {0, 0}; int x = 0;
for(int i = 1; i <= n; i ++) {
if(!link[i][0] && !link[i][1]) c[1] ++, x = i;
else if(!link[i][0] || !link[i][1]) c[0] ++;
}
if(!(c[1] == 1 && c[0] == 0)) return 0;
if(G[x].size() == 1) return 1;
else return 0;
}
} solver;
inline void solve() {
cin >> n >> m;
int S = 0, T = n + n + 1;
for(int i = 1; i <= n; i ++)
solver.AddEdge(S, i, 1), solver.AddEdge(i + n, T, 1);
for(int i = 1; i <= m; i ++) {
int a, b; cin >> a >> b;
solver.AddEdge(a, b + n, 1), solver.AddEdge(b, a + n, 1);
}
int ans = 2 * solver.MaxFlow(S, T) - n;
ans -= solver.check(n) * 2;
cout << ans << '\n';
solver.clear(2 * n + 1);
}
int main() {
freopen("aka.in", "r", stdin);
freopen("aka.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0);
int id, T; cin >> id >> T;
while(T --) solve();
return 0;
}
剩下两个题明天再写吧.
3.19
【北大集训 2021】 出题高手
唐氏题。因为数据是随机的，所以最后答案区间的长度不会很大，只需要考虑所有 \(\le 2000\) 的长度即可，实现时从左到右扫描线枚举询问的右端点即可。
这样会在 \(n=5\times 10^5\)，\(m=1\) 的点挂掉，这时候只考虑 \(\le 500\) 的长度即可。
为了平衡复杂度，用 \(\mathcal{O}(1)\) 单点取 \(\max\)，\(\mathcal{O}(\sqrt{n})\) 求区间 \(\max\) 的分块维护，时间复杂度 \(\mathcal{O}(n\sqrt{n})\)。
不是很喜欢这种题。
code
#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
struct frac {
long long a, b; // \frac{a}{b}
frac(long long x = 0, long long y = 1): a(x), b(y) {}
};
bool operator < (const frac &lhs, const frac &rhs) {
return (__int128)lhs.a * rhs.b < (__int128)rhs.a * lhs.b;
}
const int N = 5e5 + 10, M = 3e5 + 10;
int n, m, A[N], B_SIZE, id[N], L[N], R[N];
vector<pair<int, int>> Q[N];
frac ans[M];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n; B_SIZE = max((int)sqrt(n), 1);
for(int l = 1, r, ID = 1; l <= n; l = r + 1, ID ++) {
r = min(n, l + B_SIZE - 1);
for(int i = l; i <= r; i ++)
id[i] = ID, L[i] = l, R[i] = r;
}
for(int i = 1; i <= n; i ++)
cin >> A[i];
cin >> m;
for(int i = 1; i <= m; i ++) {
int l, r; cin >> l >> r;
Q[r].push_back({l, i});
}
int D;
if(n <= 100000) D = 2000;
else D = 500;
static frac C[N], BLOCK_C[N];
for(int r = 1; r <= n; r ++) {
long long sum = 0;
for(int l = r; l >= max(1, r - D + 1); l --) {
sum += A[l];
if(C[l] < frac(sum * sum, r - l + 1)) {
C[l] = frac(sum * sum, r - l + 1);
BLOCK_C[id[l]] = max(BLOCK_C[id[l]], C[l]);
}
}
for(auto pr : Q[r]) {
int l = pr.first, q_id = pr.second;
if(id[l] == id[r]) {
for(int i = l; i <= r; i ++)
ans[q_id] = max(ans[q_id], C[i]);
} else {
for(int i = l; i <= R[l]; i ++)
ans[q_id] = max(ans[q_id], C[i]);
for(int i = id[l] + 1; i < id[r]; i ++)
ans[q_id] = max(ans[q_id], BLOCK_C[i]);
for(int i = L[r]; i <= r; i ++)
ans[q_id] = max(ans[q_id], C[i]);
}
}
}
for(int i = 1; i <= m; i ++) {
long long a = ans[i].a, b = ans[i].b, d = __gcd(a, b);
cout << a / d << ' ' << b / d << '\n';
}
return 0;
}
LOJ - 6062 「2017 山东一轮集训 Day2」Pair
给出一个长度为 \(n\) 的数列 \(\{ a_i \}\) 和一个长度为 \(m\) 的数列 \(\{ b_i \}\)，求 \(\{ a_i \}\) 有多少个长度为 \(m\) 的连续子数列能与 \(\{ b_i \}\) 匹配。
两个数列可以匹配，当且仅当存在一种方案，使两个数列中的数可以两两配对，两个数可以配对当且仅当它们的和不小于 \(h\)。
\(1 \leq a_i, b_i, h \leq 10 ^ 9\)。
将 \(\{ b_i \}\) 升序，每个 \(a_i\) 可以匹配的是一段后缀。然后考虑Hall定理，设 \(N(i)\) 表示与 \(b_i\) 相邻的点集，对任意 \(i \le j\) 必然有 \(N(i) \subseteq N(j)\)，于是要判断是否对任意集合 \(S\) 有 \(|S| \le N(S)\)，只需要考虑所有 \(b_i\) 的前缀。搓一个区间加求全局最小值的线段树，时间复杂度 \(\mathcal{O}(n \log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 1.5e5 + 10;
int n, m, h, A[N], B[N];
namespace SegTree {
#define lc (u << 1)
#define rc (u << 1 | 1)
#define mid ((l + r) >> 1)
int C[N << 2], tag[N << 2];
inline void Tag(int u, int x) {tag[u] += x, C[u] += x; }
inline void pushdown(int u) {
if(!tag[u]) return;
Tag(lc, tag[u]), Tag(rc, tag[u]), tag[u] = 0;
}
void Build(int u, int l, int r) {
tag[u] = 0;
if(l != r) {
Build(lc, l, mid), Build(rc, mid + 1, r);
C[u] = min(C[lc], C[rc]);
} else C[u] = -l;
}
void Add(int u, int l, int r, int L, int R, int x) {
if(l >= L && r <= R) return Tag(u, x);
pushdown(u);
if(mid >= L) Add(lc, l, mid, L, R, x);
if(mid < R) Add(rc, mid + 1, r, L, R, x);
C[u] = min(C[lc], C[rc]);
}
inline int Ask() {return C[1]; }
#undef lc
#undef rc
#undef mid
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m >> h;
if(n < m) {
cout << "0" << '\n';
return 0;
}
for(int i = 1; i <= m; i ++)
cin >> B[i];
for(int i = 1; i <= n; i ++)
cin >> A[i];
sort(B + 1, B + m + 1);
int ans = 0;
SegTree::Build(1, 1, m);
for(int i = 1; i < m; i ++) {
int p = lower_bound(B + 1, B + m + 1, h - A[i]) - B;
if(p <= m) SegTree::Add(1, 1, m, p, m, 1);
}
for(int i = m; i <= n; i ++) {
int p = lower_bound(B + 1, B + m + 1, h - A[i]) - B;
if(p <= m) SegTree::Add(1, 1, m, p, m, 1);
if(i > m) {
p = lower_bound(B + 1, B + m + 1, h - A[i - m]) - B;
if(p <= m) SegTree::Add(1, 1, m, p, m, -1);
}
ans += SegTree::Ask() >= 0;
}
cout << ans << '\n';
return 0;
}
BZOJ - 2138 stone
本质上是要求每次加入询问后，点数尽量多地构成完美匹配。考虑Hall定理，存在完美匹配当且仅当对于任意一段 \([l,r]\) 内的石头，完全包含于 \([l,r]\) 内的询问的 \(k\) 只和不超过该区间内石头个数的和。
设 \(S_i\) 表示 \(a\) 的前缀和，\(PL_{x}\) 表示左端点 \(l \le x\) 的询问的 \(k\) 之和，\(PR_x\) 表示右端点 \(r \le x\) 的询问的 \(k\) 之和，上述条件等价于
\[PR_r-PL_{l-1} \le S_r-S_{l-1}
\]
整理得到
\[PR_r-S_r \le PL_{l-1} - S_{l-1}
\]
我们需要做的就是在每次询问扔掉石头之后仍然满足这个限制。
设 \(f_x=PR_x-S_x\)，\(g_x=PL_x-S_x\)，每次询问扔掉一些石头只会让 \(PR_{r..n}\) 和 \(PL_{l..n}\) 发生变化，具体地，设本次询问区间为 \([l,r]\)，选择扔掉 \(c\) 个石头，那么新增的要求为
\[f_{r'}+x \le g_{l'-1} \qquad r'\ge r,l' -1< l
\]
移项立即得到 \(x \le g_{l'-1}-f_{r'}\)，找到 \(f\) 的一段后缀最大值和 \(g\) 的一段前缀最小值即可，线段树维护，时间复杂度 \(\mathcal{O}(n \log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 10;
int n, m, A[N], S[N], K[N];
struct SegmentTree {
#define lc (u << 1)
#define rc (u << 1 | 1)
#define mid ((l + r) >> 1)
function<int(int, int)> f;
int C[N << 2], tag[N << 2];
inline void maintain(int u) {C[u] = f(C[lc], C[rc]); }
inline void Tag(int u, int x) {tag[u] += x, C[u] += x; }
inline void pushdown(int u) {if(tag[u]) Tag(lc, tag[u]), Tag(rc, tag[u]), tag[u] = 0; }
void Build(int u, int l, int r) {
tag[u] = 0;
if(l != r) {
Build(lc, l, mid), Build(rc, mid + 1, r);
maintain(u);
} else C[u] = -S[l];
}
void Add(int u, int l, int r, int L, int R, int x) {
if(l >= L && r <= R) return Tag(u, x);
pushdown(u);
if(mid >= L) Add(lc, l, mid, L, R, x);
if(mid < R) Add(rc, mid + 1, r, L, R, x);
maintain(u);
}
int Ask(int u, int l, int r, int L, int R) {
if(l >= L && r <= R) return C[u];
pushdown(u);
if(mid >= R) return Ask(lc, l, mid, L, R);
if(mid < L) return Ask(rc, mid + 1, r, L, R);
return f(Ask(lc, l, mid, L, R), Ask(rc, mid + 1, r, L, R));
}
#undef lc
#undef rc
#undef mid
} T[2];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
T[0].f = [&](int a, int b) {return a > b ? a : b; }; // max
T[1].f = [&](int a, int b) {return a < b ? a : b; }; // min
{
long long x, y, z, P; cin >> x >> y >> z >> P;
for(int i = 1; i <= n; i ++)
A[i] = ((i - x) * (i - x) + (i - y) * (i - y) + (i - z) * (i - z)) % P;
for(int i = 1; i <= n; i ++)
S[i] = S[i - 1] + A[i];
}
cin >> m;
{
cin >> K[1] >> K[2];
long long x, y, z, P; cin >> x >> y >> z >> P;
for(int i = 3; i <= m; i ++)
K[i] = (x * K[i - 1] + y * K[i - 2] + z) % P;
}
T[0].Build(1, 1, n), T[1].Build(1, 1, n);
for(int i = 1; i <= m; i ++) {
int l, r; cin >> l >> r;
K[i] = min(K[i], min(0, (l == 1 ? 0 : T[1].Ask(1, 1, n, 1, l - 1))) - T[0].Ask(1, 1, n, r, n));
cout << K[i] << '\n';
T[0].Add(1, 1, n, r, n, K[i]), T[1].Add(1, 1, n, l, n, K[i]);
}
return 0;
}
GYM - 102268D Dates
将所有女孩按照 \(p\) 降序，不断尝试找出时间和剩下的 \(p\) 最大的人进行匹配，不难发现实际上就是维护一个二分图，不断往左部点中加点，每个左部点中的点连向右部点的一个区间，每次加完之后询问是否存在完美匹配，和上一题一样线段树做就行了。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, t, A[N], L[N], R[N], P[N];
long long S[N];
struct SegTree {
#define lc (u << 1)
#define rc (u << 1 | 1)
#define mid ((l + r) >> 1)
function<long long(long long, long long)> f;
long long C[N << 2], tag[N << 2];
inline void maintain(int u) {C[u] = f(C[lc], C[rc]); }
inline void Tag(int u, long long x) {C[u] += x, tag[u] += x; }
inline void pushdown(int u) {if(tag[u]) Tag(lc, tag[u]), Tag(rc, tag[u]), tag[u] = 0; }
void Build(int u, int l, int r) {
tag[u] = 0;
if(l != r) {
Build(lc, l, mid), Build(rc, mid + 1, r);
maintain(u);
} else C[u] = -S[l];
}
void Add(int u, int l, int r, int L, int R, long long x) {
if(l >= L && r <= R) return Tag(u, x);
pushdown(u);
if(mid >= L) Add(lc, l, mid, L, R, x);
if(mid < R) Add(rc, mid + 1, r, L, R, x);
maintain(u);
}
long long Ask(int u, int l, int r, int L, int R) {
if(l >= L && r <= R) return C[u];
pushdown(u);
if(mid >= R) return Ask(lc, l, mid, L, R);
if(mid < L) return Ask(rc, mid + 1, r, L, R);
return f(Ask(lc, l, mid, L, R), Ask(rc, mid + 1, r, L, R));
}
#undef lc
#undef rc
#undef mid
} T[2];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
T[0].f = [&](long long a, long long b) {return a > b ? a : b; }; // max
T[1].f = [&](long long a, long long b) {return a < b ? a : b; }; // min
cin >> n >> t;
for(int i = 1; i <= t; i ++)
cin >> A[i];
for(int i = 1; i <= t; i ++)
S[i] = S[i - 1] + A[i];
for(int i = 1; i <= n; i ++)
cin >> L[i] >> R[i] >> P[i];
vector<int> vec(n); iota(vec.begin(), vec.end(), 1);
sort(vec.begin(), vec.end(), [&](int a, int b) {return P[a] > P[b]; });
T[0].Build(1, 1, t), T[1].Build(1, 1, t);
long long ans = 0;
for(auto x : vec) {
int l = L[x], r = R[x]; long long p = P[x];
if(T[0].Ask(1, 1, t, r, t) != min(0ll, l == 1 ? 0ll : T[1].Ask(1, 1, t, 1, l - 1))) {
ans += p;
T[0].Add(1, 1, t, r, t, 1), T[1].Add(1, 1, t, l, t, 1);
}
// for(int i = 1; i <= t; i ++)
// cerr << T[0].Ask(1, 1, t, i, i) << " \n"[i == t];
// for(int i = 1; i <= t; i ++)
// cerr << T[1].Ask(1, 1, t, i, i) << " \n"[i == t];
}
cout << ans << '\n';
return 0;
}
P6658 边三连通分量
貌似是板子？就是先把边双和dfs树弄出来，只考虑每个边双内部。割掉的两条边有两种情况，两个都是树边或者一个是树边一个是非树边，对于第二种情况，可以用哈希判断某条边是否只被一条非树边覆盖，然后就可以全部扔掉只剩一堆第一种情况的连通块了。
然后再做一遍dfs，如果两个树边被完全相同的非树边覆盖就从中间再隔开就行，用哈希表的话时间复杂度是 \(\mathcal{O}(n + m)\)。
注意 \(m\) 应该多开一点，因为在最后dfs的时候我们还会加 \(\mathcal{O}(n)\) 条边。
跟从你谷题解区里复制过来一样的代码
code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef unsigned long long ull;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5e5 + 10, M = 2e6 + 10;
int n, m, h[N], e[M], ne[M], idx;
inline void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }
int pre[N], low[N], dfs_clock; bool cut[M];
void Tarjan(int u, int fr) {
pre[u] = low[u] = ++dfs_clock;
for(int i = h[u]; i != -1; i = ne[i]) {
if(!(i ^ fr ^ 1)) continue;
int v = e[i];
if(!pre[v]) {
Tarjan(v, i);
low[u] = min(low[u], low[v]);
if(low[v] >= pre[v]) cut[i] = cut[i ^ 1] = true;
} else low[u] = min(low[u], pre[v]);
}
}
void dfs1(int, int);
void dfs2(int, int);
void dfs3(int, int, vector<int> &);
vector<vector<int>> ans;
bool on_tree[M], ccut[M];
int dfn[N], fa[N]; ull w[N];
gp_hash_table<ull, bool> used;
gp_hash_table<ull, int> Map;
void dfs1(int u, int fr) {
dfn[u] = ++dfs_clock;
for(int i = h[u]; i != -1; i = ne[i]) {
if(!(i ^ fr ^ 1) || cut[i]) continue;
int v = e[i];
if(!dfn[v]) {
on_tree[i] = true, fa[v] = u;
dfs1(v, i), w[u] ^= w[v];
} else {
if(dfn[v] > dfn[u]) continue;
ull x = Rand();
w[u] ^= x, w[v] ^= x, used[x] = true;
}
}
if(used.find(w[u]) != used.end())
ccut[fr] = ccut[fr ^ 1] = true;
if(fr == -1 || ccut[fr]) {
Map.clear();
dfs2(u, -1);
vector<int> tmp; dfs3(u, -1, tmp);
ans.emplace_back(tmp);
}
}
void dfs2(int u, int fr) {
for(int i = h[u]; i != -1; i = ne[i]) {
if(!on_tree[i] || cut[i] || ccut[i]) continue;
int v = e[i]; dfs2(v, i);
}
if(Map.find(w[u]) != Map.end()) {
int v = Map[w[u]];
vector<int> tmp; dfs3(u, v, tmp);
ans.emplace_back(tmp);
on_tree[fr] = false;
add(fa[u], v); on_tree[idx - 1] = true, fa[v] = fa[u];
Map[w[u]] = v;
} else Map[w[u]] = u;
}
void dfs3(int u, int goal, vector<int> &vec) {
vec.emplace_back(u);
for(int i = h[u]; i != -1; i = ne[i]) {
if(cut[i] || ccut[i] || !on_tree[i] || e[i] == goal)
continue;
dfs3(e[i], goal, vec);
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i = 1; i <= m; i ++) {
int a, b; cin >> a >> b;
add(a, b), add(b, a);
}
for(int i = 1; i <= n; i ++)
if(!pre[i]) Tarjan(i, -1);
dfs_clock = 0;
for(int i = 1; i <= n; i ++)
if(!dfn[i]) dfs1(i, -1);
for(vector<int> &v : ans)
sort(v.begin(), v.end());
sort(ans.begin(), ans.end());
cout << ans.size() << '\n';
for(vector<int> &v : ans) {
for(int x : v) cout << x << ' ';
cout << '\n';
}
return 0;
}