OI笔记 | 2023.1-2 做题记录（一）
- [USACO] Reverse Engineering
- [HNOI2011]XOR和路径
- 树的中心
- [SHOI2015]脑洞治疗仪
- 「Wdsr-2.7」文文的摄影布置
- The Child and Sequence
- 方差
- [USACO22FEB] Sleeping in Class B
- [NOI2005] 维护数列
- 哈希冲突
- 无向图三元环计数
[USACO] Reverse Engineering
Elsie 有一个程序，接受一个 $N$（$1\le N\le 100$）个变量的数组 $b[0],…,b[N−1]$ 作为输入，其中每个变量等于 0 或 1，并且返回对输入数组应用一系列 if / else if / else 语句的结果。每个语句检查至多一个输入变量的值，并返回 0 或 1。这类程序的一个例子是：
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
例如，如果上方程序的输入是 10（即 $b[0]=1$ 及 $b[1]=0$），那么输出应当为 1。
Elsie 告诉了 Bessie 对于 $M（1\le M\le 100）$个不同输入的正确输出。Bessie 现在正试图对 Elsie 的程序进行逆向工程。不幸的是，Elsie 可能说了谎；可能不存在上述形式的程序行为与 Elsie 所说的均一致。
对于 $T（1\le T\le 10）$个子测试用例中的每一个，判断 Elsie 是否一定在说谎。
题解
按位匹配。如果某一位上的某些输入中，$0$ 和 $1$ 分别的对应是没有冲突的（即没有出现有些 $0$ 对应 $1$，有些 $0$ 对应 $0$ 这种情况），我们就可以加一个 if 语句让这些不冲突的输入都返回正确的答案。
然后我们下一轮匹配就不用再匹配这些已经确定能返回正确答案的输入了。
最多匹配 $n$ 轮，每轮要遍历每一输入输出的每一位。故时间复杂度 $O(n^2 m)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 110;
bool a[MAX_N][MAX_N], res[MAX_N], vis[MAX_N], flag[2];
int bl[2];
// 省略快读快写
inline ll read() {...}
inline void write(ll x) {...}
inline bool read_bool() {...}
int main() {
int T = read();
while(T--) {
int n = read(), m = read();
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++)
a[i][j] = read_bool();
res[i] = read_bool();
vis[i] = 0;
}
for(int k = 1; k <= n; k++) {
for(int j = 1; j <= n; j++) {
bl[0] = bl[1] = -1; flag[0] = flag[1] = 0;
for(int i = 1; i <= m; i++) {
if(vis[i]) continue;
if(bl[a[i][j]] == -1) bl[a[i][j]] = res[i];
else if(bl[a[i][j]] != res[i]) flag[a[i][j]] = 1;
}
for(int i = 1; i <= m; i++)
if(!flag[a[i][j]]) vis[i] = 1;
}
}
bool f = 0;
for(int i = 1; i <= m; i++)
if(!vis[i]) f = 1;
puts(f ? "LIE" : "OK");
}
return 0;
}
[HNOI2011]XOR和路径
给定一个无向连通图，其节点编号为 $1$ 到 $N$，其边的权值为非负整数。试求出一条从 $1$ 号节点到 $N$ 号节点的路径，使得该路径上经过的边的权值的“XOR 和”最大。该路径可以重复经过某些节点或边，当一条边在路径中出现多次时，其权值在计算“XOR 和”时也要被重复计算相应多的次数。
直接求解上述问题比较困难，于是你决定使用非完美算法。具体来说，从 $1$ 号节点开始，以相等的概率，随机选择与当前节点相关联的某条边，并沿这条边走到下一个节点，重复这个过程，直到走到 $N$ 号节点为止，便得到一条从 $1$ 号节点到 $N$ 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。
$2\le N\le 100$，$M\le 10000$，图中可能有重边或自环。
题解
如果用 $f_i$ 表示 $1\sim i$ 路径的期望，这条路径可能是无穷无尽的，不好考虑。所以可以考虑用 $f_i$ 表示 $i\sim n$ 路径的期望。
然后我们拆位考虑。对于每一位，由于边权变为只有 $0$ 或 $1$，所以异或的期望就是结果为 $1$ 的概率。有以下转移：
\[f_u=\frac1{de_u}[\sum_{w(u,v)=0}f_v+\sum_{w(u,v)=1}(1-f_v)]\]即 $v$ 为 $1$，路径为 $0$ 或 $v$ 为 $0$，路径为 $1$。其中 $de_u$ 为 $u$ 的出度。
然后我们发现不是很好 dp。但是可以把上式转化成：
\[-de_uf_u+\sum_{w(u,v)=0}f_v-\sum_{w(u,v)=1}f_v=-\sum_{w(u,v)=1}1\]用高斯消元对每一位解一遍这个方程组即可。然后合并答案。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
const int MAX_N = 200;
int n, m, de[MAX_N];
double ans, a[MAX_N][MAX_N];
struct edge {
int u, v, w;
edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
};
vector<edge> edges;
vector<int> G[MAX_N];
void AddEdge(int u, int v, int w) {
edges.pb(edge(u, v, w));
G[u].pb((int)edges.size() - 1);
de[u]++;
}
inline ll read() {...}
void Gauss() {
for(int i = 1; i <= n; i++) {
int mx = i;
for(int j = i + 1; j <= n; j++)
if(fabs(a[j][i]) > fabs(a[mx][i])) mx = j;
swap(a[i], a[mx]);
for(int j = 1; j <= n; j++) {
if(j == i) continue;
double d = a[j][i] / a[i][i];
for(int k = i + 1; k <= n + 1; k++)
a[j][k] -= a[i][k] * d;
}
}
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
AddEdge(u, v, w);
if(u != v) AddEdge(v, u, w);
}
for(int k = 30; k >= 0; k--) {
memset(a, 0, sizeof(a));
a[n][n] = 1;
for(int i = 1; i < n; i++) {
a[i][i] = -de[i];
for(int j = 0; j < (int)G[i].size(); j++) {
edge t = edges[G[i][j]];
int v = t.v, w = (t.w >> k) & 1;
if(w == 1) a[i][v]--, a[i][n + 1]--;
else a[i][v]++;
}
}
Gauss();
ans += (1 << k) * a[1][n + 1] / a[1][1];
}
printf("%.3lf", ans);
return 0;
}
树的中心
树的中心是指到最远的节点距离最近的那个节点。
找到一棵树的所有中心。
题解
好像可以树形 dp，但是我觉得很麻烦。
所以你就 dfs 找出直径的两端。可以证明树的中心一定在树的直径上，且趋于中点。然后这个最远的距离一定是到直径两端的距离，枚举一下每个节点即可。
时间复杂度：$O(n)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
vector<int> G[MAX_N];
int d1[MAX_N], d2[MAX_N], n, l1, l2, mn;
int ans[MAX_N], cnt;
inline ll read() {...}
inline void write(ll x) {...}
void dfs(int u, int fa, int *d, int &mx) {
for(int v : G[u]) {
if(v == fa) continue;
d[v] = d[u] + 1;
if(d[v] > d[mx]) mx = v;
dfs(v, u, d, mx);
}
}
int main() {
n = read();
for(int i = 1; i < n; i++) {
int fa = read();
G[i + 1].push_back(fa), G[fa].push_back(i + 1);
}
dfs(1, 0, d1, l1);
memset(d1, 0, sizeof(d1));
dfs(l1, 0, d1, l2);
dfs(l2, 0, d2, l1);
mn = (1 << 30);
for(int i = 1; i <= n; i++) {
if(mn > max(d1[i], d2[i])) {
mn = max(d1[i], d2[i]);
cnt = 0;
}
if(mn == max(d1[i], d2[i])) ans[++cnt] = i;
}
for(int i = 1; i <= cnt; i++)
write(ans[i]), putchar(' ');
return 0;
}
[SHOI2015]脑洞治疗仪
曾经发明了自动刷题机的发明家 SHTSC 又公开了他的新发明：脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。
为了简单起见，我们将大脑视作一个 01 序列。$1$ 代表这个位置的脑组织正常工作，$0$ 代表这是一块脑洞。
1 0 1 0 0 0 1 1 1 0
脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出，将其中正常工作的脑组织填补在这块脑洞中。（所以脑洞治疗仪是脑洞的治疗仪？）
例如，用上面第 $8$ 号位置到第 $10$ 号位置去修补第 $1$ 号位置到第 $4$ 号位置的脑洞，我们就会得到：
1 1 1 1 0 0 1 0 0 0
如果再用第 $1$ 号位置到第 $4$ 号位置去修补第 $8$ 号位置到第 $10$ 号位置：
0 0 0 0 0 0 1 1 1 1
这是因为脑洞治疗仪会把多余出来的脑组织直接扔掉。
如果再用第 $7$ 号位置到第 $10$ 号位置去填补第 $1$ 号位置到第 $6$ 号位置：
1 1 1 1 0 0 0 0 0 0
这是因为如果新脑洞挖出来的脑组织不够多，脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。
假定初始时 SHTSC 并没有脑洞，给出一些挖脑洞和脑洞治疗的操作序列，你需要即时回答 SHTSC 的问题：在大脑某个区间中最大的连续脑洞区域有多大。
$n, m \leq 200000$。
题解
关键点是我们要用线段树维护什么。
首先要询问区间最长连续 $0$ 的个数。这个比较典，容易想到要维护前缀后缀的最长连续 $0$ 的个数 lmax 和 rmax，才能转移出这个最大值 val。此外节点还需要记录它储存的区间长度 len。再维护一个 $1$ 的数量 sum，为了支持脑洞治疗的操作。
pushup 都比较经典，可以见代码。
另一个关键点就是脑洞治疗怎么做。由于我们发现脑洞个数具有单调性，所以可以二分找到分界点，然后区间填平即可。
时间复杂度带两个 $\log$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5 + 10;
int n, q;
struct node {
int val, lmax, rmax, sum, len, tag;
node(int _val = 0, int _lmax = 0, int _rmax = 0, int _sum = 0, int _len = 0, int _tag = -1) : val(_val), lmax(_lmax), rmax(_rmax), sum(_sum), len(_len), tag(_tag){}
} d[MAX_N << 2];
inline ll read() {...}
inline void write(ll x) {...}
inline int lc(int p) {return (p << 1);}
inline int rc(int p) {return (p << 1) | 1;}
inline int mid(int s, int t) {return s + ((t - s) >> 1);}
inline node U(node L, node R) {
node ret;
ret.sum = L.sum + R.sum;
ret.len = L.len + R.len;
if(L.lmax == L.len) ret.lmax = L.len + R.lmax;
else ret.lmax = L.lmax;
if(R.rmax == R.len) ret.rmax = R.len + L.rmax;
else ret.rmax = R.rmax;
ret.val = max(max(L.val, R.val), L.rmax + R.lmax);
return ret;
}
inline void change(int p, int k) {
d[p].lmax = d[p].rmax = d[p].val = d[p].len * (k ^ 1);
d[p].sum = d[p].len * k;
d[p].tag = k;
}
inline void pd(int p) {
if(d[p].tag != -1) {
change(lc(p), d[p].tag);
change(rc(p), d[p].tag);
d[p].tag = -1;
}
}
void build_tree(int s, int t, int p) {
d[p].sum = d[p].len = t - s + 1;
if(s == t) return;
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
}
void update(int s, int t, int p, int l, int r, int k) {
if(l <= s && t <= r) {
change(p, k);
return;
}
pd(p);
int m = mid(s, t);
if(l <= m) update(s, m, lc(p), l, r, k);
if(r > m) update(m + 1, t, rc(p), l, r, k);
d[p] = U(d[lc(p)], d[rc(p)]);
}
node query(int s, int t, int p, int l, int r) {
if(l <= s && t <= r) return d[p];
pd(p);
int m = mid(s, t);
node L, R;
if(l <= m) L = query(s, m, lc(p), l, r);
if(r > m) R = query(m + 1, t, rc(p), l, r);
return U(L, R);
}
inline int queryF(int l, int r) {
node tmp = query(1, n, 1, l, r);
return (r - l + 1) - tmp.sum;
}
int main() {
n = read(), q = read();
build_tree(1, n, 1);
while(q--) {
int op = read();
if(op == 0) {
int l = read(), r = read();
update(1, n, 1, l, r, 0);
}
else if(op == 1) {
int l0 = read(), r0 = read(), l1 = read(), r1 = read(), tmp;
tmp = query(1, n, 1, l0, r0).sum;
if(!tmp) continue;
update(1, n, 1, l0, r0, 0);
int l = l1, r = r1 + 1;
while(l < r - 1) {
int m = mid(l, r);
if(queryF(l1, m) <= tmp) l = m;
else r = m;
}
update(1, n, 1, l1, l, 1);
}
else {
int l = read(), r = read();
write(query(1, n, 1, l, r).val), putchar('\n');
}
}
return 0;
}
「Wdsr-2.7」文文的摄影布置
文文给每张照片定了一个吸引度 $A_i$ 与大小 $B_i$ 。
形式化地说，规定 $\psi(i,k) = A_i + A_k - \min(B_j)$，其中需要满足 $i < j < k$。
摸清了照片价值的计算，文文会告诉你共 $m$ 个操作，可以分为以下三种：
-
$\verb!1 x y!$ ：照片的吸引度发生变化。文文要将 $A_x$ 修改为 $y$ 。
-
$\verb!2 x y!$ ：照片的大小发生变化。文文要将 $B_x$ 修改为 $y$ 。
-
$\verb!3 l r!$ ：文文打算利用素材库的第 $l$ 到第 $r$ 张中的图片，你要告诉她 $\psi(x,y)$ 的最大值（ $l\le x\le x+1<y \le r$ ）。
$1 \leq A_i,B_i,y \leq 10^8$，$1 \le x \le n$，$1 \le l \le r \le n$。
题解
这题就是要推出你要在线段树上维护什么内容。由于要的是 $A_i+A_k-\min(B_j)$ 的最大值，其实这个 $\min$ 是多余的，答案最大时 $B_j$ 自然要最小，不用在意符号。
考虑每个节点都维护它代表区间的答案。答案节点 $p$ 的答案 $ans(p)$ 由几种情况转移过来：
-
选择的三个下标 $i,j,k$ 完整地包含在左儿子或右儿子代表的区间内。则答案为 $ans(lson)$ 或 $ans(rson)$。
-
$i,j$ 在左儿子，$k$ 在右儿子。那么很容易发现 $k$ 只能取右儿子中的最大值。所以我们要维护 $A$ 数组的区间最大值。再看 $i,j$，我们要求 $A_i-B_j(i< j)$ 的最大值，这个也可以维护。
-
$i$ 在左儿子，$j,k$ 在右儿子。这个就是要多维护一个 $A_k-B_j(k>j)$ 的最大值。
上面提到要 维护 $A_i-B_j$ 的最大值($i<j$ 或 $i>j$) ，这个也可以像上面一样分类转移，就是考虑左右儿子的答案与一个左一个右。然后发现要再维护 $B_j$ 的最小值。
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int MAX_N = 5e5 + 10, INF = (1 << 30);
int n, m;
int a[MAX_N], b[MAX_N];
struct node {
int va, vb, dlr, drl, val;
node(int _va = -INF, int _vb = INF, int _dlr = -INF, int _drl = -INF, int _val = -INF) : va(_va), vb(_vb), dlr(_dlr), drl(_drl), val(_val) {}
} d[MAX_N << 2];
inline ll read() {...}
inline void write(ll x) {...}
inline int lc(int p) {return (p << 1);}
inline int rc(int p) {return (p << 1) | 1;}
inline int mid(int s, int t) {return s + ((t - s) >> 1);}
node U(node L, node R) {
node ret;
ret.va = max(L.va, R.va);
ret.vb = min(L.vb, R.vb);
ret.dlr = max(max(L.dlr, R.dlr), L.va - R.vb);
ret.drl = max(max(L.drl, R.drl), R.va - L.vb);
ret.val = max(max(L.val, R.val), max(L.dlr + R.va, R.drl + L.va));
return ret;
}
void build_tree(int s, int t, int p) {
if(s == t) {
d[p].va = a[s];
d[p].vb = b[s];
return;
}
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
d[p] = U(d[lc(p)], d[rc(p)]);
}
void update(int s, int t, int p, int x, int y, int type) {
if(s == t) {
if(type == 1) d[p].va = y;
else d[p].vb = y;
return;
}
int m = mid(s, t);
if(x <= m) update(s, m, lc(p), x, y, type);
else update(m + 1, t, rc(p), x, y, type);
d[p] = U(d[lc(p)], d[rc(p)]);
}
node query(int s, int t, int p, int l, int r) {
if(l <= s && t <= r) return d[p];
int m = mid(s, t);
node L, R;
if(l <= m) L = query(s, m, lc(p), l, r);
if(r > m) R = query(m + 1, t, rc(p), l, r);
return U(L, R);
}
signed main() {
n = read(), m = read();
for(int i = 1; i <= n; i++)
a[i] = read();
for(int i = 1; i <= n; i++)
b[i] = read();
build_tree(1, n, 1);
while(m--) {
int op = read(), x = read(), y = read();
if(op <= 2) update(1, n, 1, x, y, op);
else write(query(1, n, 1, x, y).val), putchar('\n');
}
return 0;
}
写这题时发现线段树的两种 query：
node query(int s, int t, int p, int l, int r) {
if(l <= s && t <= r) return d[p];
int m = mid(s, t);
node L, R;
if(l <= m) L = query(s, m, lc(p), l, r);
if(r > m) R = query(m + 1, t, rc(p), l, r);
return U(L, R);
}
node query(int s, int t, int p, int l, int r) {
if(l <= s && t <= r) return d[p];
int m = mid(s, t);
if(l > m) return query(m + 1, t, rc(p), l, r);
if(r <= m) return query(s, m, lc(p), l, r);
return U(query(s, m, lc(p), l, r), query(m + 1, t, rc(p), l, r));
}
如果要写前者，你的 U(L, R) 函数要满足当 L 或 R 只是初值时可以正常工作。后者则不需要这个性质。
The Child and Sequence
给定数列，区间查询和，区间取模，单点修改。
$n, m \leq 10^5$。
题解
均摊复杂度。和那个什么区间开方很像。
考虑对 $p$ 取模之后一定会变得比 $p$ 小。这相当于把所有大于 $2\cdot p$ 的数都缩小一倍以上。那么越取模数列就越趋向于变小。
所以顺便维护最大值，如果这个节点的最大值小于 $p$ 就不递归下去了。此外的话暴力取模。
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
int n, m, a[MAX_N];
struct node {
int sum, mx;
node(int _sum = 0, int _mx = 0) : sum(_sum), mx(_mx) {}
node operator + (const node &t) const {
node ret;
ret.mx = max(mx, t.mx), ret.sum = sum + t.sum;
return ret;
}
} d[MAX_N << 2];
inline ll read() {...}
inline void write(ll x) {...}
inline int lc(int p) {return (p << 1);}
inline int rc(int p) {return (p << 1) | 1;}
inline int mid(int s, int t) {return s + ((t - s) >> 1);}
inline void pu(int p) {d[p] = d[lc(p)] + d[rc(p)];}
void build_tree(int s, int t, int p) {
if(s == t) {
d[p].sum = d[p].mx = a[s];
return;
}
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
pu(p);
}
void update(int s, int t, int p, int l, int r, int x) {
if(d[p].mx < x) return;
if(s == t) {
d[p].sum %= x;
d[p].mx %= x;
return;
}
int m = mid(s, t);
if(l <= m) update(s, m, lc(p), l, r, x);
if(r > m) update(m + 1, t, rc(p), l, r, x);
pu(p);
}
void change(int s, int t, int p, int k, int x) {
if(s == t) {
d[p].sum = d[p].mx = x;
return;
}
int m = mid(s, t);
if(k <= m) change(s, m, lc(p), k, x);
else change(m + 1, t, rc(p), k, x);
pu(p);
}
int query(int s, int t, int p, int l, int r) {
if(l <= s && t <= r) return d[p].sum;
int m = mid(s, t), ret = 0;
if(l <= m) ret += query(s, m, lc(p), l, r);
if(r > m) ret += query(m + 1, t, rc(p), l, r);
return ret;
}
signed main() {
n = read(), m = read();
for(int i = 1; i <= n; i++)
a[i] = read();
build_tree(1, n, 1);
while(m--) {
int op = read();
if(op == 1) {
int l = read(), r = read();
write(query(1, n, 1, l, r)), putchar('\n');
}
else if(op == 2) {
int l = read(), r = read(), x = read();
update(1, n, 1, l, r, x);
}
else {
int k = read(), x = read();
change(1, n, 1, k, x);
}
}
return 0;
}
方差
操作 $1$：1 x y k ，表示将第 $x$ 到第 $y$ 项每项加上 $k$，$k$ 为一实数。
操作 $2$：2 x y ，表示求出第 $x$ 到第 $y$ 项这一子数列的平均数。
操作 $3$：3 x y ，表示求出第 $x$ 到第 $y$ 项这一子数列的方差。
$N\le 10^5, M\le 10^5$
题解
维护区间和、区间平方和即可。方差的另一个公式：
\[s^2 = \bar{x^2} - \bar{x}^2\]即平方的平均减平均的平方。
区间平方和在加 $k$ 的时候稍微推导一下:
\[\sum(x_i+k)^2=\sum x_i^2 + 2k\sum x_i + \sum k^2\]发现不需要维护额外的信息。
这个线段树尝试了不同的写法，感觉良好，可以成为习惯。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
int n, m;
double a[MAX_N];
struct node {
double sum1, sum2, tag;
int len;
node(double _sum1 = 0, double _sum2 = 0, double _tag = 0, int _len = 0) :
sum1(_sum1), sum2(_sum2), tag(_tag), len(_len) {}
node operator + (const node &t) const {
node ret;
ret.sum1 = sum1 + t.sum1;
ret.sum2 = sum2 + t.sum2;
ret.len = len + t.len;
return ret;
}
void operator += (double k) {
sum2 += 2 * k * sum1 + len * k * k;
sum1 += len * k;
}
} d[MAX_N << 2];
inline int lc(int p) {return (p << 1);}
inline int rc(int p) {return (p << 1) | 1;}
inline int mid(int s, int t) {return s + ((t - s) >> 1);}
inline void pd(int p) {
if(d[p].tag) {
d[lc(p)] += d[p].tag, d[rc(p)] += d[p].tag;
d[lc(p)].tag += d[p].tag, d[rc(p)].tag += d[p].tag;
d[p].tag = 0;
}
}
void build_tree(int s, int t, int p) {
if(s == t) {
d[p].sum1 = a[s];
d[p].sum2 = a[s] * a[s];
d[p].len = 1;
return;
}
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
d[p] = d[lc(p)] + d[rc(p)];
}
void update(int s, int t, int p, int l, int r, double k) {
if(l <= s && t <= r) {
d[p] += k;
d[p].tag += k;
return;
}
pd(p);
int m = mid(s, t);
if(l <= m) update(s, m, lc(p), l, r, k);
if(r > m) update(m + 1, t, rc(p), l, r, k);
d[p] = d[lc(p)] + d[rc(p)];
}
node query(int s, int t, int p, int l, int r) {
if(l <= s && t <= r) return d[p];
pd(p);
int m = mid(s, t);
node L, R;
if(l <= m) L = query(s, m, lc(p), l, r);
if(r > m) R = query(m + 1, t, rc(p), l, r);
return L + R;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%lf", &a[i]);
build_tree(1, n, 1);
while(m--) {
int op, x, y; double k, ans;
scanf("%d %d %d", &op, &x, &y);
if(op == 1) {
scanf("%lf", &k);
update(1, n, 1, x, y, k);
}
else {
node ret = query(1, n, 1, x, y);
ans = ret.sum1 / ret.len;
if(op == 3) ans = ret.sum2 / ret.len - ans * ans;
printf("%.4lf\n", ans);
}
}
return 0;
}
[USACO22FEB] Sleeping in Class B
$T$ 组数据，每组给定一个长度为 $N$ 的数组 $a_1, a_2, \dotsb , a_n$。
每次操作可选择两个相邻的数合并，得到的新数为两者之和。
求最少操作次数使得所有数相等。
$1 \leq T \leq 10$，$\sum a_i \leq 10^6$，$\sum N \leq 10^5$，$1 \le T \le 10$。
题解
我们考虑最终得到的数一定是 $\sum a_i$ 的因数。
所以 $O(\sqrt{\sum a_i})$ 枚举因数，然后扫一遍 $O(N)$ 暴力判断这个因数能不能被合并出来即可。
时间复杂度： $O(TN\sqrt{\sum{a_i}})$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10, INF = (1 << 30);
int a[MAX_N], n, sum, ans;
inline ll read() {...}
inline void write(ll x) {...}
void check(int x) {
int t = 0, cnt = 0;
for(int i = 1; i <= n; i++) {
t += a[i];
if(t == x) {
t = 0;
cnt++;
}
else if(t > x) return;
}
ans = min(ans, n - cnt);
}
int main() {
int T = read();
while(T--) {
n = read(), sum = 0, ans = INF;
for(int i = 1; i <= n; i++)
a[i] = read(), sum += a[i];
for(int i = 1; i * i <= sum; i++) {
if(sum % i == 0) {
check(i);
check(sum / i);
}
}
if(!sum) ans = 0;
write(ans), putchar('\n');
}
return 0;
}
[NOI2005] 维护数列
| 编号 | 名称 | 格式 | 说明 |
|---|---|---|---|
| 1 | 插入 | $\operatorname{INSERT}\ posi \ tot \ c_1 \ c_2 \cdots c_{tot}$ | 在当前数列的第 $posi$ 个数字后插入 $tot$ 个数字：$c_1, c_2 \cdots c_{tot}$；若在数列首插入，则 $posi$ 为 $0$ |
| 2 | 删除 | $\operatorname{DELETE} \ posi \ tot$ | 从当前数列的第 $posi$ 个数字开始连续删除 $tot$ 个数字 |
| 3 | 修改 | $\operatorname{MAKE-SAME} \ posi \ tot \ c$ | 从当前数列的第 $posi$ 个数字开始的连续 $tot$ 个数字统一修改为 $c$ |
| 4 | 翻转 | $\operatorname{REVERSE} \ posi \ tot$ | 取出从当前数列的第 $posi$ 个数字开始的 $tot$ 个数字，翻转后放入原来的位置 |
| 5 | 求和 | $\operatorname{GET-SUM} \ posi \ tot$ | 计算从当前数列的第 $posi$ 个数字开始的 $tot$ 个数字的和并输出 |
| 6 | 求最大子列和 | $\operatorname{MAX-SUM}$ | 求出当前数列中和最大的一段子列，并输出最大和 |
题解
FHQ-Treap 维护区间操作。
一旦涉及到区间翻转就必须要用平衡树了。
注意几个实现方面的细节：
-
动态开点要注意用栈进行回收利用。删除时把删除的节点加到栈里。
-
这题的最大子段和必须选一个数。所以要对这个点的 val 取 max。
-
可以实现一个函数来对数列建树。这样操作 1 就把新建的树 merge 到treap 上就行了，很方便。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e5 + 10, NUL = 1e9 + 7;
stack<int> sp;
struct node {
int sum, lmax, rmax, mx, cov;
bool rev;
int lc, rc, val, siz, rnd;
} d[MAX_N];
mt19937 rng(random_device{}());
int rt, n, m, x, y, z, a[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
inline int read_op() {...}
int new_node(int v) {
int cnt = sp.top(); sp.pop();
d[cnt].val = d[cnt].sum = d[cnt].mx = v;
d[cnt].siz = 1;
d[cnt].rnd = rng();
d[cnt].cov = NUL;
d[cnt].lc = d[cnt].rc = d[cnt].rev = 0;
d[cnt].lmax = d[cnt].rmax = max(0, v);
return cnt;
}
void pu(int u) {
if(!u) return;
int lc = d[u].lc, rc = d[u].rc;
d[u].siz = d[lc].siz + d[rc].siz + 1;
d[u].sum = d[lc].sum + d[rc].sum + d[u].val;
d[u].lmax = max(max(d[lc].lmax, d[lc].sum + d[u].val + d[rc].lmax), 0);
d[u].rmax = max(max(d[rc].rmax, d[rc].sum + d[u].val + d[lc].rmax), 0);
d[u].mx = max(d[u].val, d[lc].rmax + d[u].val + d[rc].lmax);
if(lc) d[u].mx = max(d[u].mx, d[lc].mx);
if(rc) d[u].mx = max(d[u].mx, d[rc].mx);
}
void reverse(int u) {
if(!u) return;
swap(d[u].lc, d[u].rc);
swap(d[u].lmax, d[u].rmax);
d[u].rev ^= 1;
}
void cover(int u, int v) {
if(!u) return;
d[u].val = d[u].cov = v;
d[u].sum = d[u].siz * v;
d[u].lmax = d[u].rmax = max(d[u].sum, 0);
d[u].mx = max(v, d[u].sum);
}
void pd(int u) {
if(!u) return;
if(d[u].rev) {
reverse(d[u].lc);
reverse(d[u].rc);
d[u].rev = 0;
}
if(d[u].cov != NUL) {
cover(d[u].lc, d[u].cov);
cover(d[u].rc, d[u].cov);
d[u].cov = NUL;
}
}
void del(int u) {
if(!u) return;
sp.push(u);
del(d[u].lc);
del(d[u].rc);
}
void split(int now, int k, int &x, int &y) {
if(!now) x = y = 0;
else {
pd(now);
if(d[d[now].lc].siz < k) x = now, split(d[now].rc, k - d[d[now].lc].siz - 1, d[now].rc, y);
else y = now, split(d[now].lc, k, x, d[now].lc);
pu(now);
}
}
int merge(int L, int R) {
if(!L || !R) return L + R;
if(d[L].rnd < d[R].rnd) {
pd(L);
d[L].rc = merge(d[L].rc, R);
pu(L);
return L;
}
else {
pd(R);
d[R].lc = merge(L, d[R].lc);
pu(R);
return R;
}
}
int create(int *A, int l, int r) {
if(l == r) return new_node(A[l]);
int mid = l + ((r - l) >> 1);
int L = create(A, l, mid), R = create(A, mid + 1, r);
return merge(L, R);
}
int main() {
for(int i = 1; i < MAX_N; i++)
sp.push(i);
n = read(), m = read();
for(int i = 1; i <= n; i++)
a[i] = read();
rt = create(a, 1, n);
while(m--) {
int op = read_op();
if(op == 1) {
int pos = read(), tot = read();
for(int i = 1; i <= tot; i++)
a[i] = read();
split(rt, pos, x, y);
x = merge(x, create(a, 1, tot));
rt = merge(x, y);
}
if(op == 2) {
int pos = read(), tot = read();
split(rt, pos - 1, x, y);
split(y, tot, y, z);
del(y);
rt = merge(x, z);
}
if(op == 3) {
int pos = read(), tot = read(), v = read();
split(rt, pos - 1, x, y);
split(y, tot, y, z);
cover(y, v);
rt = merge(merge(x, y), z);
}
if(op == 4) {
int pos = read(), tot = read();
split(rt, pos - 1, x, y);
split(y, tot, y, z);
reverse(y);
rt = merge(merge(x, y), z);
}
if(op == 5) {
int pos = read(), tot = read();
split(rt, pos - 1, x, y);
split(y, tot, y, z);
write(d[y].sum), putchar('\n');
rt = merge(merge(x, y), z);
}
if(op == 6) write(d[rt].mx), putchar('\n');
}
return 0;
}
哈希冲突
给定一个数列 $v$，支持两种操作：
-
将 $v_x$ 赋值为 $y$。
-
求 $\sum\limits_{i\bmod x=y} v_i$。
$n\leq 150000,m\leq 150000$.
题解
根号分治。
对于 $x\le \sqrt n$，预处理答案，时间复杂度 $O(\sqrt n)$。
对于 $x> \sqrt n$，暴力计算，时间复杂度 $O(\sqrt n)$。
总的时间复杂度 $O(n\sqrt n)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1.5e5 + 10, MAX_SIZ = 500;
int v[MAX_N], ans[MAX_SIZ][MAX_SIZ], n, m, siz;
inline ll read() {...}
inline void write(ll x) {...}
inline char read_op() {...}
int main() {
n = read(), m = read();
siz = pow(n, 0.15);
for(int i = 1; i <= n; i++)
v[i] = read();
for(int i = 1; i <= n; i++)
for(int p = 1; p <= siz; p++)
ans[p][i % p] += v[i];
while(m--) {
char op = read_op();
int x = read(), y = read();
if(op == 'A') {
if(x <= siz) write(ans[x][y]);
else {
int t = 0;
for(y; y <= n; y += x)
t += v[y];
write(t);
}
putchar('\n');
}
else {
for(int p = 1; p <= siz; p++)
ans[p][x % p] = ans[p][x % p] - v[x] + y;
v[x] = y;
}
}
return 0;
}
无向图三元环计数
给定一个 $n$ 个点 $m$ 条边的简单无向图，求其三元环个数。
题解
用度数小的点指向度数大的点，重构出 DAG。
然后打时间戳来判断是否能构成三元环。
时间复杂度 $O(m\sqrt m)$，相当于根号分治。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 2e5 + 10;
pii e[MAX_N];
int dg[MAX_N], to[MAX_N], ans;
vector<int> G[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), m = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read();
e[i] = make_pair(u, v);
dg[u]++, dg[v]++;
}
for(int i = 1; i <= m; i++) {
int u = e[i].first, v = e[i].second;
if(dg[u] > dg[v]) swap(u, v);
if(dg[u] == dg[v] && u > v) swap(u, v);
G[u].pb(v);
}
for(int u = 1; u <= n; u++) {
for(int v : G[u])
to[v] = u;
for(int v : G[u])
for(int w : G[v])
if(to[w] == u) ans++;
}
write(ans);
return 0;
}
♥