$Part.1$ 插头dp

「UVA 11270」Tiling Dominoes
用$1\times2$的骨牌铺满方格，问方案数。
骨牌放置基础题，按格子转移记录左上是否有插头。

「HDU 4804」Campus Design
用$1\times2$和$1\times1$的骨牌铺满方格，问$1\times1$的骨牌个数在$c$和$d$之间的方案数。
与上一题类似，多记录一下放置了几个$1\times1$的骨牌。

「HDU 1693」Eat the Trees
用若干回路完全覆盖网格方案数，只需生成和合并成对插头。

「ZOJ 4231」The Hive II
用若干回路完全覆盖六边形网格方案数，和上一题类似。

「Ural 1519」Formula 1
用一条回路覆盖网格方案数，回路的闭合只能出现在最后一个格子。

「POJ 1739」Tony’s Tour
用一条路径覆盖网格方案数，起点终点固定，可以在外面加一圈限制变成一条回路问题。

「USACO 6.1.1」Postal Vans
用一条回路覆盖网格方案数，$m$很小$n$很大，矩阵快速幂+高精度。

「HNOI2007」神奇游乐园
网格图，每个格子有权值，找一条最大权回路，不要求覆盖所有格子，意味着回路可以在任何格子闭合。

「ProjectEuler 393」Migrating ants
用若干有向回路覆盖网格的方案数，$k$条无向回路覆盖的贡献是$2^k$，多加一个域记录回路闭合次数。

「ZOJ 3213」Beautiful Meadow
网格图，每个格子有权值，找一条最大权不自交路径，多加一个域记录独立插头的生成与消失次数。

「CQOI 2017」矩形
将网格染色成黑白两部分，每部分都与边界连通的方案数。
钦定左上角是黑色，这样只需要白色与边界相连，当轮廓线颜色全部是A，上方放过B，再要放A时不合法。

「UVA 10572」Black & White
将网格染色成黑白两部分，且不存在$2\times2$同色的方案数，输出方案。
除了轮廓线之外，再记录当前格子左上角颜色即可。
对于输出方案，记录$pre_{i,j,x}$和$op_{i,j,x}$表示格子$(i,j)$从上一格的哪个状态转移过来，以及这格放什么颜色，逆推回去即可。

「JLOI 2009」神秘的生物
网格图，每个格子有权值，找一个最大权连通块。
多开一个域记录是否有连通分量与外界完全隔绝。

「NOI 2007」生成树计数
问一类特殊的图的生成树个数，其实并不是传统意义上的插头dp，但用到了最小表示法，思想类似。
最小表示法，对状态编号+矩阵快速幂。

「2015 ACM-ICPC Asia Shenyang Regional Contest - Problem E」Efficient Tree
求网格图的最小生成树个数，以及所有最小生成树的$\Pi_{LRdeg(u)}$之和，$LUdeg(u)$定义为节点$u$与左边和上边的节点中和$u$相连的节点的个数$+1$。
每个点只考虑向左上连边，注意不能成环，且不能孤立连通分量，连通分量被孤立当且仅当上方节点所在连通分量在轮廓线上只出现一次，且当前节点不与上方节点连边。

「HDU 4113」Construct the Great Wall
网格图，沿着格边的一条回路，把所有的O圈在里面，X隔在外面，求回路的最小长度。
一个格子在回路内部当前仅当他左侧有奇数个插头，在回路外部当且仅当左侧有偶数个插头，仅在合法时转移。

「HDU 4796」Winter’s Coming
网格图，找一条最小权路径连通上下边界，且所有W在路径左侧，L在路径右侧。
一个格子在路径左侧当前仅当他左侧有偶数个插头，在路径右侧当且仅当左侧有奇数个插头，仅在合法时转移。
独立插头只能在第一行生成，在最后一格判断已经生成过独立插头且轮廓线上仅有一个插头则合法。

「ZOJ 2125」Rocket Mania
网格图，每个格子是’.’,’+’,’L’,’T’,’-‘中的一种，可以旋转，问右侧最多几行和左侧的第d行相连。
首先把图旋转，让左右变成上下，把与上边第k列相连的插头钦定为1，只能在制定格子生成1插头，其余插头使用最小表示法表示，然后分类讨论每种格子每种放置方法的转移。
有一个减少状态数的小trick，一个非1的插头在轮廓线上只出现一次，那他就没用了，直接视作0。

「ZOJ 2126」Rocket Mania Plus
同上，问右侧最多几行和左侧相连。
可以在第一列任何格子生成1插头。

「World Finals 2009/2010 Harbin」Channel
网格图找一条从左上到右下的最长路径，使得路径在拐角处八连通意义上不相邻，且不能存在$2\times2$都是路径的块，输出方案。
输出方案和「UVA 10572」Black & White类似。
除了记录插头之外还需要记录每个格子是否有路径，因为存在路径也可能没有插头。
考虑拐角处八连通意义不相邻怎么处理，需要记录当前格子左上以及右上两个格子，右上在轮廓线上可以直接知道，左上不在轮廓线上，当在上一格处他在轮廓线上，额外记录即可。当生成成对的右下插头时左上不能有路径，当左插头延伸到下插头时右上不能有路径。

「HDU 3958」Tower Defence
网格图给定起点终点，图上有若干障碍物，再放置若干障碍物最大化起点到终点的最短路。
同上一题，只不过没有拐角处不能八连通的限制，对于输出方案，把所有不是路径的格子全放上障碍物。

「UVA 1214」Manhattan Wiring
网格图，有一对2一对3，两条路径连接相同数字，路径不相交，最化小路径长度和。
不需要最小表示法，插头直接生成2和3即可，自环一定会使答案不优，不需要判。

「SDOI 2014」电路板
同上，但最多有九对需要相连的数字，且一个格子可以有两根线，具体见题目。

「SPOJ CAKE3」Delicious Cake
给一个网格蛋糕，延网格的边切分分成若干块，问方案数。
考虑染色模型，但有个问题，合并两个相邻的连通分量是不合法的，看到$n$很小，可以直接把连通分量两两之间相邻与否压入状态。

「AIZU 2452」Pipeline Plans
有若干种瓷砖，每种有若干个，不可以旋转，问有多少种放置方式让左上和右下格子中心点连通。
将每种瓷砖剩余个数压入状态，分类讨论转移即可，统计方案可以在转移至最后一格时统计，比较方便。

「Atcoder TDPC」マス目
网格图，黑白染色，使得左上角和右下角同属一个黑色连通块的方案数。
将与左上角连通的黑色连通分量即为1，其余使用最小表示法即可。
也可以多开一个域表示当前哪个编号的连通分量和左上角相连。

怎么写了一坨屎出来啊（恼）

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

using i64 = long long;

const int inf = 0x3f3f3f3f;

int p3[20], g[160];
vector<pair<int, int>> h[11][60000];
vector<int> state[11];
int n, m, k;
int id[11][60000], tot, f[2][2000];

int get(int x, int y) { 
    return (x % p3[y + 1]) / p3[y];
}

void set(int& x, int y, int z) { 
    x += p3[y] * (z - get(x, y)); 
}

bool check(int S) {
    int last = -1, len = 0;
    for (int j = 0; j < m; j++) {
        int cur = get(S, j);
        if (cur == last) {
            len++;
        } else {
            if (last == 2 && len % 2) return false;
            if (last == 1 && len < 2) return false;
            len = 1;
        }
        last = cur;
    }
    if (last == 2 && len % 2) return false;
    if (last == 1 && len < 2) return false;
    return true;
}

bool check(int S, int i) {
    for (int j = 0; j < m; j++)
        if (get(S, j) && (g[i] >> j & 1))
            return false;
    return true;
}

int calc(int S, int T) {
    int U = 0;
    for (int j = 0; j < m; j++) {
        int a = get(S, j), b = get(T, j);
        if (a) {
            if (b != a - 1) return -1;
        } else {
            set(U, j, b);
        }
    }    
    int last = -1, len = 0, res = 0;
    for (int j = 0; j < m; j++) {
        int cur = get(U, j);
        if (cur == last) {
            len++;
        } else {
            if (last == 1) {
                if (len % 3) return -1;
                res += len / 3;
            } else if (last == 2) {
                if (len % 2) return -1;
                res += len / 2;
            }
            len = 1;
        }
        last = cur;
    }
    if (last == 1) {
        if (len % 3) return -1;
        res += len / 3;
    } else if (last == 2) {
        if (len % 2) return -1;
        res += len / 2;
    }
    return res;
}

int main() {
    p3[0] = 1;
    for (int i = 1; i <= 11; i++) {
        p3[i] = p3[i - 1] * 3;
    }  
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m >> k;
        memset(g, 0, sizeof g);
        while (k--) {
            int x, y;
            cin >> x >> y;
            --y;
            g[x] |= 1 << y;
        }
        if (state[m].empty()) {
            state[m].clear();
            for (int i = 0; i < p3[m]; i++) {
                if (check(i)) {
                    state[m].emplace_back(i);
                }
            }
            tot = 0;
            for (auto S : state[m]) id[m][S] = ++tot;
            for (auto a : state[m]) {
                h[m][a].clear();
                for (auto b : state[m]) {
                    int v = calc(a, b);
                    if (~v) {
                        h[m][a].emplace_back(b, v);
                    }
                }
            } 
        }
        memset(f, -0x3f, sizeof f);
        f[0][id[m][0]] = 0;
        for (int i = 0; i < n; i++) {
            int cur = i & 1, ne = (i + 1) & 1;
            memset(f[ne], -0x3f, sizeof f[ne]);
            for (auto a : state[m]) {
                if (f[cur][id[m][a]] != -inf) {
                    for (auto [b, v] : h[m][a]) {
                        if (check(b, i + 1) && check(a, i + 1)) {
                            f[ne][id[m][b]] = max(f[ne][id[m][b]], f[cur][id[m][a]] + v);
                        }
                    }
                }
            }
        }
        cout << f[n & 1][id[m][0]] << '\n';
    }
    return 0;
}

就那个常用卷积

$id_k * 1 = \sigma_k$

$\mu * id = \phi$

$\phi * 1 = id$

$\mu * 1 = \epsilon$

$\sigma_0 * \mu = 1$

就那个狄利克雷前/后缀和

$O(nlog(logn))$

$g(d)=\sum \limits _{d|T}f(T)$

for (int i = 0; i < cnt; i++) {
    for (int j = n / primes[i]; j; j--) {
        f[j] += f[j * primes[i]];
    }
}

$g(T)=\sum \limits _{d|T}f(d)$

for (int i = 0; i < cnt; i++) {
    for (int j = 1; j * primes[i] <= n; j++) {
        f[primes[i] * j] += f[j];
    }
}

就那个伯努利数和自然数幂和多项式的系数

$O(n^2)$

void init_B(int n) {
    B[0] = 1;
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 0; j < i; j++) {
            sum = (sum + 1ll * c(i + 1, j) * B[j] % mod) % mod;
        }
        B[i] = (mod - 1ll * sum * qpow(c(i + 1, i), mod - 2) % mod);
    }
    for (int i = 0; i <= n; i++) {
        f[n + 1 - i] = 1ll * c(n + 1, i) * B[i] % mod * qpow(n + 1, mod - 2) % mod;
    }
}

首先对一个数操作两次等于没有操作，所以每个数要么操作要么不操作。

首先$1$和所有质数显然一定要操作。

对于$x=p_1p_2$，之前已经被翻转过$3$次，所以一定要操作。

对于$x=p_1p_2p_3$，之前已经被翻转过$7$次，所以一定要操作。

…

对于$x = p_1p_2 …p_k$，之前已经被翻转过$2^k-1$次，所以一定要操作。

这样操作之后所有$x = p_1^{\alpha_1}p_2^{\alpha_2} …p_k^{\alpha_k}$都被翻转了$2^k$次，满足要求。

答案就是$\sum\limits _{i=1}^n \mu^2(i)$。

$\sum\limits_{i=1} ^ {n} \mu^2(i) = \sum\limits_{i=1} ^{\lfloor \sqrt n \rfloor} \mu(i) \lfloor \frac{n}{i^2} \rfloor$

杜教筛+整除分块即可。

时间复杂度不会算，反正过了。

#include <iostream>
#include <unordered_map>
#include <cmath>

using namespace std;

const int N = 20000010;

using i64 = long long;

int primes[N], cnt;
bool st[N];
int mu[N];
unordered_map<int, int> ans_mu;

void init(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            mu[i] = -1;
        }
        for (int j = 0; j < cnt && primes[j] * i <= n; j++) {
            int x = primes[j];
            st[i * x] = true;
            if (i % x == 0) {
                break;
            } else {
                mu[i * x] = -mu[i];
            }
        }
    }
    for (int i = 1; i <= n; i++) mu[i] += mu[i - 1];
}

int sum_mu(int n) {
    if (n <= 20000000) return mu[n];
    if (ans_mu.count(n)) return ans_mu[n];
    i64 res = 1;
    for (i64 l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        res -= (r - l + 1) * sum_mu(n / l);
    }
    return ans_mu[n] = res;
}

int main() {
    init(20000000);
    i64 n;
    cin >> n;
    i64 res = 0;
    for (i64 l = 1, r; l <= n / l; l = r + 1) { 
        r = sqrt(n / (n / l / l));
        res += (sum_mu(r) - sum_mu(l - 1)) * (n / (l * l));
    }
    cout << res << '\n';
    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

using i64 = long long;

const int N = 50010;

int n, m, primes[N], cnt;
bool st[N];
i64 mu[N], f[N];

void init(int n = 50000) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i, mu[i] = -1;
        for (int j = 0; j < cnt && primes[j] * i <= n; j++) {
            st[i * primes[j]] = true;    
            if (i % primes[j] == 0) break;
            mu[i * primes[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= n; i++) mu[i] += mu[i - 1];
    for (int i = 1; i <= 50000; i++) {
        for (int l = 1, r; l <= i; l = r + 1) {
            r = i / (i / l);
            f[i] += 1ll * (r - l + 1) * (i / l);
        }
    }
}

i64 calc(int n, int m) {
    i64 res = 0;
    if (n > m) swap(n, m);
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        res += (mu[r] - mu[l - 1]) * f[n / l] * f[m / l];
    }
    return res;
}

int main() {
    init(50000);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        cout << calc(n, m) << '\n';
    }
    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

using i64 = long long;

const int N = 50010;

int n, m, primes[N], cnt;
bool st[N];
i64 mu[N];

void init(int n = 50010) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i, mu[i] = -1;
        for (int j = 0; j < cnt && primes[j] * i <= n; j++) {
            st[i * primes[j]] = true;    
            if (i % primes[j] == 0) break;
            mu[i * primes[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= n; i++) mu[i] += mu[i - 1];
}

i64 calc(int n, int m, int k) {
    i64 res = 0;
    n /= k, m /= k;
    if (n > m) swap(n, m);
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        res += (mu[r] - mu[l - 1]) * (n / l) * (m / l);
    }
    return res;
}

int main() {
    init(50000);
    int T;
    cin >> T;
    while (T--) {
        int a, b, c, d, k;
        cin >> a >> b >> c >> d >> k;
        cout << calc(b, d, k) - calc(a - 1, d, k) - calc(b, c - 1, k) + calc(a - 1, c - 1, k) << '\n';
    }
    return 0;
}

$SATT$是一种用$splay$维护树收缩结构从可以实现树链/子树修改/查询的动态树。
时间复杂度超大常数均摊$O(logn)$。
研究了两天，参考了别人的代码和博客，但是现在也没理解透彻原理。
有一些压行，代码比较丑。

#include <iostream>

using namespace std;

const int N = 500010;
const int inf = 1e9;

#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
#define ms(x) tr[x].s[2]
#define fa(x) tr[x].fa

struct Tag {
    int mul, add;
    Tag(int mul = 1, int add = 0) : mul(mul), add(add) {}
    void clear() { mul = 1, add = 0; }
};

struct Data {
    int sz, sum, mx, mn;
    Data(int sz = 0, int sum = 0, int mx = -inf, int mn = inf) : sz(sz), sum(sum), mx(mx), mn(mn) {}
};

Tag operator+ (Tag& a, Tag& b) { return Tag(a.mul * b.mul, a.add * b.mul + b.add); }
Data operator+ (const Data& a, const Data& b) { return Data(a.sz + b.sz, a.sum + b.sum, max(a.mx, b.mx), min(a.mn, b.mn)); }
Data operator+ (const Data& a, const Tag& b) { return Data(a.sz, a.sum * b.mul + a.sz * b.add, a.mx == -inf ? -inf : a.mx * b.mul + b.add, a.mn == inf ? inf : a.mn * b.mul + b.add); }
int operator+ (const int& a, const Tag& b) { return a * b.mul + b.add; }

struct Node {
    int v, fa, s[3];
    int rev;
    Tag pt, tt;
    /* path tag & tree tag */
    Data p, t;
    void clear() {
        tt.clear(), pt.clear();
        v = rev = s[0] = s[1] = s[2] = 0;
    }
} tr[N];
int stk[N], top, idx;
int root;
pair<int, int> edge[N];
int n, m;

void clear(int& x) { tr[x].clear(), stk[++top] = x; }
int new_node() { return top ? stk[top--] : ++idx; }
bool get(int x) { return x == rs(fa(x)); }
bool isroot(int x) { return ls(fa(x)) != x && rs(fa(x)) != x; }
void set(int x, int fa, int t) { if (x) fa(x) = fa; tr[fa].s[t] = x; }
void rev(int x) { swap(ls(x), rs(x)), tr[x].rev ^= 1; }

void pathtag(int x, Tag& tag) {
    tr[x].v = tr[x].v + tag;
    tr[x].p = tr[x].p + tag;
    tr[x].pt = tr[x].pt + tag;
}

void treetag(int x, Tag& tag) {
    tr[x].t = tr[x].t + tag;
    tr[x].tt = tr[x].tt + tag;
}

void pushup(int x, int t) {
    auto& u = tr[x], &l = tr[ls(x)], &r = tr[rs(x)], &m = tr[ms(x)];
    if (!t) {
        /* compress node */
        u.t = l.t + m.t + r.t;
        u.p = l.p + Data(1, u.v, u.v, u.v) + r.p;
    } else {
        /* rake node */
        u.t = l.t + m.t + m.p + r.t;
    }
}

void pushdown(int x, int t) {
    if (!t) {
        /* compress node */  
        if (tr[x].rev) {
            rev(ls(x)), rev(rs(x));
            tr[x].rev = 0; 
        }
        if (tr[x].pt.mul != 1 || tr[x].pt.add) {
            pathtag(ls(x), tr[x].pt);
            pathtag(rs(x), tr[x].pt);
            tr[x].pt.clear();
        }
        if (tr[x].tt.mul != 1 || tr[x].tt.add) {
            treetag(ls(x), tr[x].tt);
            treetag(rs(x), tr[x].tt);
            treetag(ms(x), tr[x].tt);
            tr[x].tt.clear();
        }
    } else {
        /* rake node */
        if (tr[x].tt.mul != 1 || tr[x].tt.add) {
            treetag(ls(x), tr[x].tt);
            treetag(rs(x), tr[x].tt);
            treetag(ms(x), tr[x].tt);
            pathtag(ms(x), tr[x].tt);
            tr[x].tt.clear();
        }
    }
}

void pushall(int x, int t) {
    if (!isroot(x)) pushall(fa(x), t);
    pushdown(x, t);
}

void rotate(int x, int t) {
    int y = fa(x), z = fa(y);
    int k = get(x), w = tr[x].s[k ^ 1]; 
    if (z) tr[z].s[ms(z) == y ? 2 : get(y)] = x;
    if (w) fa(w) = y;
    fa(x) = z, tr[x].s[k ^ 1] = y;
    fa(y) = x, tr[y].s[k] = w;
    pushup(y, t), pushup(x, t);
}

void splay(int x, int t, int goal = 0) {
    pushall(x, t);
    for (int y; y = fa(x), !isroot(x) && y != goal; rotate(x, t))
        if (fa(y) != goal && !isroot(y)) 
            rotate(get(x) == get(y) ? y : x, t);
}

void del(int x) {
    set(ms(x), fa(x), 1);
    if (ls(x)) {
        int y = ls(x);
        pushdown(y, 1);
        for (pushdown(y, 1); rs(y); y = rs(y)) pushdown(y, 1);
        splay(y, 1, x);
        set(rs(x), y, 1);
        set(y, fa(x), 2);
        pushup(y, 1), pushup(fa(x), 0);
    } else {
        set(rs(x), fa(x), 2);
    } 
    clear(x);
}

void splice(int x) {
    /*  local splay */  
    splay(x, 1);
    int y = fa(x);
    splay(y, 0);
    pushdown(x, 1);
    /*  splice  */
    if (rs(y)) swap(fa(ms(x)), fa(rs(y))), swap(ms(x), rs(y));
    else del(x);
    pushup(x, 1), pushup(y, 0);
}

void access(int x) {
    splay(x, 0);
    int z = x;
    if (rs(x)) {
        int y = new_node();
        set(ms(x), y, 0);
        set(rs(x), y, 2);
        rs(x) = 0;
        set(y, x, 2);
        pushup(y, 1);
        pushup(x, 0);
    }
    while (fa(x)) splice(fa(x)), x = fa(x), pushup(x, 0);   
    splay(z, 0);
    /* global splay */
}

void evert(int x) { access(x), rev(x); } /* aka. makeroot */
void expose(int x, int y) { evert(x), access(y); } /* aka. split */
void link(int x, int y) { access(x), evert(y), set(y, x, 1), pushup(x, 0); }
void change_root(int x) { evert(root = x); }
int findroot(int x) { access(x); while (ls(x)) pushdown(x, 0), x = ls(x); splay(x, 0); return x; }
int cut(int x) { access(x); int y = ls(x); for (; rs(y); y = rs(y)) pushdown(y, 0); ls(x) = fa(ls(x)) = 0; pushup(x, 0); return y; }
Data path_query(int x, int y) { expose(x, y); Data res = tr[y].p; evert(root); return res; }
Data tree_query(int x) { access(x); Data res = Data(1, tr[x].v, tr[x].v, tr[x].v) + tr[ms(x)].t; return res; }

void path_update(int x, int y, int mul, int add) { 
    Tag tag(mul, add); 
    expose(x, y);
    pathtag(y, tag);
    evert(root); 
}

void tree_update(int x, int mul, int add) { 
    Tag tag(mul, add); 
    access(x);
    treetag(ms(x), tag);
    tr[x].v = tr[x].v + tag;
    pushup(x, 0);
    evert(root); 
}

void change_father(int x, int y) {
    if (x == y || x == root) return;
    int z = cut(x);
    if (findroot(x) == findroot(y)) link(x, z);
    else link(x, y);
    evert(root);
}

int main() {
    Data tmp(0, 0, -inf, inf);
    tr[0].t = tr[0].p = tmp;
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        auto& [u, v] = edge[i];
        cin >> u >> v;
    }
    for (int i = 1; i <= n; i++) {
        cin >> tr[i].v;
        pushup(i, 0);
    }
    idx = n;
    for (int i = 1; i < n; i++) {
        auto& [u, v] = edge[i];
        link(u, v);
    }    
    cin >> root;
    evert(root);
    while (m--) {
        int op, x, y, z;
        cin >> op;
        /* subtree update */
        if (op == 0 || op == 5) {
            cin >> x >> y;
            if (op == 0) tree_update(x, 0, y);
            if (op == 5) tree_update(x, 1, y);
        }
        /* path update */
        if (op == 2 || op == 6) {
            cin >> x >> y >> z;
            if (op == 2) path_update(x, y, 0, z);
            if (op == 6) path_update(x, y, 1, z);
        } 
        /* subtree query */
        if (op == 3 || op == 4 || op == 11) {
            cin >> x;
            Data data = tree_query(x);
            if (op == 3) cout << data.mn << '\n';
            if (op == 4) cout << data.mx << '\n';
            if (op == 11) cout << data.sum << '\n';
        }
        /* path query */
        if (op == 7 || op == 8 || op == 10) {
            cin >> x >> y;
            Data data = path_query(x, y);
            if (op == 7) cout << data.mn << '\n';
            if (op == 8) cout << data.mx << '\n';
            if (op == 10) cout << data.sum << '\n';
        }
        /* change root */
        if (op == 1) {
            cin >> x;
            change_root(x);
        }
        /* change structure */
        if (op == 9) {
            cin >> x >> y;
            change_father(x, y);
        }
    }
    return 0;
}

$Picks \; loves \; segment \; tree \; VIII$

存档。

查询区间和不知道写的对不对。

#include <iostream>
#include <cstring>

using namespace std;

using i64 = long long;

const int inf = 2e9;
const int N = 500010;

struct Tag {
    int add, mx, mn;
    void clear() {
        add = mx = mn = 0;
    }
};

Tag operator+ (Tag a, Tag b) {
    a.mx = max(a.mx, a.add + b.mx);
    a.mn = min(a.mn, a.add + b.mn);  
    a.add += b.add;
    return a;
}

struct Max {
    int val, se, his, cnt;
} tmpmx;

Max operator+ (Max a, Max b) {
    if (a.val == b.val) {
        a.se = max(a.se, b.se);
        a.cnt = a.cnt + b.cnt;
    } else if (a.val < b.val) {        
        a.cnt = b.cnt;
        a.se = max(a.val, b.se);
    } else {
        a.se = max(a.se, b.val);
    }   
    a.val = max(a.val, b.val);
    a.his = max(a.his, b.his);
    return a;
}

struct Min {
    int val, se, his, cnt;
} tmpmn;

Min operator+ (Min a, Min b) {
    if (a.val == b.val) {
        a.se = min(a.se, b.se);
        a.cnt = a.cnt + b.cnt;
    } else if (a.val > b.val) {
        a.se = min(a.val, b.se);    
        a.cnt = b.cnt;
    } else {
        a.se = min(a.se, b.val);
    } 
    a.val = min(a.val, b.val);    
    a.his = min(a.his, b.his);
    return a;
}

struct Node {
    int l, r;
    i64 sum;
    Max mx;
    Min mn;
    Tag tmx, tmn, oth;
    void cleartag() {
        tmx.clear();
        tmn.clear();
        oth.clear();
    }
} tr[N << 2];
int n, m;
int w[N];

#define ls (u << 1)
#define rs (u << 1 | 1)

void pushup(int u) {
    tr[u].mx = tr[ls].mx + tr[rs].mx;
    tr[u].mn = tr[ls].mn + tr[rs].mn;
    tr[u].sum = tr[ls].sum + tr[rs].sum;
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        tr[u].sum = w[l];
        tr[u].mn = {w[l], inf, w[l], 1};
        tr[u].mx = {w[l], -inf, w[l], 1};
        return;
    } 
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void pushmn(Node& u, Tag t) {    
    u.sum += 1ll * t.add * u.mn.cnt;
    u.mn.his = min(u.mn.his, u.mn.val + t.mn);
    if (tmpmn.val == tmpmx.se) u.mx.se += t.add;
    u.mn.val += t.add;
    u.tmn = u.tmn + t;
}

void pushmx(Node& u, Tag t) {
    if (tmpmn.val != tmpmx.val) u.sum += 1ll * t.add * u.mx.cnt;
    u.mx.his = max(u.mx.his, u.mx.val + t.mx);
    if (tmpmn.se == tmpmx.val) u.mn.se += t.add;
    u.mx.val += t.add;
    u.tmx = u.tmx + t;
}

void pushoth(Node& u, Tag t) {
    int cnt = u.r - u.l + 1;
    if (tmpmn.val == tmpmx.val) cnt -= u.mx.cnt;
    else cnt -= u.mx.cnt + u.mn.cnt;
    u.sum += 1ll * t.add * cnt;
    if (tmpmn.se != tmpmx.val && u.mn.se != inf) u.mn.se += t.add;
    if (tmpmx.se != tmpmn.val && u.mx.se != -inf) u.mx.se += t.add;
    u.oth = u.oth + t;
}

void pushall(Node& u, Tag t) {
    u.sum += 1ll * t.add * (u.r - u.l + 1);
    if (u.mx.se != -inf) u.mx.se += t.add;
    if (u.mn.se != inf) u.mn.se += t.add;
    u.mx.his = max(u.mx.his, u.mx.val += t.add);
    u.mn.his = min(u.mn.his, u.mn.val += t.add);
    u.tmn = u.tmn + t;
    u.tmx = u.tmx + t;
    u.oth = u.oth + t;
}

void pushdown(int x) {
    Node &u = tr[x], &l = tr[x << 1], &r = tr[x << 1 | 1];

    int mn = min(l.mn.val, r.mn.val);
    int mx = max(l.mx.val, r.mx.val);

    tmpmn = l.mn, tmpmx = l.mx;
    if (l.mn.val == mn) pushmn(l, u.tmn);
    else if (l.mn.val == mx) pushmn(l, u.tmx);
    else pushmn(l, u.oth);
    if (l.mx.val == mx) pushmx(l, u.tmx);
    else if (l.mx.val == mn) pushmx(l, u.tmn);
    else pushmx(l, u.oth);  
    pushoth(l, u.oth);

    tmpmn = r.mn, tmpmx = r.mx;
    if (r.mn.val == mn) pushmn(r, u.tmn);
    else if (r.mn.val == mx) pushmn(r, u.tmx);
    else pushmn(r, u.oth);
    if (r.mx.val == mx) pushmx(r, u.tmx);
    else if (r.mx.val == mn) pushmx(r, u.tmn);
    else pushmx(r, u.oth);  
    pushoth(r, u.oth);

    u.cleartag();
}

void cmax(int u, int l, int r, int v) {  
    if (tr[u].mn.val >= v) return;
    if (tr[u].l >= l && tr[u].r <= r && tr[u].mn.se > v) {
        v -= tr[u].mn.val;   
        tmpmx = tr[u].mx, tmpmn = tr[u].mn;
        if (tr[u].mx.val == tr[u].mn.val) pushmx(tr[u], {v, v, v});
        return pushmn(tr[u], {v, v, v});
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) cmax(u << 1, l, r, v);
    if (r > mid) cmax(u << 1 | 1, l, r, v);
    pushup(u);
}

void cmin(int u, int l, int r, int v) {    
    if (tr[u].mx.val <= v) return; 
    if (tr[u].l >= l && tr[u].r <= r && tr[u].mx.se < v) {
        v -= tr[u].mx.val;    
        tmpmx = tr[u].mx, tmpmn = tr[u].mn;
        if (tr[u].mx.val == tr[u].mn.val) pushmn(tr[u], {v, v, v});
        return pushmx(tr[u], {v, v, v});
    }  
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1; 
    if (l <= mid) cmin(u << 1, l, r, v);
    if (r > mid) cmin(u << 1 | 1, l, r, v);
    pushup(u);
}

void add(int u, int l, int r, int v) {
    if (tr[u].l >= l && tr[u].r <= r) 
        return pushall(tr[u], {v, v, v});
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) add(u << 1, l, r, v);
    if (r > mid) add(u << 1 | 1, l, r, v);
    pushup(u);
}

int query_mn(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].mn.val;
    int mid = tr[u].l + tr[u].r >> 1, res = inf;
    pushdown(u);
    if (l <= mid) res = min(res, query_mn(u << 1, l, r));
    if (r > mid) res = min(res, query_mn(u << 1 | 1, l, r));
    return res;
}

int query_hmn(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].mn.his;
    int mid = tr[u].l + tr[u].r >> 1, res = inf;
    pushdown(u);
    if (l <= mid) res = min(res, query_hmn(u << 1, l, r));
    if (r > mid) res = min(res, query_hmn(u << 1 | 1, l, r));
    return res;
}

int query_hmx(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].mx.his;
    int mid = tr[u].l + tr[u].r >> 1, res = -inf;
    pushdown(u);
    if (l <= mid) res = max(res, query_hmx(u << 1, l, r));
    if (r > mid) res = max(res, query_hmx(u << 1 | 1, l, r));
    return res;
}

i64 query_sum(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    i64 res = 0;
    pushdown(u);
    if (l <= mid) res += query_sum(u << 1, l, r);
    if (r > mid) res += query_sum(u << 1 | 1, l, r);
    return res;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    build(1, 1, n);
    while (m--) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> x;
            add(1, l, r, x);
        }
        if (op == 2) {
            cin >> x;
            cmax(1, l, r, x);
        }
        if (op == 3) {
            cout << query_mn(1, l, r) << '\n';
        }
        if (op == 4) {
            cout << query_hmn(1, l, r) << '\n';
        }
        if (op == 5) {
            cin >> x;
            cmin(1, l, r, x);
        }
        if (op == 6) {
            cout << query_hmx(1, l, r) << '\n';
        }
        if (op == 7) {
            cout << query_sum(1, l, r) << '\n';
        }
    }
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

const int N = 1000010;

using i64 = long long;

struct Node{
    int l, r;
    int val;
    int sz;
} tr[N * 40];
int nodes[N * 40], tt;
int n, m, k;
int root[N], idx;
int a[N], q[N];
vector<int> pos[N];

int new_node(int val) {
    int u = tt ? nodes[tt--] : ++idx;
    tr[u].l = tr[u].r = 0;
    tr[u].val = val;
    tr[u].sz = 1;
    return u;
}

void pushup(int u) {
    tr[u].sz = tr[tr[u].l].sz + tr[tr[u].r].sz + 1;
}

int build(int l, int r) {
    if (l > r) return 0;
    int mid = l + r >> 1;   
    int u = new_node(q[mid]);
    tr[u].l = build(l, mid - 1);
    tr[u].r = build(mid + 1, r);
    pushup(u);
    return u;
}

void split(int u, int val, int &x, int &y) {
    if (!u) return x = y = 0, void();
    if (tr[u].val <= val) {
        x = u;
        split(tr[u].r, val, tr[u].r, y);
        pushup(x);
    } else {
        y = u;
        split(tr[u].l, val, x, tr[u].l);
        pushup(y);
    }
}

int merge(int x, int y) {
    if (!x or !y)  return x | y;    
    if (rand() % (tr[x].sz + tr[y].sz) < tr[x].sz) {
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    } else {
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
    return 0;
}

struct Fenwick {
    i64 tr[N];
    inline int lowbit(int x) {
        return x & -x;
    }
    inline void add(int x, int v) {
        for (; x <= n; x += lowbit(x))
            tr[x] += v;
    }
    inline i64 ask(int x) {
        i64 res = 0;
        for (; x; x -= lowbit(x))
            res += tr[x];
        return res;
    }
    inline i64 ask(int l, int r) {
        return ask(r) - ask(l - 1);
    }
} t;

void divide(int pos, int x) {
    t.add(pos, a[pos] / x - a[pos]);
    a[pos] /= x;
}

void dfs(int u, int x) {
    if (!u) return;
    dfs(tr[u].l, x);
    if (a[tr[u].val] % x == 0) divide(tr[u].val, x);
    if (a[tr[u].val] % x == 0) q[++k] = tr[u].val;
    dfs(tr[u].r, x);
    nodes[++tt] = u;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = 1; j * j <= a[i]; j++) {
            if (a[i] % j == 0) {
                if (j != 1) pos[j].emplace_back(i);
                if (j != a[i] / j) pos[a[i] / j].emplace_back(i);
            }
        }
        t.add(i, a[i]);
    }
    for (int i = 2; i <= 1000000; i++) {
        k = 0;
        for (auto p : pos[i]) q[++k] = p;
        root[i] = build(1, k);
    }
    while (m--) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> x;
            int p1, p2, p3;   
            split(root[x], l - 1, p1, p2); 
            split(p2, r, p2, p3);
            k = 0;  
            dfs(p2, x);
            p2 = build(1, k); 
            root[x] = merge(merge(p1, p2), p3); 
        }
        if (op == 2) {
            cout << t.ask(l, r) << '\n';
        }
    }
    return 0;
}