根號算法 - HackMD

# 根號算法 --- # 陣列分塊 ---- - 通常是區間詢問類問題 - 將陣列分成 B 塊處理，共有 $\left\lfloor\dfrac{N}{B}\right\rfloor$ 塊 - 每一塊的答案先預處理好 - 對於詢問，完整包含的塊用預處理的答案 - 左右剩下不完整的暴力處理，詢問也是一樣 - 可能在同一塊要用到 lazy tag - 每一次處理最多 $\left\lfloor\dfrac{N}{B}\right\rfloor$ 塊，剩下最多 2B 個 - 若將 B 設為 $\sqrt{N}$ ，一次操作複雜度是 $O(\sqrt{N})$ ---- ## [LOJ -- 数列分块入门 4](https://loj.ac/p/6280) 給定一個長度 $n$ 的序列，接下來有 $q$ 筆詢問，詢問有兩種 1. 將區間[l,r]的值加上 w 2. 詢問區間[l,r]的和mod c $1\leq n,q\leq 10^5$ - 假裝你不知道線段樹BIT之類的資料結構 ---- - 將陣列分成 $B=\sqrt{N}$ 塊 - 每塊儲存總和與加值的 tag - 每個節點儲存值以及所屬的塊 - 修改時塊的部分更改總和與 tag - 修改時節點更改值與所屬塊總和 - 詢問時塊直接用其總和 - 詢問時節點用值加所屬塊tag ---- 程式碼： ```cpp! #include <cmath> #include <iostream> using namespace std; int id[50005], len; // id 表示块的编号, len=sqrt(n) , 即上述题解中的s, sqrt的时候时间复杂度最优 long long a[50005], b[50005], s[50005]; // a 数组表示数据数组, b 数组记录每个块的整体赋值情况, 类似于 lazy_tag, s // 表示块内元素总和 void add(int l, int r, long long x) { // 区间加法 int sid = id[l], eid = id[r]; if (sid == eid) { // 在一个块中 for (int i = l; i <= r; i++) a[i] += x, s[sid] += x; return; } for (int i = l; id[i] == sid; i++) a[i] += x, s[sid] += x; for (int i = sid + 1; i < eid; i++) b[i] += x, s[i] += len * x; // 更新区间和数组(完整的块) for (int i = r; id[i] == eid; i--) a[i] += x, s[eid] += x; // 以上两行不完整的块直接简单求和,就OK } long long query(int l, int r, long long p) { // 区间查询 int sid = id[l], eid = id[r]; long long ans = 0; if (sid == eid) { // 在一个块里直接暴力求和 for (int i = l; i <= r; i++) ans = (ans + a[i] + b[sid]) % p; return ans; } for (int i = l; id[i] == sid; i++) ans = (ans + a[i] + b[sid]) % p; for (int i = sid + 1; i < eid; i++) ans = (ans + s[i]) % p; for (int i = r; id[i] == eid; i--) ans = (ans + a[i] + b[eid]) % p; // 和上面的区间修改是一个道理 return ans; } int main() { int n; cin >> n; len = sqrt(n); // 均值不等式可知复杂度最优为根号n for (int i = 1; i <= n; i++) { // 题面要求 cin >> a[i]; id[i] = (i - 1) / len + 1; s[id[i]] += a[i]; } for (int i = 1; i <= n; i++) { int op, l, r, c; cin >> op >> l >> r >> c; if (op == 0) add(l, r, c); else cout << query(l, r, c + 1) << endl; } return 0; } ``` ---- ### 我們有樹狀的資料結構，可以處理 RMQ 問題，為什麼需要分塊？ ---- ## [Luogu -- 教主的魔法](https://www.luogu.com.cn/problem/P2801) 給定一個長度為 $n$ 的序列，每個位置有初始值 $a_i$ ，接下來有 $q$ 比操作，操作有兩種類型 1. 將區間 $[l,r]$ 的值加上 $w$ 2. 求區間 $[l,r]$ 內有多少個數字大於等於 $w$ $1\leq n\leq 10^6,1\leq q\leq 3000$ ---- - 我們預處理的區間需要排序 - 詢問就可以用二分搜求數量 - 線段樹無法合併兩個序列 - 分塊不需要合併，可以獨立計算 - 詢問不需合併，預處理無法合併用陣列分塊 - 無法用線段樹可以直接套套看 - 塊的大小接近 $\sqrt{n}$ 即可，可以自己測最優的 ---- - 對於每個點，存所屬塊與該點權值 - 對於一塊，存排序好陣列以及加值tag - 修改整塊改tag的偏移值即可，順序不變 - 修改點更改所屬塊排序以及點值 - 詢問塊二分搜第一個$\geq w-tag_i$ - 單點求點權 $a_i+tag_{a_i}\geq w$ - 每次修改 $\sqrt{n}$ 塊，兩塊最後重新排序 - 複雜度 $O(q(\sqrt{n}+\sqrt{n}\log\sqrt{n}))$ ---- 程式碼： ```cpp! #include <bits/stdc++.h> #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; const int N = 1e6 + 6, B = 400; int ar[N], fr[N], tg[N]; vector<int> st[N]; signed main() { int n, q, l, r, w; char c[5]; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &ar[i]), st[fr[i] = i / B].pb(ar[i]); for (int i = 0; i < fr[n]; i++) sort(iter(st[i])); while (q-- && scanf("%s%d%d%d", c, &l, &r, &w)) { if (c[0] == 'M') { for (int i = fr[l] + 1; i < fr[r]; i++) tg[i] += w; vector<int> po; if (fr[l] != fr[r]) { for (int i = l; fr[i] == fr[l]; i++) po.pb(lower_bound(iter(st[fr[i]]), ar[i]) - st[fr[i]].begin()); for (int i = l; fr[i] == fr[l]; i++) st[fr[i]][po[i - l]] = ar[i] += w; po.clear(); for (int i = r; fr[i] == fr[r]; i--) po.pb(lower_bound(iter(st[fr[i]]), ar[i]) - st[fr[i]].begin()); for (int i = r; fr[i] == fr[r]; i--) st[fr[i]][po[r - i]] = ar[i] += w; sort(iter(st[fr[l]])), sort(iter(st[fr[r]])); } else { for (int i = l; i <= r; i++) po.pb(lower_bound(iter(st[fr[i]]), ar[i]) - st[fr[i]].begin()); for (int i = l; i <= r; i++) st[fr[i]][po[i - l]] = ar[i] += w; sort(iter(st[fr[l]])); } } else { int ans = 0; for (int i = fr[l] + 1; i < fr[r]; i++) ans += st[i].end() - lower_bound(iter(st[i]), w - tg[i]); if (fr[l] != fr[r]) { for (int i = l; fr[i] == fr[l]; i++) ans += (ar[i] + tg[fr[i]] >= w); for (int i = r; fr[i] == fr[r]; i--) ans += (ar[i] + tg[fr[i]] >= w); } else { for (int i = l; i <= r; i++) ans += (ar[i] + tg[fr[i]] >= w); } printf("%d\n", ans); } } } ``` --- # 莫隊演算法 ---- - 可以輕易將狀態加入一個點或刪除一個點 - 需要先讀入所有詢問，用更好的順序處理 - 一樣會有塊的大小B，用來輔助排序詢問 - 將詢問以左界所屬塊排序，同塊以右界排序 - 同塊左界每次最多移動 B，右界總共移動 N - 左界持續往右總共 N ，右界移動$\left\lfloor\dfrac{N}{B}\right\rfloor$ 次 - 設 $B=\sqrt{N}$ ，總複雜度 $O(n\sqrt{n})$ ---- ### 奇偶優化 - 設有 $k$ 塊，右界動$N$最多往右 k 次，左 k-1 次 - 當塊編號是奇數，右界降序排，偶數時升序排 - 往左往右交替，不會出現每塊開始時，需要要返回到前面，均攤每塊右界最多移動 $n$ - 常數優化不到兩倍，但分塊常常需要壓時間 ---- ## [ZJ -- 區間眾數](https://zerojudge.tw/ShowProblem?problemid=b417) 給定一個長度 $n$ 序列 $a_i$ ，接下來有 $q$ 比詢問，每筆詢問求區間 $[l,r]$ 內，同個數字出現最多幾次，有多少種數字出現最多次？ $1\leq n,\leq 10^5,1\leq q\leq 10^6$ ---- - 當前狀態維護數字出現次數，以及各次數有幾種數字 - 用一塊大小 $\sqrt{n}$ 左右排序詢問 - 每次插入刪除數字，更改出現次數與種類 - 第一次加入最大次數，更新最大次數 - 最大次數扣到 0 次，最大次數-1（減少一次） - 要先插入再刪除，避免刪到未加入的數字壞掉 ---- 程式碼： ```cpp! #include <bits/stdc++.h> #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; const int N = 1e5 + 5, M = 1e6 + 5, B = 150; int ar[N], ct[N], an[N], a1[M], a2[M], mx, ql[M], qr[M], od[M]; bool cmp(int a, int b) { const int x = ql[a] / B, y = ql[b] / B; if (x != y) return x < y; return (qr[a] < qr[b]) ^ (x & 1); } void add(int x) { an[ct[x]]--, an[++ct[x]]++, tmax(mx, ct[x]); } void sub(int x) { if (!--an[ct[x]] && ct[x] == mx) mx--; an[--ct[x]]++; } signed main() { int n, q; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &ar[i]); for (int i = 0; i < q; i++) scanf("%d%d", &ql[i], &qr[i]); iota(od, od + q, 0); sort(od, od + q, cmp); for (int l = 1, r = 0, i = 0; i < q; i++) { while (r < qr[od[i]]) add(ar[++r]); while (l > ql[od[i]]) add(ar[--l]); while (r > qr[od[i]]) sub(ar[r--]); while (l < ql[od[i]]) sub(ar[l++]); a1[od[i]] = mx, a2[od[i]] = an[mx]; } for (int i = 0; i < q; i++) printf("%d %d\n", a1[i], a2[i]); } ``` ---- ## [Luogu -- [国家集训队] 小 Z 的袜子](https://www.luogu.com.cn/problem/P1494) 給定一個長度 $n$ 的序列 $a_i$ ，接下來有 $q$ 比詢問，每筆詢問求在區間 $[l,r]$ 內，隨機選取兩個不同位置，請問兩個位置數字相同機率是多少？ $1\leq n,m\leq 10^5$ ---- - 維護當前區間個數字出現次數 $c_i$ - 答案會是 $(\sum_{pos_i\in [l,r]}{\binom{c_i}{2}})/\binom{r-l+1}{2}$ - 更新 $c_i$ 時扣掉選舊的，加上選新的 - 觀察到一般莫隊無法進行修改操作 ---- 程式碼： ```cpp! #include <bits/stdc++.h> #define lowbit(x) ((x) & -(x)) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define pb push_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define eps 1e-9 #define F first #define S second #define N 50004 #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; #define f(i) (((i)*llt((i)-1)) >> 1) int lm, ar[N], ct[N]; llt a[N], b[N], cr; struct P { int l, r, id; bool operator<(const P &rh) const { if (l / lm == rh.l / lm) return (r < rh.r) ^ ((l / lm) & 1); return l / lm < rh.l / lm; } } qy[N]; inline void add(int x) { cr -= f(ct[x]); ct[x]++; cr += f(ct[x]); } inline void sub(int x) { cr -= f(ct[x]); ct[x]--; cr += f(ct[x]); } signed main() { int n, q; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &ar[i]); lm = sqrt(n); for (int i = 0; i < q; i++) scanf("%d%d", &qy[i].l, &qy[i].r), qy[i].id = i; sort(qy, qy + q); for (int i = 0, l = 1, r = 0; i < q; i++) { while (r < qy[i].r) add(ar[++r]); while (l > qy[i].l) add(ar[--l]); while (r > qy[i].r) sub(ar[r--]); while (l < qy[i].l) sub(ar[l++]); a[qy[i].id] = cr; b[qy[i].id] = f(r - l + 1); } for (int i = 0; i < q; i++) { if (a[i]) { cr = __gcd(a[i], b[i]); printf("%lld/%lld\n", a[i] / cr, b[i] / cr); } else puts("0/1"); } } ``` ---- ### 可修改莫隊 - 對於一個詢問，有三維屬性$(l,r,t)$ - $t$ 帶表進行了多少次修改操作 - 移動到相鄰位置，只需要花很少時間O(1) - 移動 t 軸時，將陣列的特定位置更改 - 若修改位置在區間內，刪除舊的值加上新的 - 不能處理區間修改的問題 ---- - 將塊的大小設 $B$ ，總共 $n/B$ 塊，修改操作 $t$ 次 - 詢問以(左界塊號碼, 右界塊號碼 , 修改次數)排序 - 時間軸移動 $\dfrac{n^2}{B^2}t$ ，同塊 l,r 移動 $QB$ - 右界跨塊移動 $\dfrac{n^2}{B}$，左界跨塊移動 $n$ - 假設 $n=t=Q$ ，取 $B=n^{2/3}$ 最佳 - 複雜度為 $O(n^{5/3})$，比不修改的略差一些 - 操作簡單，記得排序方法和塊大小(較大)即可 ---- ## [luogu -- 数颜色 / 维护队列](https://www.luogu.com.cn/problem/P1903) 給一個長度 $n$ 的序列 $a_i$ ，接下來有 $q$ 次操作，操作有兩種 1. 將第 $p$ 個數字改成 $w$ 2. 求區間 $[l,r]$ 內有多少種不同數字 $1\leq n,q\leq 133333,1\leq a_i,w\leq 10^6$ ---- - 當前狀態維護各數字出現次數與種類數量 - 幫詢問與修改分開編號 - 紀錄每次詢問前有幾次修改 - 紀錄每次修改位置與修改前後的值 - 用上述方法分塊大小進行排序 - 移動 $(l,r,t)$ 並更新序列算答案 ---- 程式碼： ```cpp! #include <bits/stdc++.h> #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; const int N = 1.4e5, M = 1e6 + 6, B = 5000; struct Q { int l, r, id, t; } qy[N]; int ar[N], mp[N], m1[N], m2[N], cnt, cq, ct[M], ans; bool cmp(const Q &a, const Q &b) { return mpr(mpr(a.l / B, a.r / B), a.t) < mpr(mpr(b.l / B, b.r / B), b.t); } inline void add(int x) { if (!ct[x]++) ans++; } inline void sub(int x) { if (!--ct[x]) ans--; } signed main() { int n, q; char c[5]; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &ar[i]); for (int i = 0; i < q; i++) { scanf("%s", c); if (c[0] == 'R') { cnt++; scanf("%d%d", &mp[cnt], &m2[cnt]); m1[cnt] = ar[mp[cnt]], ar[mp[cnt]] = m2[cnt]; } else { scanf("%d%d", &qy[cq].l, &qy[cq].r); qy[cq].id = i, qy[cq].t = cnt, cq++; } } for (int i = cnt; i > 0; i--) ar[mp[i]] = m1[i]; sort(qy, qy + cq, cmp); for (int i = 0, l = 1, r = 0, t = 0; i < cq; i++) { Q &qq = qy[i]; while (r < qq.r) add(ar[++r]); while (l > qq.l) add(ar[--l]); while (r > qq.r) sub(ar[r--]); while (l < qq.l) sub(ar[l++]); while (t < qq.t) { t++; if (l <= mp[t] && mp[t] <= r) add(m2[t]), sub(m1[t]); ar[mp[t]] = m2[t]; } while (t > qq.t) { if (l <= mp[t] && mp[t] <= r) add(m1[t]), sub(m2[t]); ar[mp[t]] = m1[t], t--; } qq.t = ans; } sort(qy, qy + cq, [&](const Q &a, const Q &b) { return a.id < b.id; }); for (int i = 0; i < cq; i++) printf("%d\n", qy[i].t); } ``` ---- ### 回滾莫隊 - 當僅有刪除操作好做，插入需要加全部均攤 - 詢問左界分到所在的塊，同一塊一起 O(n) 處理 - 一塊開始時，先插入該塊以右所有節點 - 同塊的詢問依照右界降序排序 - 每次詢問先刪右界的，再刪左界的 - 算好答案以後，左界刪除的操作undo掉 ---- 題目：https://www.luogu.com.cn/problem/P8078 比較難，就不講解了題解：https://hail-garage-f95.notion.site/P8087-5412fd878b0f4ca6a14925520c2f2c60?pvs=4 --- # 根號分治 - 可能有算式 $x\times y =k\leq 10^6$ - 對於 $x\leq 10^3(\sqrt{n})$，枚舉 x 後O(n) 處理 y - 對於 $x>10^3(\sqrt{n})$，$y\leq\sqrt{n}$，特殊處理 y ---- ## [CF -- D. Tree Queries](https://codeforces.com/contest/1254/problem/D) 給定一棵 $n$ 個節點的樹，初始的點權為 0 ，接下來有 $q$ 比詢問，每筆詢問有兩種 1. 給節點 $v$ ，然後隨機取節點 $r$ ，對於所有的節點 $u$ ，若 $u$ 到 $r$ 的最短路徑經過 $v$ ，將節點權值加上 $d$ 2. 詢問節點 $v$ ，求該節點權值期望值 $1\leq n,q,\leq 2\times 10^5$ ---- - 觀察到若節點 $u$ 被更改，在以 $v$ 為根的樹，$u$ 和 $r$ 屬於不同子樹 - 同一個子樹加值相同，設子樹大小為 $s$，加了 $\frac{n-s}{n}\times d$ - 節點 $v$ 直接加上 $d$ - 可以用樹壓平，對子樹區間修改 - 一個修改對詢問影響，可以 O(logn) 用LCA處理 ---- - 度數超過 $\sqrt{n}$ 的節點數量不超過 $\sqrt{n}$ 個 - 對於修改節點，輕點遍歷鄰邊將子樹用樹壓平更新 - 詢問O(logn)補上每個重點的影響 - 總複雜度 $O(n\sqrt{n}\log n)$ - 重點其實很少，分界可以設小一點更快 ---- 程式碼： ```cpp! #include <bits/stdc++.h> #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + M + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; const int M = 998244353; // random_device rm; // mt19937 rg(rm()); // default_random_engine rg(rm()); // uniform_int_distribution<int> rd(INT_MIN, INT_MAX); // uniform_real_distribution<double> rd(0, M_PI); void db() { cerr << "\n"; } template <class T, class... U> void db(T a, U... b) { cerr << a << " ", db(b...); } template <typename T> void rd(T &x) { x = 0; bool f = 0; char c = getchar(); while (!isdigit(c)) f ^= !(c ^ 45), c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); f && (x = -x); } template <typename T> void prt(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) prt(x / 10); putchar((x % 10) ^ 48); } const int N = 1.5e5 + 5, B = 150; vector<int> eg[N], sk; int ac[20][N], in[N], ou[N], sz[N], ct; int vl[N], bs[N]; inline int pw(int v, int p) { int sm = 1; for (; p; p >>= 1) { if (p & 1) tml(sm, v); tml(v, v); } return sm; } void dfs(int u, int fa) { in[u] = ++ct, sz[u] = 1; for (int v : eg[u]) { if (v == fa) continue; ac[0][v] = u; for (int t = 1; t < 20; t++) ac[t][v] = ac[t - 1][ac[t - 1][v]]; dfs(v, u), sz[u] += sz[v]; } if (eg[u].size() >= B) sk.pb(u); ou[u] = ct; } inline bool isa(int p, int x) { return in[p] <= in[x] && ou[x] <= ou[p]; } inline void cg(int p, int v) { for (; p < N; p += lowbit(p)) tad(bs[p], v); } inline int qy(int p) { int sm = 0; for (; p; p -= lowbit(p)) tad(sm, bs[p]); return sm; } signed main() { int n, q, x, y, c; rd(n), rd(q); for (int i = 1; i < n; i++) { rd(x), rd(y); eg[x].pb(y); eg[y].pb(x); } dfs(1, -1); int rn = pw(n, M - 2); while (q--) { rd(c); if (c == 1) { rd(x), rd(y); if (!y) continue; if (eg[x].size() < B) { cg(in[1], ml(y, ml(sz[x], rn))); cg(in[x], ml(y, mi(1, ml(sz[x], rn)))); cg(in[x] + 1, -y); cg(ou[x] + 1, ml(y, ml(sz[x], rn))); for (int v : eg[x]) if (v != ac[0][x]) cg(in[v], ml(y, mi(1, ml(sz[v], rn)))), cg(ou[v] + 1, -ml(y, mi(1, ml(sz[v], rn)))); } else tad(vl[x], y); } else { rd(x); int ans = qy(in[x]); for (int i : sk) { if (!vl[i]) continue; if (i == x) tad(ans, vl[i]); else if (isa(i, x)) { int u = x; for (int k = 19; k >= 0; k--) if (ac[k][u] && !isa(ac[k][u], i)) u = ac[k][u]; tad(ans, ml(vl[i], mi(1, ml(sz[u], rn)))); } else tad(ans, ml(vl[i], ml(sz[i], rn))); } prt(ans), putchar('\n'); } } } ``` ---- ## 不會過另解：操作分塊 - 紀錄了一些修改，可以 O(n) dp 更改整張圖 - 將詢問 $\sqrt{n}$ 分成一塊，每塊結束 O(n) 更新圖 - 塊內詢問用LCA枚舉塊內修改影響 - 複雜度一樣，但是常數超級大 [參考 Solution1](https://hail-garage-f95.notion.site/1254D-d05b85923a5240e1b934d0c382219825?pvs=4) ---- --- # 數論分塊 ---- - 遇到要處理下連續下高斯函數時 - 問題形式可能長 $\sum_{i=1}^{n}{f(i)g(\lfloor \frac{n}{i}\rfloor)}$ - 已知 $f$ 前綴，可以快速算 $\sum_{i=l}^{r}{f(i)}$ - 相同的 $g(\lfloor \frac{n}{i}\rfloor)$ 的與 $f(i)$ 打包一起算 - 總共有 $O(\sqrt{n})$ 種 $\lfloor \frac{n}{i}\rfloor$ ---- ![](https://hackmd.io/_uploads/SJA5vLLMT.png) ---- - 對於 $\lfloor\dfrac{n}{i}\rfloor=k$，我們想要找出 $i$ 的左右界 - 可以枚舉左界是上個右界+1，右界剛好是 $\lfloor\dfrac{n}{k}\rfloor$ 1. 固定初始做界為 1 2. 算右界與計算函數值 3. 更新左界為右界+1，重複2 4. 左界 > n 結束 ### [略證](https://hail-garage-f95.notion.site/e9fe227bfb8c45fa8ef34bac2a3f2a54?pvs=4) ---- ## [UVA -- 11526 - H(n)](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2521) 總共有 $T$ 比測資，每一筆測資有一個數字 $n$ ，求 $\sum_{i=1}^{n}{\lfloor\dfrac{n}{i}\rfloor}$ $1\leq T\leq 1000,\ 1\leq n\leq 2^{31}$ - 以上面的式子來看， $f(x)=1,\ g(x)=x$ ---- 程式碼： ```cpp! long long H(int n) { long long res = 0; // 储存结果 int l = 1, r; // 块左端点与右端点 while (l <= n) { r = n / (n / l); // 计算当前块的右端点 res += (r - l + 1) * 1LL * (n / l); // 累加这一块的贡献到结果中。乘上 1LL 防止溢出 l = r + 1; // 左端点移到下一块 } return res; } ``` ---- ## [CSES -- Sum of Divisors](https://cses.fi/problemset/task/1082) 定義函數 $H(x)$ 為 $x$ 的因數和，例如 $H(12)=1+2+3+4+6+12=28$，給出一個整數 $n$ ，求 $\sum_{i=1}^{n}{H(i)}\ \ mod\ \ 10^9+7$ $1\leq n\leq 10^{12}$ ---- - 一個數 $x$ 會當因數 $\lfloor\dfrac{n}{x}\rfloor$ 次 - 改寫式子 $\sum_{i=1}^{n}{(i\times\lfloor\frac{n}{i}\rfloor)}$ - 以上面的式子來看， $f(x)=x,\ g(x)=x$ - 不一定要有式子才數論分塊 - 遇到下高斯可能可快速算左右界幫助 dp - 有可能只是除法結果 $O(\sqrt{n})$ 種，幫助離散化 ---- 程式碼： ```cpp! #include <bits/stdc++.h> #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; const int M = 1e9 + 7; inline int C2(llt x) { return (((x + 1) * x) >> 1) % M; } signed main() { llt n, l = 1, r; int ans = 0; scanf("%lld", &n); while (l <= n) { r = n / (n / l); tad(ans, ml(n / l, mi(C2(r % M), C2((l - 1) % M)))); l = r + 1; } printf("%d\n", ans); } ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.