本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-31 16:35:31
设 $f(S)$ 表示匹配完集合 $S$ 的方案数，最后一个匹配的左点编号就是 $S$ 的模，那么这最后一个点可以和一个右点匹配，当且仅当这两点之间有边且这个右点在 $S$ 中。
然后就好了。可以推测这个问题应该是 NP 难的。
ryp 的博客
博客
标签
暂无
atdpo 状压求二分图完备匹配数
最小路径覆盖
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-08 15:15:17
最小路径覆盖就是选出最少数量的互不重合的路径，使其包含所有的点。也即，每个点在且仅在一条路径上头。
题解区队爷提到：对于这种“对于每个，有且只有”的性质，可以抽象成二分图。
每个点与两个点连接，分别是作为入点和出点的情况。那么我们考虑把每个点抽象成两个点 $(u, u + n)$，然后向 $u$ 的每个出点连边 $(u + n, v)$。这样，我们就能求出来合并的数量，以 $n$ 减去就是路径数量。
试题库问题
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-09 14:11:54
二分图做法
我们考虑将每种试题拆成 $k$ 个点，作为左侧点，代表这种试题的可选项。
右侧点就是每个试题。每个试题与试题选项之间连边。
然后进行二分图匹配。我们知道，每个左侧点有唯一的匹配点，每个右侧点也最多匹配一个左侧点，于是符合题意。
网络流做法
我们设源点为 $S$，汇点为 $T$，那么 $S$ 与每个试题相连，容量均为一；$T$ 与每种类别相连，容量为其需要的数量。然后，试题与其所属于的类型相连，容量是一。
在这个网络中，如果最大流不为总共需要匹配的数量，那么就无解；否则直接找流量非零的点然后输出即可。
这样下来，一共需要 $n + k + 2$ 个点。
p.s. 感觉开始悟到二分图和网络流的一些用处了 /hsh
gcd 动态维护
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-16 08:54:23
ryp love gcd
给定一个数列，需要维护以下操作：
点修
给定 $x$，查询 $\gcd (a_i, a_j) = x$ 的 $(a_i, a_j)$ 中 $\lvert a_i - a_j \rvert$ 最大的 $a_i$ 和 $a_j$
值域 $[2, 10^5]$
这时候 $a_i$ 和 $a_j$ 一定均是 $x$ 的倍数（但反之不一定），那么我们就需要维护一个数的所有存在于序列中的倍数。
妈的，这玩意儿怎么维护？
暴力修好像是能接受的。我日。牛逼。
那这题做完了。
ABC348G 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-10 12:08:45
给定长为 $N$ 的两个整数列 $A$ 与 $B$，对于每个 $k = 1, 2, \cdots, N$，选择 $k$ 个互异下标组成集合 $S$，使 $(\sum\limits_{i\in S} A_i) - \max\limits_{i\in S}B_i$ 最大。
输出每个 $k$ 对应的最大值。
我用的是 $O(n\log^2 n)$ 的主席树 + 决策单调性分治，但是听说有单 $\log$ 的做法。
考虑 $k$ 固定的情况。我们枚举一个 $d\in [k, n]$ 作为 $\max B$ 的下标（先以 $B$ 为关键字排序），那么那个式子的最大值，显然是取 $k - 1$ 个最大的 满足 $B$ 小于 $B_d$ 的 $A$ 值之和。因为我们已经按照 $B$ 排序，那么就是取 $d$ 之前的 $k - 1$ 个最大 $A$ 值。明显主席树维护。
接下来观察单调性。一图胜千言，下面是 $k$ 与决策点的关系：
于是，$k$ 的决策点一定不高于 $k + 1$ 的，也不低于 $k - 1$ 的。这时，我们可以用决策单调性分治来得到 $[1, n]$ 上每个最大值。
最终复杂度是 $T(n) = T(\dfrac n 2) + O(n\log n) = O(n\log^2n)$ 的。
代码：
#include <iostream>
#include <algorithm>
#define int long long
#define fi first
#define se second
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
const int N = 2e5 + 10;
const ll inf = 1e18;
int qcnt[32 * N], qsum[32 * N], ls[32 * N], rs[32 * N], rt[N], cnt = 0, nr = 0;
ll dsc[N], f[N];
pair<ll, ll> z[N];
static inline ll J (ll x) { return dsc[nr++] = x; }
static inline int Q (ll x) { return lower_bound (dsc, dsc + nr, x) - dsc + 1; }
void upd (int &u, int v, int x, int y, int k, ll val)
{
int mid = (x + y) \/ 2;
qcnt[u = ++cnt] = qcnt[v] + 1, qsum[u] = qsum[v] + val, ls[u] = ls[v], rs[u] = rs[v];
if (x == y) return;
if (k <= mid) upd (ls[u], ls[v], x, mid, k, val);
else upd (rs[u], rs[v], mid + 1, y, k, val);
}
ll qry (int u, int x, int y, int k)
{
int mid = (x + y) \/ 2;
if (x == y) return dsc[x - 1] * k;
if (k <= qcnt[rs[u]]) return qry (rs[u], mid + 1, y, k);
else return qry (ls[u], x, mid, k - qcnt[rs[u]]) + qsum[rs[u]];
}
void solve (int l, int r, int ql, int qr)
{
int mid = (ql + qr) \/ 2, mpos = -1;
ll mval = -inf;
if (l > r || ql > qr) return;
for (int d = max (l, mid); d <= r; d++) {
ll f = qry (rt[d], 1, nr, mid) - z[d].se;
if (f > mval) mval = f, mpos = d;
}
f[mid] = mval;
solve (l, mpos, ql, mid - 1), solve (mpos, r, mid + 1, qr);
}
signed main (void)
{
int n;
ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> z[i].fi >> z[i].se, J (z[i].fi);
sort (z + 1, z + n + 1, [](pi &x, pi &y) { return x.se < y.se; }), sort (dsc, dsc + nr), nr = unique (dsc, dsc + nr) - dsc;
for (int i = 1; i <= n; i++) upd (rt[i], rt[i - 1], 1, nr, Q (z[i].fi), z[i].fi);
solve (1, n, 1, n);
for (int i = 1; i <= n; i++) cout << f[i] << '\n';
return 0;
}
P2633 Count on a tree 主席树的树上差分
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-11 13:27:25
题意很简单。
我们如果要查询的是子树上的第 $k$ 小，那这就是很裸的 dfn 序套 DS 维护，DS 选主席树就很合适。
但是现在维护的是 $u$ 到 $v$ 路径上的，这段路径上的 dfn 序并不是连续的，并且第 $k$ 小这种东西也是可加的，没法说分开求解。
那怎么办呢？我们想起了树上差分。
我们知道，$u$ 到 $v$ 路径上的信息，就是他们到 LCA 上路径信息的叠加。我们再考虑主席树，可以将 $u$，$v$，LCA 与 LCA 父节点做差分，那么得到的就是 $u$ 到 $v$ 路径上的信息。维护即可。
非常美丽的线段树差分！
Niareh 的四月 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-15 08:00:59
A - 回忆
题意
在正整数集合中每次选取一对 $x$ 与 $y$ 使得 $x - y \gt 0 \notin S$，然后将其加入 $S$。计算最终 $S$ 模的最大值。
分析
考虑到最终的 $S$ 一定是一个等差数列，否则一定存在不属于 $S$ 的非负 $x - y$。那么我们所要找的就是这个最终等差数列的公差。不难发现，其就是原序列的 $\gcd$。
因此，最终集合的模就是集合中最大的元素除以 $\gcd$。
复杂度： $O(n\log n)$
STD
#include <iostream>
using namespace std;
int gcd (int a, int b) { return b ? gcd (b, a % b) : a; }
int main (void)
{
int n, res, v;
ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
cin >> n >> res, --n;
while (n--) cin >> v, res = gcd (res, v);
cout << v \/ res << '\n';
return 0;
}
B - 街道
题意
给定一棵树，找其中距离小于等于 $k$ 的点对的数量的总和。
分析
换根 DP 模板题。我们设 $g(u, i)$ 代表在 $u$ 子树中距离其小于等于 $i$ 的点数量，有转移方程：
$$g(u, i) = \sum\limits_{v} g(v, i - 1)$$
然后，我们设 $f(u, i)$ 表示在整棵树里距离 $u$ 小于等于 $i$ 的点数量，对于 $u$ 的每个孩子 $v$ ，有转移方程：
$$f(v, i) = \begin{cases} f(u, i) + g(v, i) - g(v, i - 2) & (i \ge 2) \ g(v, 1) + 1 & (i = 1) \ 1 & (i = 0) \end{cases}$$
不妨设点 $1$ 为根，那么 $f(1, i) = g(1, i)$，转移即可。
复杂度： $O(n)$
STD
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int N = 2e5 + 10, K = 25;
ll f[N][K], g[N][K];
int k;
vector<int> e[N];
void dfs1 (int u, int fa)
{
g[u][0] = 1;
for (auto v : e[u])
if (v != fa) {
dfs1 (v, u);
for (int i = 1; i <= k; i++) g[u][i] += g[v][i - 1];
}
}
void dfs2 (int u, int fa)
{
for (auto v : e[u])
if (v != fa) {
f[v][0] = 1, f[v][1] = g[v][1] + 1;
for (int i = k; i >= 2; i--) f[v][i] = f[u][i - 1] + g[v][i] - g[v][i - 2];
}
for (auto v : e[u]) if (v != fa) dfs2 (v, u);
}
int main (void)
{
int n;
ll res = 0;
ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
cin >> n >> k;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
e[u].emplace_back (v), e[v].emplace_back (u);
}
dfs1 (1, 0);
for (int i = 0; i <= k; i++) f[1][i] = g[1][i];
dfs2 (1, 0);
for (int i = 1; i <= n; i++) for (int j = 0; j <= k; j++) res += f[i][j];
cout << res << '\n';
return 0;
}
C - 数环
题意
从 $n$ 个数中选出几个，使得其和在模 $p$ 的意义下最大。
分析
注意数据范围 $n \le 40$。若暴搜 $O(2^n)$ 显然无法通过。我们考虑折半搜索，即 meet-in-the-middle。
将序列均分成两半。对于左边，我们搜出所有和并存在数组中，并排序。对于右边，我们枚举能加出的每个和。考虑右边每个和能和左边哪些组合产生最大值。
设在右边搜出了 $v$，那么首先可以和左边第一个，即最大的使得 $u \lt p - v$ 的结合。其次，我们可以和最大值结合，因为其与 $v$ 的和模 $p$ 后一定不劣于其他大于 $p$ 的和。
复杂度： $O(2^{n/2}\log n + n\log n)$
STD
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 42;
int z[N], n, m, res = 0;
vector<int> w;
void dfs1 (int x, int sum)
{
if (x > n \/ 2) return w.push_back (sum), void ();
dfs1 (x + 1, sum), dfs1 (x + 1, (sum + z[x]) % m);
}
void dfs2 (int x, int sum)
{
if (x > n) {
int p = lower_bound (begin (w), end (w), m - sum)[-1];
res = max (res, max (p + sum, (w.back () + sum) % m));
return;
}
dfs2 (x + 1, sum), dfs2 (x + 1, (sum + z[x]) % m);
}
int main (void)
{
ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> z[i];
dfs1 (1, 0), sort (begin (w), end (w)), dfs2 (n \/ 2 + 1, 0);
cout << res << '\n';
return 0;
}
D - 周期
题意
给定一个 $n$ 点 $n$ 边的无向图（基环树），可以改变每条边的方向。若随机等概率改变，求不出现环的概率模 $998244353$。
分析
我们知道，一个有向环存在，当且仅当环上所有边的方向相同。那么，对每个无向环，只有两种情况能存在环。
可能存在多个环。我们设环总共的大小为 $x$，每个环的大小为 $x_i$，那么答案就是：
$$2^{-n} \times 2^{n-x} \times \prod\limits_{i} (2^{x_i}-2)$$
即
$$2^{-x} \times\prod\limits_{i}(2^{x_i}-2)$$
复杂度： $O(n\log n)$
STD
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int N = 2e5 + 10, P = 998244353;
vector<int> e[N];
int dep[N], w[N], nr = 0, tst = 0;
ll fxp (ll a, ll b)
{
ll res = 1;
while (b) {
if (b & 1) res = res * a % P;
b >>= 1, a = a * a % P;
}
return res;
}
void dfs (int u, int fa)
{
dep[u] = dep[fa] + 1;
for (auto v : e[u])
if (!dep[v]) dfs (v, u);
else if (dep[v] > dep[u]) w[nr++] = dep[v] - dep[u] + 1;
}
int main (void)
{
int n;
ll cnt = 0, prd = 1;
ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
cin >> n;
for (int u = 1, v; u <= n; u++) cin >> v, e[u].push_back (v), e[v].push_back (u);
for (int u = 1; u <= n; u++) if (!dep[u]) dfs (u, 0);
for (int i = 0; i < nr; i++) (cnt += w[i]) %= P, (prd *= (fxp (2, w[i]) + P - 2) % P) %= P;
cout << fxp (fxp (2, cnt), P - 2) * prd % P << '\n';
return 0;
}
F - 人偶
题意
从 $n$ 个物品中不断选 $P$ 次（$P \rightarrow \infty$），若超过 $k$ 个就弹出队头。每个物品被选中的概率是 $p_i$，只能选中一次。求最终每个物品在队中的概率。
分析
最终队列不满的概率大概是 $\prod (1-p)^P$ 量级的，早就爆掉精度了，不计。因此我们只计算队列满的情况下的概率。
可以直接状压。设 $f(S)$ 是选中这个状态的概率，那么方程显然：
$$f(S) = \sum\limits_{k\in S} f(S - \{k\}) \cdot p_k$$
转移即可。
注意边界。当每个物品一定会被选中时候特判。
复杂度： $O(2^n \times n)$
STD
#include <iostream>
#include <iomanip>
using namespace std;
const int N = 20;
const long double eps = 1e-12;
long double f[1 << N], z[N], res[N];
int main (void)
{
int n, k, cnt = 0;
ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> z[i], cnt += z[i] > eps;
if (cnt <= k) {
for (int i = 0; i < n; i++) cout << (z[i] > eps ? "1.00 " : "0.00 ");
return 0;
}
f[0] = 1;
for (int i = 0; i < 1 << n; i++) {
long double sum = 0;
if (__builtin_popcount (i) == k) {
for (int j = 0; j < n; j++) if (i & (1 << j)) res[j] += f[i];
continue;
}
if (f[i] < eps) continue;
for (int j = 0; j < n; j++) if (i & (1 << j)) sum += z[j];
f[i] \/= 1 - sum;
for (int j = 0; j < n; j++) if (!(i & (1 << j))) f[i + (1 << j)] += f[i] * z[j];
}
cout << fixed << setprecision (2);
for (int i = 0; i < n; i++) cout << res[i] << ' ';
return 0;
}
G - 溶解
题意
求 $$\exp(\ln g \sum_{d\mid n} {n\choose d}) \bmod 1000000223$$
分析
设 $P = 1000000223$，由欧拉定理，原式即
$$\exp(\ln g \sum_{d\mid n} {n\choose d} \bmod \ arphi(P)) \bmod P$$
其中，由于 $P$ 是质数，$\ arphi(P) = P - 1$。
就算是转换后，求指数里数也并不简单，况且 $P - 1$ 不是质数。题目里已经给了 $P - 1$ 的质因数分解，这时候我们应该能够想到分别求解四组同余方程，然后用 CRT 合并。
至于里头这个大组合数，明显 Lucas。
代码实现不难。
STD
#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const ll p[4] = { 2, 13, 2797, 13751 }, T = 1000000222, P = T + 1;
ll a[4], fac[40000], x, y;
static void exgcd (ll a, ll b)
{
ll t;
if (!b) return x = 1, y = 0, void ();
exgcd (b, a % b), t = x, x = y, y = t - a \/ b * y;
}
static inline ll inv (ll v, ll p) { return exgcd (v, p), (x + p) % p; }
static inline ll C (ll m, ll n, ll p) { return m > n ? 0 : fac[n] * inv (fac[m], p) % p * inv (fac[n - m], p) % p; }
static inline ll lucas (ll m, ll n, ll p) { return m ? lucas (m \/ p, n \/ p, p) * C (m % p, n % p, p) % p : 1; }
static ll fxp (ll a, ll b)
{
ll res = 1;
while (b) {
if (b & 1) res = res * a % P;
b >>= 1, a = a * a % P;
}
return res;
}
int main (void)
{
ll res = 0, n, g;
ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
cin >> n >> g;
if (g % P == 0) cout << "0\n", exit (0);
for (int i = 0; i < 4; i++) {
fac[0] = 1;
for (int j = 1; j <= p[i]; j++) fac[j] = fac[j - 1] * j % p[i];
for (ll q = 1; q * q <= n; q++) {
ll y = q;
if (n % y) continue;
(a[i] += lucas (y, n, p[i])) %= p[i];
if (y * y == n) continue;
(a[i] += lucas (n \/ y, n, p[i])) %= p[i];
}
}
for (int i = 0; i < 4; i++) (res += T \/ p[i] * inv (T \/ p[i], p[i]) % T * a[i] % T) %= T;
cout << fxp (g, res) << '\n';
return 0;
}
G - 水杯
题意
一个长度为 $n$ 的序列，两种操作：
- 单点赋值
- 找 $x$ 个数，每个数删掉一，问能不能重复 $k$ 次。
分析
本场的数据结构压轴。
比较好分析。设大于等于 $k$ 的数有 $u$ 个，小于 $k$ 的数和为 $v$，那么只要满足：
$$v \ge (x - u) \times k$$
在线可以用平衡树，离线可以用树状数组。本来想做强制在线，但是太毒瘤了。（但是赛时还是加了一个在线版本）
复杂度： $O(n\log n)$
STD
#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
int fa[N], son[N][2], siz[N], cntq[N], cnt = 1, rt;
ll qsum[N], val[N], z[N];
static inline void maintain (int x) { qsum[x] = qsum[son[x][0]] + qsum[son[x][1]] + val[x] * cntq[x], siz[x] = siz[son[x][0]] + siz[son[x][1]] + cntq[x]; }
static inline int get (int x) { return x == son[fa[x]][1]; }
static inline int compare (int f, int k) { return k > val[f]; }
void rotate (int x)
{
int y = fa[x], z = fa[y], p = get (x);
son[y][p] = son[x][p ^ 1];
if (son[x][p ^ 1]) fa[son[x][p ^ 1]] = y;
fa[fa[son[x][p ^ 1] = y] = x] = z;
if (z) son[z][y == son[z][1]] = x;
maintain (y), maintain (x);
}
int splay (int x, int t = 0)
{
for (int f = fa[x]; (f = fa[x]) != t; rotate (x))
if (fa[f] != t) rotate (get (x) == get (f) ? f : x);
return t ? x : rt = x;
}
int insert_at (int f, ll k)
{
qsum[cnt] = val[cnt] = k, siz[cnt] = cntq[cnt] = 1, fa[cnt] = f;
if (f) son[f][compare (f, k)] = cnt;
return cnt++;
}
int insert (int k)
{
int f = rt, last = 0;
if (!f) return rt = insert_at (0, k);
while (f && val[f] != k) last = f, f = son[f][compare (f, k)];
if (f && val[f] == k) return cntq[f]++, splay (f);
else return f = insert_at (last, k), maintain (last), splay (f);
}
int find (int k)
{
int f = rt;
if (!f) return 0;
while (son[f][compare (f, k)] && val[f] != k) f = son[f][compare (f, k)];
return splay (f);
}
int merge (int x, int y)
{
int f = x;
if (!x || !y) return x + y;
while (son[f][1]) f = son[f][1];
splay (f, fa[x]);
if (y) fa[y] = f;
son[f][1] = y;
return f;
}
int remove (int k)
{
int f = find (k), x;
if (val[f] != k) return 0;
if (cntq[f] > 1) return cntq[f]--, splay (f);
if ((x = merge (son[f][0], son[f][1]))) fa[x] = 0;
return rt = x;
}
int qpre (int k)
{
int f = son[find (k)][0];
if (val[rt] < k) return rt;
while (son[f][1]) f = son[f][1];
return f;
}
int qnext (int k)
{
int f = son[find (k)][1];
if (val[rt] > k) return rt;
while (son[f][0]) f = son[f][0];
return f;
}
int main (void)
{
int n, m;
ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
cin >> n >> m;
insert (0), insert (1e9);
memset (z, 0x80, sizeof z);
while (m--) {
int t, x, y;
cin >> t >> x >> y;
if (t == 1) z[x] >= 0 ? remove (z[x]) : 0, insert (z[x] = y);
else {
int p = qpre (y), q = qnext (y);
ll sum, k;
splay (p), sum = qsum[p] - qsum[son[p][1]];
splay (q, p), k = cntq[son[q][0]];
splay (q), k += siz[q] - siz[son[q][0]] - 1;
cout << (sum >= (x - k) * y ? "Yes" : "No") << '\n';
}
}
return 0;
}
ABC350F 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-21 16:00:05
这是一篇 平衡树 题解，跑得比较慢（$O(n\log n)$，121ms），但是思维难度较低。
题意
把括号序列从内向外展开。展开是指区间与大小写的同时反转。
输出最后的字符串，不含括号。
分析
根据“序列翻转”，我们可以想到文艺平衡树。大小写反转，无非就是在标记上简单操作一下。
怎么保证从内向外展开呢？我们可以用栈模拟括号匹配：遇到左括号就入栈当前下标，遇到右括号就从栈里弹出左括号，并且将左右括号下标存起来。
最后所有的括号都是不交的，也即，$l_i \lt r_i \lt l_{i+1} \lt r_{i+1}$。于是，我们按照 $r - l$ 即括号序列的长度排序，然后挨个展开，就一定能保证是从内向外展开的。
核心代码：
for (int i = 0; i < n; i++)
if (s[i] == '(') q.push (i);
else if (s[i] == ')') g.push_back(make_pair (q.top (), i)), q.pop ();
sort (begin (g), end (g), [](pi &x, pi &y) { return x.se - x.fi < y.se - y.fi; });
for (auto v : g) rev (v.fi + 2, v.se);
dfs (rt);
submission 121ms
后记：发现自己纯 nt 了。。。$O(n)$ 简单可做。。黄愣成蓝
ABC350G 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-21 23:44:22
LCT 板子，然而我没不会 LCT，然而可以根号分治甚至跑得贼快。
既然已经保证了整个图是森林，我们就好办了，树上可简单得多。
我们先考虑只有操作二的情况：很明显，我们只需要找两个点所连接的点的交集，明显这个交集的模不大于一。这个过程是 $O(d(u)) = O(n)$ 的。可以用一个 bitset 优化，那么就比上一个 $\omega$ 的常数。
再看操作一。我们暴力改的话无非就是 bitset 设位，是 $O(1)$ 的…… 但是
…… 明显这个做法是行不通的，bitset 空间 $O(n^2)$，爆掉。
考虑根号分治。对于度不大于 $\sqrt N$ 的点，修改无视 $O(1)$，操作直接暴力 $O(\sqrt N)$，很优。
大于 $\sqrt N$ 的点，建立 bitset（我们最多只会建立 $\sqrt N$ 个 bitset） 是 $O(\sqrt N)$ 的。查找是最差 $O(\dfrac N {2\omega})$ 的（因为两个点的度都要大于 $\sqrt N$，于是比上一个 $2$）。
看起来很差，但是 $N$ 和 $Q$ 的和是有限制的（设 $T = 10^5$），解一下得到一个大致最大 $Q = \dfrac {T} 2$ 时候为 $\dfrac {T^2} {8\omega} \pprox 10^{7.29}$，叉不掉。简单写了一个 generator，但是根本叉不掉，只叉到 100ms 左右。
#include <iostream>
using namespace std;
const int N = 5e4, Q = 5e4;
int main (void)
{
ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
cout << N << ' ' << N + Q << '\n';
for (int i = 4; i <= N \/ 2 + 1; i++) cout << "1 2 " << i << '\n';
for (int i = N \/ 2 + 2; i <= N; i++) cout << "1 3 " << i << '\n';
cout << "1 1 2\n1 1 3\n";
for (int i = 0; i < Q + 1; i++) cout << "2 2 3\n";
return 0;
}
这题到这里就真正做完了。
题解：AT_abc351_f [ABC351F] Double Sum
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-28 09:58:14
题意明显：对每个 $i$，求 $\sum\limits_{j=i+1}^n \max (A_j - A_i, 0)$。求每个 $i$ 的答案总和。
实际上就是找使得 $A_j \gt A_i$ 且 $j \gt i$ 的所有 $A_j$ 的和。我们从后往前加入 $A_i$，那么就消掉了第二维。于是只需要统计当前所有大于 $A_i$ 的数的和以及数量即可。
可以用离散化 + 树状数组，也可以平衡树。我写的后者。
upd 2024.05.02 加了一个树状数组写法
共 201 篇博客
鲁ICP备2025150228号