## 排队
#枚举 #数学
> [!note] 思路
>
> 首先考虑如何支持等差，不难想到枚举差 $k$ 然后在此方差的情况下选择修改次数最小的方案。由于它规定了值域是 $[1,w]$，而方差为 $k$ 时目标 $a_n$ 至少为 $1+(n-1)k$，所以枚举上界就是 $k=\left\lfloor\cfrac{w-1}{n-1}\right\rfloor$。这个枚举时间复杂度 ${} \mathcal O\left(\cfrac{w}{n}\right) {}$。
>
> 对于第 $i$ 个元素，我们生成基准目标元素 $a_i=1+(i-1)k$，那么需要将原始 $a$ 修改成和基准目标元素每个差值相同的（保证插值 $k$）。具体来说，选择与基准元素差值相同数量最多的，最后需要修改的数量就越少。
>
> 这个检查是 $\mathcal O(n)$ 线性的。但是由于需要用到负数下标，我使用了 `map`。
> [!attention] 注意
>
> 需要特别注意第一个元素和最后一个元素，不能超过 $[1,w]$。
>
> > [!bug] Hack 数据
> > 对于 $n=4,m=7$，有 $a=(2,4,6,7)$。
> >
> > 答案是 $2$ 不是 $1$，因为最后一个元素无法别改成 $8$。
时间复杂度 $\mathcal O\left(\cfrac{w}{n}\times n\log_2 n\right)=\mathcal O\left(w\log_2 n\right)$。
```cpp
const LL kMaxN = 3e5 + 5;
LL a[kMaxN], n, m, ans = 1e18;
map<LL, LL> f;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
}
for (LL k = 0; 1 + (n - 1) * k <= m; k++) {
f.clear();
for (LL i = 1; i <= n; i++) {
int d = 1 + (i - 1) * k - a[i];
if (1 - d >= 1 && 1 + (n - 1) * k - d <= m) {
f[d]++;
}
}
for (auto i : f) {
ans = min(ans, n - i.second);
}
}
cout << ans << '\n';
return 0;
}
```
## 攀比
#结论 #找规律
> [!note] 思路
>
> 这道题目有多个询问，这代表着我们可能需要 $\mathcal O(\log)$ 级别求出单次询问的答案。
>
> 首先考虑找规律/猜结论。对于一个点 $x$，我们删掉之后这个连通块会变成多少个呢？当然是 $d_x$ 个；然而，由于 $x$ 是之前更小的点删去后分出来的连通块的新的最小点，所以实际上是变成 $d_x-1$ 个，但是对于一个初始连通块本身就有一个。所以答案就是连通块数量+$\sum \max(0,d_i-1)$……吗？
>
> 随便画一个不是树的连通块，就发现一个点删掉之后并不会出现 $d_x-1$ 个连通块。现在我们知道从连通块个数的增加上考虑思路有点困难了，不如直接考虑最后不被删除需要什么条件。
>
> 思考两年半，我们可以得知一个节点如果最后会留下来，那么它的邻居节点的编号一定均小于它，因为如果有大于它的它就会因为存在于一个大小大于 $1$ 的连通块中删除。
>
> 所以我们直接用 `set` 动态维护每个节点的邻点编号，动态计算答案即可。
时间复杂度 $\mathcal O(q\log_2 n)$，当然可以通过标记的方式去掉 `set` 的 $\log$。
```cpp
const int kMaxN = 1e5 + 5;
int n, m, q, ans;
set<int> e[kMaxN];
bool check(int x) {
return e[x].empty() || *e[x].rbegin() < x;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e[u].insert(v);
e[v].insert(u);
}
for (int i = 1; i <= n; i++) {
ans += check(i);
}
cin >> q;
for (int o, u, v; q; q--) {
cin >> o;
if (o == 1) {
cin >> u >> v;
ans -= check(u);
ans -= check(v);
e[u].insert(v);
e[v].insert(u);
ans += check(u);
ans += check(v);
} else if (o == 2) {
cin >> u >> v;
ans -= check(u);
ans -= check(v);
e[u].erase(v);
e[v].erase(u);
ans += check(u);
ans += check(v);
} else {
cout << ans << '\n';
}
}
return 0;
}
```
## 排排队
#暴力 #找规律 #结论 #前缀和
> [!important] 重点
>
> 这种题目又出现了，就是优化枚举。普通的暴力枚举肯定过不了，但是对于大多数情况都不可能造成最优解的，直接不考虑。
> [!note] 思路
>
> 若干次合并相邻的两个元素可以看作区间合并为一个，于是想到异或前缀和，这样就可以 $\mathcal O(1)$ 求出区间异或和了。
>
> 一个显而易见的结论是：
>
> - [n] 我们只会进行区间合成最多两次，因为只需要构造一对逆序的。
>
> 于是可以想出时间复杂度为 $\mathcal O(n^3)$ 的暴力，即枚举左端点 $i$ 和右端点 $j$，中间枚举 $k$ 让 $[i,k]$ 的合并，$[k+1,j]$ 的合并，满足的要求就是 $p_k\oplus p_{i-1}=p_j\oplus p_{k}$。答案取 $\min(j-i-1)$。
>
> 对于 $n>400$，直接输出 $1$。此时就可以直接获得 $100$ 分了。
>
> > [!question] 疑问
> > 为什么这样做是对的呢？怎么想到的？具体的边界真的是 $400$ 还是其它？
>
> > [!tldr] 证明
> >
> > 实际上边界是 $60$。
> >
> > 对于 $3$ 个相邻的数，如果它们最高 $1$ 位是相同的，那么前两个异或之后这一位就没有了，所以答案是 $1$。
> >
> > 为了避免这种情况，我们需要构造相邻 $3$ 个数最高位均不同的，但是最高位不能单调递减（这样本身答案就是 $0$ 了）。所以最好的构造方案是每个数位作为最高位构造两个数，最高数位单调递增。这样子就是 $60$ 个数了。大于 $60$ 必然崩盘，答案就为 $1$。
>
> 我的做法更奇特。没有钦定对于 $n>60$ 答案一定为 $1$，因为不保险。我钦定答案不会超过 $2\times 30=60$，所以对于每个 $i$，$j$ 只枚举往后最多 $60$ 个。
>
> > [!attention] 注意
> >
> > 这种做法的运算量高达 $7.2\times 10^8$，需要配合最优性剪枝才能通过。当然忽略常数时间复杂度 $\mathcal O(n)$。
这是我的做法。
```cpp
const int kMaxN = 2e5 + 5;
int p[kMaxN], a[kMaxN], t, n, ans;
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
p[i] = p[i - 1] ^ a[i];
}
ans = 1e9;
for (int i = 1; i <= n; i++) {
for (int j = i + 2; j <= min(n, i + 60); j++) {
if (j - i - 1 >= ans) {
break;
}
for (int k = i; k < j; k++) {
if ((p[k] ^ p[i - 1]) > (p[j] ^ p[k])) {
ans = j - i - 1;
}
}
}
}
cout << (ans != 1e9 ? ans : -1) << '\n';
}
return 0;
}
```
## 南斯拉夫
#深度优先搜索 #广度优先搜索 #并查集
> [!note] 思路
>
> 我采用的暴力。
>
> 首先可以看作二选一，每个元素最后必须被选偶数次，于是 DFS 暴搜 $\mathcal O(2^mn)$，$\mathcal O(n)$ 判断优化为 $\mathcal O(m)$ 判断后直接获得 $40$ 分。