二分图的概念很简单，就是将点分成两个集合，且每条边连接的两个点属于不同的集合，比较常见的判断一个图是否为二分图的方式是染色法，即对于每个还没染色的点进行搜索，对于当前点，检查其邻点：
- 如果已经染色且与当前点相同，那么这个图就不是二分图；
- 如果已经染色且与当前点不同，那么继续检查；
- 如果尚未染色，则染成与当前点不同的颜色，并进入该点继续搜索；
代码模板如下：
// 染色法判定二分图
bool DyeCheckBipartite(vector<vector<int>> &g) {
int n = static_cast<int>(g.size());
vector<int> color(n, -1);
function<bool(int, int)> dye = [&](int u, int c) -> bool {
if (color[u] != -1) {
return color[u] == c;
}
color[u] = c;
for (auto &v : g[u]) {
if (!dye(v, c ^ 1)) {
return false;
}
}
return true;
};
for (int i = 0; i < n; i++) {
if (color[i] == -1 && !dye(i, 0)) {
return false;
}
}
return true;
}
这里分享一种并查集的做法，在某些情况使用起来会更加方便，思路如下：
- 先将每个点拆成两个点，分别表示该点为黑色和白色的状态，表示为 $v_0$ 和 $v_1$ ；
- 建图连边时，如果一条边连接的是 $(u, v)$ ，那么就将 $u_0$ 和 $v_1$ 合并，以及将 $u_1$ 和 $v_0$ 合并；
- 所有边连接完成后，如果存在某个点 $v$ ，它的 $v_0$ 和 $v_1$ 在同一个集合，那么它就不是二分图。
代码模板如下：
bool DsuCheckBipartite(vector<vector<int>> &g) {
int n = static_cast<int>(g.size());
// 并查集
Dsu d(2 * n);
for (int u = 0; u < n; u++) {
for (auto &v : g[u]) {
d.unite(u, v + n);
d.unite(u + n, v);
}
}
for (int i = 0; i < n; i++) {
if (d.get(i) == d.get(i + n)) {
return false;
}
}
return true;
}
如果要求一组合法的染色方案，可以像这样：
// color 数组为一组方案
vector<int> color(n, -1);
vector<bool> used(2 * n, false);
for (int i = 0; i < n; i++) {
if (!used[d.get(i)] && !used[d.get(i + n)]) {
// i 点所在集合还没染过，令 i 点为 0 即可
color[i] = 0;
used[d.get(i)] = true;
} else if (used[d.get(i)]) {
// i 点为 0 的状态已经存在
color[i] = 0;
} else if (used[d.get(i + n)]) {
// i 点为 1 的状态已经存在
color[i] = 1;
} else {
assert(false);
}
}
下面这道题就可以用到这种方法，后面还有几道最近做的觉得还挺有意思的题目，一起放上来吧。
D. X(or)-mas Tree
题目链接： D. X(or)-mas Tree
题意：
给定一棵树，对于某些边，给定一个数，其它边的数暂时丢失，再给定一些要求，每个要求给定两个点，以及这两点之间的路径上所有边的数异或和在二进制表示下 $1$ 的个数是奇数还是偶数，问是否能够将丢失的数补全以满足所有要求。
解题思路：
题意看起来有些绕，但实际上，由于计算是异或，且要求是异或和在二进制下 $1$ 的个数的奇偶性，因此数值是多少并不重要，如果一条边的数值在二进制下 $1$ 的个数是奇数，将这个数值替换成 $1$ ，否则替换成 $0$ ，也是符合题意的。
然后题目要求我们做的事情，实际上就是将这个图构造成一个二分图，但这个图上的边并只不是这棵树的边，而是以下几种边：
- 对于树上的边，如果数值是 $1$ ，这条边上的两个点应该属于两个不同的集合；
- 对于树上的边，如果数值是 $0$ ，这条边上的两个点应该属于同一个集合；
- 对于每个要求，如果异或和在二进制下 $1$ 的个数为 $1$ ，那么 $a,b$ 属于两个不同的集合；
- 对于每个要求，如果异或和在二进制下 $1$ 的个数为 $0$ ，那么 $a,b$ 属于同一个集合；
对于这样一个新的图，判断是否为二分图即可。
最后，题目要求是补全边上丢失的数值，因此判断树上所有边的两个点是否属于同一个集合即可。
染色法代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
vector<int> x(n - 1);
vector<int> y(n - 1);
vector<int> v(n - 1);
for (int i = 0; i < n - 1; i++) {
cin >> x[i] >> y[i] >> v[i];
--x[i];
--y[i];
if (v[i] != -1) {
int c = (int) __builtin_popcount(v[i]);
g[x[i]].emplace_back(y[i], c & 1);
g[y[i]].emplace_back(x[i], c & 1);
}
}
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
--a;
--b;
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
bool flag = true;
vector<int> color(n, -1);
function<bool(int, int)> dye = [&](int u, int c) -> bool {
if (color[u] != -1) {
return color[u] == c;
}
color[u] = c;
for (auto &[v, t] : g[u]) {
if (!dye(v, c ^ t)) {
return false;
}
}
return true;
};
for (int i = 0; i < n; i++) {
if (color[i] == -1 && !dye(i, 0)) {
flag = false;
break;
}
}
if (!flag) {
cout << "NO\n";
continue;
}
cout << "YES\n";
for (int i = 0; i < n - 1; i++) {
if (v[i] == -1) {
if (color[x[i]] == color[y[i]]) {
v[i] = 0;
} else {
v[i] = 1;
}
}
cout << x[i] + 1 << ' ' << y[i] + 1 << ' ' << v[i] << '\n';
}
}
return 0;
}
并查集代码：
#include <bits/stdc++.h>
using namespace std;
class Dsu {
public:
vector<int> p, sz;
int n;
Dsu(int _n) {
n = _n + 1;
p.resize(n);
sz.assign(n, 1);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
return true;
}
return false;
}
inline int getSize(int x) {
return sz[get(x)];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<int> x(n - 1);
vector<int> y(n - 1);
vector<int> v(n - 1);
Dsu d(2 * n);
for (int i = 0; i < n - 1; i++) {
cin >> x[i] >> y[i] >> v[i];
--x[i];
--y[i];
if (v[i] != -1) {
int c = (int) __builtin_popcount(v[i]);
if (c & 1) {
d.unite(x[i], y[i] + n);
d.unite(x[i] + n, y[i]);
} else {
d.unite(x[i], y[i]);
d.unite(x[i] + n, y[i] + n);
}
}
}
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
--a;
--b;
if (c & 1) {
d.unite(a, b + n);
d.unite(a + n, b);
} else {
d.unite(a, b);
d.unite(a + n, b + n);
}
}
bool flag = true;
for (int i = 0; i < n; i++) {
flag &= (d.get(i) != d.get(i + n));
}
if (!flag) {
cout << "NO\n";
continue;
}
cout << "YES\n";
vector<int> color(n, -1);
vector<bool> used(2 * n, false);
for (int i = 0; i < n; i++) {
if (!used[d.get(i)] && !used[d.get(i + n)]) {
color[i] = 0;
used[d.get(i)] = true;
} else if (used[d.get(i)]) {
color[i] = 0;
} else if (used[d.get(i + n)]) {
color[i] = 1;
} else {
assert(false);
}
}
for (int i = 0; i < n - 1; i++) {
if (v[i] == -1) {
if (color[x[i]] == color[y[i]]) {
v[i] = 0;
} else {
v[i] = 1;
}
}
cout << x[i] + 1 << ' ' << y[i] + 1 << ' ' << v[i] << '\n';
}
}
return 0;
}
F - Swap and Sort
题目链接： F - Swap and Sort
题意：
给定一个排列以及多种操作，每种操作可以将两个位置的数交换，问是否能在最多操作 $5\times 10^5$ 次的情况下将排列按升序排列，并给出操作顺序。
解题思路：
首先判断在没有次数限制的情况下是否能够将它排序，对于每种操作，用并查集将两个位置合并到一个集合，对于某个位置的数 $a_i$ ，如果 $a_i$ 和 $i$ 不在一个集合上，说明 $a_i$ 无法到 $i$ ，也就无法排序了。否则一定可以，因为在最坏情况下，操作次数是 $1+2+\dots +n-1 \leq 5\times 10^5$ 。
在构造操作顺序时，要注意，可以把所有操作看作边，对于一条边，如果两个点已经属于同一个集合，那么可以忽略这条边，也就是说每个集合其实都是一棵树，然后从叶子开始处理，直到这棵树所有数都在最终的位置。
代码如下：
#include <bits/stdc++.h>
using namespace std;
class Dsu {
public:
vector<int> p, sz;
int n;
Dsu(int _n) {
n = _n + 1;
p.resize(n);
sz.assign(n, 1);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
return true;
}
return false;
}
inline int getSize(int x) {
return sz[get(x)];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> p(n);
for (auto &u : p) {
cin >> u;
--u;
}
int m;
cin >> m;
Dsu d(n);
vector<int> a(m);
vector<int> b(m);
vector<int> deg(n);
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
cin >> a[i] >> b[i];
--a[i];
--b[i];
if (d.get(a[i]) != d.get(b[i])) {
d.unite(a[i], b[i]);
g[a[i]].emplace_back(b[i], i);
g[b[i]].emplace_back(a[i], i);
deg[a[i]]++;
deg[b[i]]++;
}
}
for (int i = 0; i < n; i++) {
if (d.get(i) != d.get(p[i])) {
cout << "-1\n";
return 0;
}
}
vector<int> leaves;
for (int i = 0; i < n; i++) {
if (deg[i] == 1) {
leaves.emplace_back(i);
}
}
vector<int> res;
for (int ll = 0; ll < (int) leaves.size(); ll++) {
int leaf = leaves[ll];
vector<int> path;
function<bool(int, int)> dfs = [&](int u, int fa) -> bool {
if (p[u] == leaf) {
return true;
}
for (auto &[v, id] : g[u]) {
if (v != fa) {
path.emplace_back(id);
if (dfs(v, u)) {
return true;
}
path.pop_back();
}
}
return false;
};
dfs(leaf, -1);
reverse(path.begin(), path.end());
for (auto &u : path) {
swap(p[a[u]], p[b[u]]);
res.emplace_back(u);
}
for (auto &[u, id] : g[leaf]) {
if (--deg[u] == 1) {
leaves.emplace_back(u);
}
}
}
cout << (int) res.size() << '\n';
for (auto &u : res) {
cout << u + 1 << ' ';
}
cout << '\n';
return 0;
}
F - Simple Operations on Sequence
题目链接： F - Simple Operations on Sequence
题意：
给定两个序列 $a,b$ ，可以以任意顺序进行无限次以下两种操作：
- 花费 $x$ 将 $a_i$ 增加或减少 $1$ ；
- 花费 $y$ 将 $a_i$ 和 $a_{i+1}$ 交换。
要使得两个序列相等，要最小花费。
解题思路：
这是一类典型的题目，思路是规定先进行第二种操作，然后进行第一种，但复杂度不允许进行枚举所有顺序，因此要想办法优化。
这里的做法是逐个排列一个新的数组，定义 $f[mask]$ ，表示在 $mask$ 中，是 $1$ 的位置表示已经加入了数组后面的所有方案，属性是花费的最小值。
转移时，枚举 $mask$ 中的 $0$ ，将其加入到 $mask$ 中，假如这个 $0$ 在原来的 $a$ 数组第 $bit$ 个数，当前 $mask$ 中有 $j$ 个 $1$ ，那么进行第一种操作的花费是 $|b[j+1]-a[bit]|$ 。第二种操作的花费就比较巧妙了，由于它是交换相邻两个数，要求花费，就要求交换的次数，这不就是逆序对的定义吗？只需要求出第 $bit$ 位前有多少个 $0$ ，这就是 $bit$ 移动到当前位置需要交换的次数，乘以 $y$ 即可更新下一个状态。
注意事项：
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
long long x, y;
cin >> n >> x >> y;
vector<long long> a(n);
for (auto &u : a) {
cin >> u;
}
vector<long long> b(n);
for (auto &u : b) {
cin >> u;
}
auto GetInv = [&](int mask, int x) -> int {
// 求 mask 中 x 位之前有多少个 0
int res = 0;
for (int bit = 0; bit < n; bit++) {
if (((mask >> bit) & 1) == 0 && bit < x) {
++res;
}
}
return res;
};
vector<long long> f(1 << n, (long long) 4e18);
f[0] = 0;
for (int cur = 0; cur < 1 << n; cur++) {
int j = (int) __builtin_popcount(cur);
for (int bit = 0; bit < n; bit++) {
if (((cur >> bit) & 1) == 0) {
int nxt = (cur | (1 << bit));
f[nxt] = min(f[nxt], f[cur] + abs(b[j] - a[bit]) * x + GetInv(cur, bit) * y);
}
}
}
cout << f.back() << '\n';
return 0;
}
D. Shuffle
题目链接： D. Shuffle
题意：
给定一个 $01$ 串，选择任意一个有恰好 $k$ 个 $1$ 的子段，将子段任意排列，做恰好一次这样的操作，问可能有多少种结果。
解题思路：
如果整个串 $1$ 的个数不超过 $k$ ，那么一次都不能操作。
否则，可以枚举两个端点 $[i,j]$ ，表示当前选择的子段， $i$ 为最左边出现变化的位置， $j$ 为最右边出现变化的位置，假如它们之间有 $ones$ 个 $1$ ，这两个位置改变后，如果 $s_i=0$ ， $ones$ 要减去 $1$ ，如果 $s_j=0$ ， $ones$ 也要减去 $1$ ，对于剩下的 $len=j-i-1$ 的位置，要放置 $ones$ 个 $1$ ，也就是 $C_{len}^{ones}$ 。
当然 $[i,j]$ 要满足 $[i,j]$ 之间的 $1$ 的个数要小于等于 $k$ ，这里可以暴力算也可以用前缀和。
注意事项：
记得加上操作后与原来相同的情况，也就是 $1$ 。
代码如下：
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 998244353;
// assume -mod <= x < 2 * mod
int norm(int x) {
if (x < 0) {
x += mod;
}
if (x >= mod) {
x -= mod;
}
return x;
}
template<typename T, typename U>
T qp(const T &a, const U &b) {
assert(b >= 0);
T res = 1, x = a;
U p = b;
for (; p; p /= 2, x *= x) {
if (p % 2) {
res *= x;
}
}
return res;
}
class Mint {
public:
int x;
Mint(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Mint operator-() const {
return Mint(norm(mod - x));
}
Mint inv() const {
assert(x != 0);
return qp(*this, mod - 2);
}
Mint &operator*=(const Mint &rhs) {
x = (int) ((long long) x * rhs.x % mod);
return *this;
}
Mint &operator+=(const Mint &rhs) {
x = norm(x + rhs.x);
return *this;
}
Mint &operator-=(const Mint &rhs) {
x = norm(x - rhs.x);
return *this;
}
Mint &operator/=(const Mint &rhs) {
return *this *= rhs.inv();
}
friend Mint operator*(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res *= rhs;
return res;
}
friend Mint operator+(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res += rhs;
return res;
}
friend Mint operator-(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res -= rhs;
return res;
}
friend Mint operator/(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res /= rhs;
return res;
}
};
vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);
Mint C(int n, int k) {
if (k < 0 || k > n) {
return 0;
}
while ((int) fact.size() < n + 1) {
fact.push_back(fact.back() * (int) fact.size());
inv_fact.push_back(1 / fact.back());
}
return fact[n] * inv_fact[k] * inv_fact[n - k];
}
Mint Fact(int n) {
assert(n >= 0);
while ((int) fact.size() < n + 1) {
fact.push_back(fact.back() * (int) fact.size());
inv_fact.push_back(1 / fact.back());
}
return fact[n];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, k;
string s;
cin >> n >> k >> s;
vector<int> pre(n + 1);
for (int i = 0; i < n; i++) {
pre[i + 1] = pre[i] + (int) (s[i] - '0');
}
Mint res = 1;
if (pre[n] >= k) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int ones = pre[j + 1] - pre[i];
if (ones <= k) {
ones -= (int) (s[i] == '0');
ones -= (int) (s[j] == '0');
int len = j - i - 1;
res += C(len, ones);
}
}
}
}
cout << res.val() << '\n';
return 0;
}
F - Make Bipartite
题目链接： F - Make Bipartite
题意：
给定一个 $n+1$ 个点的图，对于所有 $i=1,2,\dots ,n$ ，都有一条权值为 $a_i$ 的边 $(0,i)$ ，对于所有 $i=1,2,\dots,n$ ，都有一条权值为 $b_i$ 的边 $(a_i,a_{i+1})$ ，$n+1$ 表示为 $1$ 。
要删掉一些边使得这个图成为一个二分图，问删掉的边权值和最小是多少。
解题思路：
这里用染色法构造二分图，规定点 $0$ 为白色，然后定义 DP 数组 $f[i,j,k]$ 表示只看前 $i$ 个点， $i$ 为 $j$ 色，点 $1$ 为 $k$ 色的所有方案，其中 $0$ 表示白色， $1$ 表示黑色，属性为要删去的边的最小权值和。
转移时，对于 $f[i,j,k]$ ，枚举 $nj$ ，如果 $nj$ 和 $j$ 不同，则 $i$ 和 $i+1$ 之间的边可以留下，如果 $nj$ 不为白色，则 $i+1$ 和点 $0$ 之间的边可以留下，否则要加上相应的权值。
最后枚举 $f[n][j][k]$ ，用点 $n$ 和点 $1$ 的状态去更新答案。
这道题有一定的启发性，就是虽然它是一个环，其实也可以用线性的处理方式，最后特判一下环的首尾即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (auto &u : a) {
cin >> u;
}
vector<int> b(n);
for (auto &u : b) {
cin >> u;
}
const long long INF = (long long) 4e18;
vector<vector<vector<long long>>> f(n + 1, vector<vector<long long>>(2, vector<long long>(2, INF)));
f[1][0][0] = a[0];
f[1][1][1] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
for (int nj = 0; nj < 2; nj++) {
long long w = f[i][j][k];
if (nj == 0) {
w += a[i];
}
if (j == nj) {
w += b[i - 1];
}
f[i + 1][nj][k] = min(f[i + 1][nj][k], w);
}
}
}
}
long long res = INF;
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
long long w = f[n][j][k];
if (j == k) {
w += b[n - 1];
}
res = min(res, w);
}
}
cout << res << '\n';
return 0;
}
D - Checker
题目链接： D - Checker
题意：
建议直接看原题。
解题思路：
将所有坐标对 $2k$ 取模，这个图可以转换成 $2k\times 2k$ 的网格图，且不改变每个格子的颜色。
对于黑白点，求出整个网格的黑白点前缀和，然后枚举一个白色正方形的角，求白色区域内白色点个数，以及黑色区域内黑色点个数，两个颜色还要取反，同样计算一次，用这两个数更新答案即可。
注意事项：
细心找坐标。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int m, k;
cin >> m >> k;
int n = 2 * k;
vector<vector<vector<int>>> pre(2, vector<vector<int>>(n + 1, vector<int>(n + 1)));
for (int i = 0; i < m; i++) {
int x, y;
char c;
cin >> x >> y >> c;
x %= n;
y %= n;
pre[(c == 'W' ? 0 : 1)][x + 1][y + 1] += 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
pre[0][i][j] += pre[0][i - 1][j] + pre[0][i][j - 1] - pre[0][i - 1][j - 1];
pre[1][i][j] += pre[1][i - 1][j] + pre[1][i][j - 1] - pre[1][i - 1][j - 1];
}
}
auto Get = [&](int c, int x1, int y1, int x2, int y2) -> int {
if (x1 >= 1 && x1 <= x2 && x2 <= n && y1 >= 1 && y1 <= y2 && y2 <= n) {
return pre[c][x2][y2] - pre[c][x1 - 1][y2] - pre[c][x2][y1 - 1] + pre[c][x1 - 1][y1 - 1];
}
return 0;
};
int res = 0;
for (int x2 = k; x2 <= n; x2++) {
for (int y2 = k; y2 <= n; y2++) {
int ans = 0;
int x1 = x2 - k + 1;
int y1 = y2 - k + 1;
ans += Get(0, x1, y1, x2, y2);
ans += Get(0, 1, 1, x1 - 1, y1 - 1);
ans += Get(0, 1, y2 + 1, x1 - 1, n);
ans += Get(0, x2 + 1, y2 + 1, n, n);
ans += Get(0, x2 + 1, 1, n, y1 - 1);
ans += Get(1, x1, 1, x2, y1 - 1);
ans += Get(1, 1, y1, x1 - 1, y2);
ans += Get(1, x1, y2 + 1, x2, n);
ans += Get(1, x2 + 1, y1, n, y2);
res = max(res, ans);
// 当前颜色取反后的情况
res = max(res, m - ans);
}
}
cout << res << '\n';
return 0;
}
D. Keep the Average High
题目链接： D. Keep the Average High
题意：
给定一个序列，求最多可以选择多少个数，使得对于每个长度大于 $1$ 的子段满足以下至少一个条件：
- 子段中存在没有被选择的数；
- 子段的平均值大于等于一个定值 $x$ 。
解题思路：
手算样例发现了一个 trick ，那就是先找到所有平均值小于 $x$ 的子段，然后对这些子段进行区间选点的贪心即可，但是子段可能会很多，进而又发现只需要看长度为 $2$ 或 $3$ 的子段即可，不过很严谨的证明我还没想出来 hh 。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<long long> a(n);
for (auto &u : a) {
cin >> u;
}
long long x;
cin >> x;
vector<long long> pre(n + 1);
for (int i = 0; i < n; i++) {
pre[i + 1] = pre[i] + a[i];
}
vector<pair<int, int>> seg;
for (int len = 2; len <= 3; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if (pre[j] - pre[i - 1] < len * x) {
seg.emplace_back(i, j);
}
}
}
int m = (int) seg.size();
vector<int> order(m);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return seg[i].second < seg[j].second;
});
int cnt = 0;
int last = (int) -2e9;
for (auto &i : order) {
if (seg[i].first > last) {
last = seg[i].second;
++cnt;
}
}
cout << n - cnt << '\n';
}
return 0;
}
