学术版。
9.9
P4117 [Ynoi2018] 五彩斑斓的世界
分块神题。
拿到题以后发现不能直接做，然后你就开始观察。
设区间最大值为 \(maxn\) ,查询的数为 \(x\)
一个显然的性质：
- 把所有小于等于 \(x\) 的数加上 \(x\) ，然后区间减 \(x\) ，得到的结果不变。
然后我们思考一下，发现有一个比较套路的对区间数的情况进行分讨，这个分讨非常妙妙
- 定义一个删除标记 \(del\) ，如果 \(2x<=maxn\) ，那么直接按照上面的性质处理，再把标记加 \(x\)
- 否则我们直接按题意修改。
为什么是对的？因为每次操作之后显然元素差值不断变小，那么我们发现它实质上次数是 \(O(n)\) 的，它就非常对。
然后我们发现这个暴力修改的操作太蠢了，想想什么能快速统计相同值，啊就是并查集。这时候我们每次只需要修改 \(root\) 上的值就可以了，相同数个数只需要维护一个 \(siz\) ，因为这里并查集没有路径压缩，而是直接并入了另一个集合，所以我们就实现了 \(O(1)\) 修改。对于部分修改可以暴力重构， \(O(\sqrt n)\) 即可。
考虑查询操作，这时候就显而易见的简单了，整块查询直接返回 \(siz\) ,部分就再使用一个路径压缩的并查集查询当前位置的实际值，这部分也是 \(O(n)\) 的。
东拼西凑总时间复杂度 \(O(n \sqrt n)\) ，你现在可以通过弱化版
CF896E Welcome home, Chtholly 了。
最抽象的是这题空间只有 64MB ，直接爆炸。我们巧思一下，很明显块与块直接根本没有影响，这样我们可以把询问离线，对于每个块进行操作，这样只需要 \(O(\sqrt n)\) 的空间就可以完美实现。
注意 hack 数据是针对 \(0\) 的，额外处理一下即可，稍微卡卡常。
然后你就通过了 突刺贯穿第二分块 ！
代码太丑了不放了。
CF1779E Anya's Simultaneous Exhibition
据说是竞赛图套路题。
懒得写了，直接搬题解
点击查看代码
#include <bits/stdc++.h>
const int N = 305;
using namespace std;
int in[N], id[N], ans[N];
signed main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cout << '?' << ' ' << i << ' ';for (int j = 1; j <= n; j++)cout << (i == j ? 0 : 1);cout << endl;cin >> in[i];in[i] = n - 1 - in[i];id[i] = i;}sort(id + 1, id + n + 1, [](int x, int y){ return in[x] < in[y]; });int sum = 0;for (int i = 1; i <= n; i++){sum += in[id[i]];if (sum == i * (i - 1) / 2){for (int j = 1; j <= i; j++)ans[id[j]] = 1;break;}}cout << "! ";for (int i = 1; i <= n; i++)cout << ans[i];cout << endl;
}