闲话
闲话【碎片】(2/?)
这时候是不是该写历年省选真题了？
怎么这些天闲话阅读量低迷啊？
是不是没有多项式就没人看啊？
杂题
给定一张 \(n\) 个点 \(m\) 条边的无向连通图 \(G_0 = (V_0, E_0)\)，点集 \(V_0\) 中编号为 \(i\) 的点有颜色 \(c_i(1\le c_i\le 3)\)。
定义 \(G_{i - 1} = (V_{i - 1}, E_{i - 1})\) 的拓张生成了 \(G_i = (V_i, E_i)\)，\(G_i\) 定义如下：
- 对每个点 \(s\in V_{i - 1}\)，\(V_i\) 中都包含两个与 \(s\) 颜色相同的点 \(s_1, s_2\)。\(s_1, s_2\) 间的连边 \((s_1, s_2) \in E_i\)。
- 对每条边 \((s, t) \in E_{i - 1}\)：若 \(s, t\) 颜色相同，则 \((s_1, t_1), (s_2, t_2) \in E_i\)；反之 \((s_1, t_2), (s_2, t_1) \in E_i\)。
定义一张无向连通图的直径为图上任意两点间最短路的最大长度。
给定 \(k\)，求 \(G_k\) 的直径。
\(2\le n\le 100, \ 0\le k\le 100, \ n - 1\le m\le n(n - 1) / 2\)。
这是 *2500？
首先需要刻画 \(G_k\) 的形态。
节点 \(u\in V_0\) 在 \(G_0\to G_k\) 的过程中被倍增地复制，因此我们可以用所有长度为 \(k\) 的二进制串 \(b\) 来标明 \(G_k\) 中 \(u\) 对应的 \(2^k\) 个节点，对一个特定的串 \(b\)，记它指代的节点为 \([u, b]\)。例如 \([u, \texttt{001}]\) 指代了 \(((u_1)_2)_2\)。在有上下文的情况下不声明二进制串的长度。
对 \(u\in V_0\) 倍增得到的 \(2^k\) 个 \(G_k\) 中的节点，有以下性质：假设有两个节点 \([u, b_1], [u, b_2]\in V_{k}\)，则 \([u, b_1]\) 和 \([u, b_2]\) 有连边当且仅当二进制串 \(b_1, b_2\) 之间的汉明距离 \(\Delta(b_1, b_2)\) 为 \(1\)。这不难通过归纳法证明。
对一条边 \((u, v)\in E_0\)，假设 \(u, v\) 的颜色相同，则在 \(G_k\) 中节点 \([u, b]\) 和 \([v, b]\) 有连边；反之记二进制串 \(b\) 按位取反得到了二进制串 \(\overline b\)，\([u, b]\) 和 \([v, \overline b]\) 有连边。这也可以通过归纳法证明。
随后考虑如何计算新图的直径。
一条 \(G_k\) 上长度为 \(l\) 的路径 \([u_1, b_{u_1}], [u_2, b_{u_2}], \dots, [u_l, b_{u_l}]\) 是奇的，当且仅当存在 \(2i + 1\) 个位置 \(p > 1\)，满足 \((u_{p - 1}, b_{u_{p - 1}})\) 和 \((u_{p}, b_{u_{p}})\) 的颜色不相同；类似地定义偶路径。也就是说，我们定义路径的奇偶性是路径经过的端点颜色不同的边的数量的奇偶性。
下面的定理给出了一种计算答案的方法。
我们断言，\(G_k\) 内节点 \([u, b_u]\) 和 \([v, b_v]\) 的最短路是以下两个值中较小的值。
- \(u\) 和 \(v\) 之间的最短奇路径的长度 \(+\ \Delta(b_u, b_v)\)；
- \(u\) 和 \(v\) 之间的最短偶路径的长度 \(+\ \Delta(\overline {b_u}, b_v)\)。
证明：
考虑 \(G_k\) 内一条长度为 \(l\) 的路径 \([u_1, b_{u_1}], [u_2, b_{u_2}], \dots, [u_l, b_{u_l}]\)，其中 \([u_1, b_{u_1}] = [u, b_u]\)，\([u_l, b_{u_l}] = [v, b_v]\)。由于 \(G_k\) 的对称性，我们总能将路径中形如 \([u, b_1]\to [u, b_2]\) 的一步放到这条路径的最后走。因此不失一般性地，我们假设存在一个位置 \(i\)，\(\forall j < i, u_j \neq u_{j + 1}\) 且 \(\forall j\ge i,\ u_{j} = u_{j + 1}\)。发现这个全相同的后缀（即 \(i\sim l\) 段路径）节点对应的 \(G_0\) 节点均为 \(v\)。
考虑把这条路径投影到 \(G_0\) 上，得到路径 \(u_1, u_2, \dots, u_l\)。仍然考虑上面的位置 \(i\)，我们发现 \(1\sim i\) 段的路径长度就是 \(u\) 和 \(v\) 之间的最短路径的长度。可以发现，如果 \(1\sim i\) 段路径是偶的，则 \([u_i, b_{u_i}] = [v, b_u]\)；反之 \([u_i, b_{u_i}] = [v, \overline{b_u}]\)。这点可以从上面的若干结论中得出。因此当 \(1\sim i\) 段路径是偶路径时，\(i\sim l\) 段路径的长度就是 \(\Delta(b_u, b_v)\)，反之是 \(\Delta(\overline {b_u}, b_v)\)。
这就完成了证明。
我们其实不需要关注从任意 \([u, b_u]\) 起始的路径。由 \(G_k\) 的对称性可以知道，我们总能把路径 \([u_1, b_{u_1}], [u_2, b_{u_2}], \dots, [u_l, b_{u_l}]\) 中 \(2\sim l\) 段的二进制串 \(b_{u_i}\) 和 \(b_{u_1}\) 做异或，得到等价的路径 \([u_1, \texttt{00...0}], [u_2, (b_{u_2})'], \dots, [u_l, (b_{u_l})']\)。因此我们在计算直径时，只需要考虑从 \([u, \texttt{00...0}]\) 起始的路径。
取两个节点 \(u, v\in V_0\)，考虑确定 \(b\) 使得 \([u, \texttt{00...0}]\) 到 \([v, b]\) 的路径长度最大。根据上述的定理，前半段路径总是从 \([u, \texttt{00...0}]\) 到 \([v, \texttt{00..0}]\) 的最短偶路径或从 \([u, \texttt{00...0}]\) 到 \([v, \texttt{11...1}]\) 的最短奇路径。随后设 \(b\) 中的 \(\texttt{1}\) 数量为 \(x\)，不难发现 \([v, \texttt{00...0}]\to [v, b]\) 的长度是 \(x\)，\([v, \texttt{11...1}]\to [v, b]\) 的长度是 \(k - x\)。
这样我们设 \(\text{dis}_0(u, v)\) 为 \(u\) 到 \(v\) 的最短偶路径，\(\text{dis}_1(u, v)\) 为 \(u\) 到 \(v\) 的最短奇路径，\([u, \texttt{00...0}]\) 到 \([v, b]\) 的最长路径长度可以写成
对确定源点的 \(\text{dis}_0, \text{dis}_1\) 可以通过一次 bfs 得到，随后只需要枚举 \(u, v, x\) 计算长度即可。总时间复杂度 \(O(nm + n^2 k)\)。
给定一个长度为 \(n\) 的序列，给出 \(q\) 个操作，形如：
1 l r x表示将序列下标介于 \([l,r]\) 的元素加上 \(x\)（请注意，\(x\) 可能为负）
2 p y表示查询 \(a_p\) 在过去的多少秒时间内不小于 \(y\)（不包括这一秒）开始时为第 \(0\) 秒，第 \(i\) 个操作发生在第 \(i\) 秒。
\(2 \leq n,q \leq 100000\)， \(1 \leq l \leq r \leq n\)， \(1 \leq p \leq n\)，\(-10^9 \leq x,y,a_i \leq 10^9\)
水紫时刻！
先想 \(n = 1\) 怎么做。考虑维护时间序列 \(b\)，也就是第 \(i\) 秒的值为 \(b_i\)。我们发现 1. 操作就是对 \(b\) 的一个后缀 \(+x\)，2. 操作就是查询 \(b\) 的前缀中 \(\ge y\) 的位置数。
这样我们只需要分块维护有序块即可。可以套基数排序做到 \(O(n\sqrt{n\log n})\)。
当 \(n > 1\) 时可以离线操作，做扫描线，过程中维护 \(b\) 序列。
1.操作就是在 \(l\) 位置后缀 \(+x\)，\(r +1\) 位置后缀 \(-x\)，2. 操作不变。
有 \(O(n)\) 次修改和查询，总时间复杂度 \(O(n\sqrt{n\log n})\)。懒得写基数排序，\(O(n\sqrt n\log n)\) 也能过。
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int _T_; cin >> _T_; for (int TestNo = 1; TestNo <= _T_; ++ TestNo)
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb push_back
#define pb pop_back
const int N = 1e5 + 10, B = 350;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, q, a[N], typ, t1, t2, t3, sqr, bel[N], lp[N], rp[N], ans[N], qcnt;
struct query {
int l, r, w, id;
}; vector<query> qu[N];
struct block {
int a[N], sorted_a[N], siz, lzy;
inline void resize(int __siz) { siz = __siz; }
inline void pdown() {
rep(i,1,siz) a[i] += lzy;
lzy = 0;
}
inline void pup() {
memcpy(sorted_a + 1, a + 1, sizeof(int) * siz);
sort(sorted_a + 1, sorted_a + siz + 1);
}
inline void add_block(int va) {
lzy += va;
}
inline void add_side(int l, int r, int va) {
pdown();
rep(i,l,r) a[i] += va;
pup();
}
inline int query_block(int va) {
va -= lzy;
int id = lower_bound(sorted_a + 1, sorted_a + 1 + siz, va) - sorted_a;
return siz - id + 1;
}
inline int query_side(int l, int r, int va) {
int ret = 0;
rep(i,l,r) if (a[i] + lzy >= va) ++ ret;
return ret;
}
inline void debug() {
rep(i,1,siz) cout << a[i] + lzy << ' '; cout << '\n';
rep(i,1,siz) cout << sorted_a[i] + lzy << ' '; cout << '\n';
}
} bl[B];
signed main() {
cin >> n >> q;
rep(i,1,n) cin >> a[i];
rep(i,1,q) {
cin >> typ;
if (typ == 1) cin >> t1 >> t2 >> t3, qu[t1].eb( { i, q, t3, 0 } ), qu[t2 + 1].eb( { i, q, - t3, 0 } );
else ++ qcnt, cin >> t1 >> t2, qu[t1].eb( { 1, i - 1, t2, qcnt } ), ans[qcnt] += (a[t1] >= t2);
} sqr = sqrt(q);
rep(i,1,q) {
bel[i] = (i - 1) / sqr + 1;
if (bel[i] != bel[i - 1]) lp[bel[i]] = i, rp[bel[i - 1]] = i - 1;
} rp[bel[q]] = q;
rep(i,1,bel[q]) bl[i].resize(rp[i] - lp[i] + 1);
rep(i,1,n) {
rep(j,1,bel[q]) bl[j].add_block(a[i]);
sort(qu[i].begin(), qu[i].end(), [&](auto a, auto b){return a.id < b.id;});
for (auto v : qu[i]) {
if (v.l > v.r) continue;
int bll = bel[v.l], blr = bel[v.r];
if (v.id == 0) {
if (bll == blr) {
bl[bll].add_side(v.l - rp[bll - 1], v.r - rp[bll - 1], v.w);
} else {
bl[bll].add_side(v.l - rp[bll - 1], rp[bll] - rp[bll - 1], v.w);
rep(j,bll + 1,blr) bl[j].add_block(v.w);
}
} else {
if (bll == blr) {
ans[v.id] += bl[bll].query_side(v.l - rp[bll - 1], v.r - rp[bll - 1], v.w);
} else {
rep(j,bll,blr - 1) ans[v.id] += bl[j].query_block(v.w);
ans[v.id] += bl[blr].query_side(1, v.r - rp[blr - 1], v.w);
}
}
}
rep(j,1,bel[q]) bl[j].add_block(- a[i]);
} rep(i,1,qcnt) cout << ans[i] << '\n';
}