template

 2020.06.17 16:34  2023.09.01 18:14  ACM  Template 󰈭 21385字

1 字符串

trie树

实现一：数组实现的按键查找

 1const int maxn = 2e5 + 10;
 2const int maxsize = 26;
 3struct TRIE{
 4    int ch[maxn][maxsize];
 5    int flag[maxn];
 6    int top = 1;
 7
 8    //按照实际条件进行修改
 9    inline int getid(char c){return c - 'a';}
10
11    //插入长度为n的字符串s[0,..n - 1]
12    void insert(char s[maxn], int n){
13        int u = 0;
14        for(int i = 0; i < n; i++){
15            int id = getid(s[i]);
16            if(!ch[u][id]) ch[u][id] = top++;
17            u = ch[u][id];
18        }
19        flag[u] = 1;
20    }
21
22    bool query(char s[maxn], int n){
23        int u = 0;
24        for(int i = 0; i < n; i++){
25            int id = getid(s[i]);
26            if(!ch[u][id]) return false;
27            u = ch[u][id];
28        }
29        if(flag[u]) return true; return false;
30    }
31};

实现二：数组实现的按边查找（左儿子右兄弟优化）

 1const int maxn = 2e5 + 10;
 2const int maxsize = 26;
 3const int maxnode = maxn * maxsize;
 4struct TRIE{
 5//    vector<int> head, next;
 6//    vector<char> ch;
 7    int head[maxnode], next[maxnode];
 8    char ch[maxnode];
 9    bool flag[maxnode];
10    int top = 1;
11    
12    void insert(char s[maxn], int n){
13        int u = 0;
14        for(int i = 0; i < n; i++){
15            int find = 0, v;
16            for(v = head[u]; v; v = next[v]) if(ch[v] == s[i]){
17                find = 1; break;
18            }
19            if(!find){
20                v = top++;
21                ch[v] = s[i];
22                next[v] = head[u];
23                head[u] = v;
24            }
25            u = v;
26        }
27        flag[u] = 1;
28    }
29    
30    bool query(char s[maxn], int n){
31        int u = 0;
32        for(int i = 0; i < n; i++){
33            int find = 0;
34            for(int v = head[u]; v; v = next[v]) if(ch[v] == s[i]){
35                find = 1; u = v; break;
36            }
37            if(!find) return false;
38        }
39        if(flag[u]) return true; return false;
40    }
41};

实现二倒是第一次见，与实现一的区别大概就是邻接表与邻接矩阵的区别。

在对于空间要求更加特殊的环境中可以用实现二优化空间~~然而总感觉不用vector的话空间消耗比实现一更大？~~，具体的情况等以后遇到了再修改板子。

Manacher

 1/*
 2 Manacher算法
 3 读入一个字符串temp及其长度n;
 4 该算法构造出s并赋予截断标志, 自动初始化、获得数组p[i];
 5 对于某个位置i∈[0, 2 * n], 以i为中心的回文串的参数如下:
 6    int start = (i / 2) - (p[i] / 2) + (i & 1), d = p[i] - 1;
 7 */
 8int n;
 9char temp[maxn], s[maxn << 1];
10int p[maxn << 1];
11void manacher(){
12    //scanf("%s", temp);
13    for(int i = 0; i < n; i++){
14        s[i << 1] = '#'; s[i << 1 | 1] = temp[i];
15    }
16    s[n << 1] = '#'; s[n << 1 | 1] = 0;
17    
18    int id = 0, right = 0;
19    for(int i = 0; i <= n << 1; i++) p[i] = 1;
20    for(int i = 1; i <= n << 1; i++){
21        if(i <= right) p[i] = min(right - i + 1, p[2 * id - i]);
22        while(i + p[i] <= 2 * n && i - p[i] >= 0 && s[i + p[i]] == s[i - p[i]])
23            p[i]++;
24        if(right < i + p[i] - 1){
25            id = i; right = i + p[i] - 1;
26        }
27    }
28}

KMP

 1//注意，从1开始编号！
 2int nxt[maxn];
 3void kmp(char s[maxn], int n){
 4    memset(nxt, 0, sizeof nxt); 
 5    for(int i = 2; i <= n; i++){
 6        int p = nxt[i - 1];
 7        while(p > 0 && s[p + 1] != s[i]) p = nxt[p];
 8        if(s[p + 1] == s[i]) p++;
 9        nxt[i] = p;
10    }
11}

AC自动机

 1const int maxn = 2e5 + 10;
 2const int N = 30;
 3
 4char s[maxn * 10];
 5int ch[maxn][N], top = 1;
 6int fail[maxn];
 7
 8int pos[maxn];
 9
10void insert(char *s, int id){
11    int p = 0;
12    for(int i = 0; s[i]; i++){
13        if(!ch[p][s[i] - 'a']) ch[p][s[i] - 'a'] = top++;
14        p = ch[p][s[i] - 'a'];
15    }
16    pos[id] = p;
17}
18
19queue<int> q;
20void getfail(){
21    for(int i = 0; i < N; i++) if(ch[0][i]){
22        fail[ch[0][i]] = 0;
23        q.push(ch[0][i]);
24    }
25    while(!q.empty()){
26        int now = q.front(); q.pop();
27        for(int i = 0; i < N; i++){
28            if(ch[now][i]){
29                fail[ch[now][i]] = ch[fail[now]][i];
30                q.push(ch[now][i]);
31            }
32            else ch[now][i] = ch[fail[now]][i];
33        }
34    }
35}
36
37struct star{int to, next;}edge[maxn];
38int head[maxn], _top = 0, sze[maxn];
39void add(int u, int v){
40    edge[_top].to = v;
41    edge[_top].next = head[u];
42    head[u] = _top++;
43}
44
45void dfs(int now){
46    for(int i = head[now]; ~i; i = edge[i].next){
47        int to = edge[i].to; dfs(to);
48        sze[now] += sze[to];
49    }
50}
51
52
53int main(){
54//    Fastin;
55    clr(head, -1);
56    int n; scanf("%d", &n);
57    for(int i = 1; i <= n; i++){
58        scanf("%s", s); insert(s, i);
59    }
60    getfail();
61    
62    scanf("%s", s);
63    for(int i = 0, p = 0; s[i]; i++){
64        p = ch[p][s[i] - 'a'];
65        sze[p]++;
66    }
67    
68    for(int i = 1; i < top; i++) add(fail[i], i); dfs(0);
69    for(int i = 1; i <= n; i++) printf("%d\n", sze[pos[i]]);
70    
71    return 0;
72}

查询在主串中所有模式串出现的次数。

不能暴力跳fail进行匹配，对于主串的每一个位置有可能fail遍历所有深度（如aaaaaaa)，因而建fail树记录并每一个节点被直接访问的次数，最后dfs求得节点所在的子树总共的访问次数即可。

回文树

 1const int maxn = 3e5 + 10;
 2const int N = 26 + 10;
 3char s[maxn];
 4
 5int len[maxn], fail[maxn];
 6int ch[maxn][N], top;
 7
 8void ini(){fail[1] = fail[0] = 1; len[1] = -1; top = 2;}
 9
10//插入字符s[n]
11int getfail(int x, int n){
12    while(s[n - 1 - len[x]] != s[n]) x = fail[x];
13    return x;
14}
15
16//下标从1开始
17void build(char s[maxn]){
18    ini();
19    //选取一个保证不会出现的字符。
20    s[0] = -1;
21    //last维护了以s[n - 1]结尾的最长回文子串的节点标号。
22    int last = 0;
23    for(int i = 1; s[i]; i++){
24        s[i] -= 'a';
25        int p = getfail(last, i);
26        if(!ch[p][s[i]]){
27            len[top] = len[p] + 2;
28            fail[top] = ch[getfail(fail[p], i)][s[i]];
29            ch[p][s[i]] = top;
30            top++;
31        }
32        last = ch[p][s[i]];
33    }
34}

2 计算几何

已知平面圆上三点求圆心及其半径

 1void cal(double x1, double y1, double x2, double y2, double x3, double y3){
 2    double a, b, c, d, e, f;
 3    a = 2 * (x2 - x1);
 4    b = 2 * (y2 - y1);
 5    c = x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1;
 6    d = 2 * (x3 - x2);
 7    e = 2 * (y3 - y2);
 8    f = x3 * x3 + y3 * y3 - x2 * x2 - y2 * y2;
 9    
10    double x, y, r;
11    x = (b * f - e * c)/(b * d - e * a);
12    y = (d * c - a * f)/(b * d - e * a);
13    r = sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
14}

证明方法是做差解二元一次方程的行列式表达。

根据实际需要将函数中的x, y, r的值进行转移(~~要是再加入3个替身变量就好长的列表~~)。

平面上圆的k次交

 1const int manx = 1e2 + 10;
 2const double eps = 1e-8;
 3const double pi = acos(-1);
 4
 5inline int sgn(double x){return x < -eps? -1: x > eps? 1: 0;}
 6inline double sqr(double x){return x * x;}
 7
 8struct CIRCLE{
 9    double x, y, r, angle;
10    int d;
11    CIRCLE(){d = 1; angle = 0;}
12    CIRCLE(double _x, double _y, double _angle = 0, int _d = 0){
13        x = _x; y = _y; angle = _angle; d = _d; r = 0;
14    }
15    bool operator < (const CIRCLE &b)const{
16        return sgn(r - b.r) == -1;
17    }
18};
19
20inline double dis(CIRCLE a, CIRCLE b){return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
21inline double cross(CIRCLE a, CIRCLE b, CIRCLE c){
22    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
23}
24
25//有两个交点返回true，以及两个交点的坐标和方位角，p1按照顺时针，p2按照逆时针
26bool cir_inter_cir(CIRCLE a, CIRCLE b, CIRCLE &p1, CIRCLE &p2){
27    double d = dis(a, b);
28    if(sgn(d - a.r - b.r) >= 0 || sgn(abs(b.r - a.r) - d) >= 0) return false;
29    double cosa = (sqr(a.r) + sqr(d) - sqr(b.r)) / (2 * a.r * d);
30    double sina = sqrt(max(0., 1. - sqr(cosa)));
31    //旋转矩阵 [cosa, -sina; sina, cosa]
32    p1 = p2 = a;
33    p1.x += a.r / d * ((b.x - a.x) * cosa + (b.y - a.y) * -sina);
34    p1.y += a.r / d * ((b.x - a.x) * sina + (b.y - a.y) * cosa);
35    p2.x += a.r / d * ((b.x - a.x) * cosa + (b.y - a.y) * sina);
36    p2.y += a.r / d * ((b.x - a.x) * -sina + (b.y - a.y) * cosa);
37    return true;
38}
39
40bool cmp(const CIRCLE &a, const CIRCLE &b){
41    if(sgn(a.angle - b.angle)) return sgn(a.angle - b.angle) == -1;
42    else return a.d > b.d;
43}
44
45double cal(CIRCLE a, CIRCLE p1, CIRCLE p2){
46    double ans = sqr(a.r) * (p2.angle - p1.angle) - cross(a, p1, p2) + cross(CIRCLE(0, 0), p1, p2);
47    return ans / 2;
48}
49
50CIRCLE dot[maxn << 1];
51double area[maxn];
52void cirunion(CIRCLE cir[], int n){
53    sort(cir, cir + n);
54    //记录每个圆被完全覆盖的次数，初始值显然为1
55    for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++)
56        if(sgn(dis(cir[i], cir[j]) + cir[i].r - cir[j].r) <= 0) cir[i].d++;
57    CIRCLE p1, p2;
58    for(int i = 0; i < n; i++){
59        //针对每一个圆考虑它与所有其他圆的交
60        int cnt = 0, top = 0;
61        for(int j = 0; j < n; j++){
62            if(i == j) continue;
63            if(!cir_inter_cir(cir[i], cir[j], p1, p2)) continue;
64            p1.angle = atan2(p1.y - cir[i].y, p1.x - cir[i].x);
65            p2.angle = atan2(p2.y - cir[i].y, p2.x - cir[i].x);
66            p1.d = -1; p2.d = 1;
67            dot[top++] = p1; dot[top++] = p2;
68            if(sgn(p2.angle - p1.angle) == 1) cnt++;
69        }
70        
71        //加入起点终点位置
72        dot[top++] = CIRCLE(cir[i].x - cir[i].r, cir[i].y, -pi, -2);
73        dot[top++] = CIRCLE(cir[i].x - cir[i].r, cir[i].y, pi, 2);
74        sort(dot, dot + top, cmp);
75        int now = cir[i].d + cnt;
76        for(int j = 1; j < top; j++){
77            area[now] += cal(cir[i], dot[j - 1], dot[j]);
78            now += dot[j].d;
79        }
80    }
81}
82
83CIRCLE cir[maxn];
84int main(){
85//    Fastin;
86    int t; scanf("%d", &t); while(t--){
87        clr(area, 0);
88        int n; scanf("%d", &n);
89        for(int i = 0; i < n; i++) scanf("%lf %lf %lf", &cir[i].x, &cir[i].y, &cir[i].r);
90        cirunion(cir, n);
91        for(int i = 1; i <= n; i++) printf("%.5f\n", area[i]);
92    }
93    return 0;
94}

凸包周长

 1const int maxn = 1e2 + 10;
 2const double eps = 1e-9;
 3
 4struct POINT{
 5    double x, y;
 6    POINT operator - (const POINT &b){
 7        POINT temp;
 8        temp.x = x - b.x;
 9        temp.y = y - b.y;
10        return tmep;
11    }
12}p[maxn];
13
14double cross(POINT a, POINT b){ return a.x * b.y - a.y * b.x;}
15double dis(POINT a){return sqrt(a.x * a.x + a.y * a.y);}
16int sgn(double x){return x < -eps? -1: x > eps? 1: 0;}
17bool cmp(POINT a, POINT b){
18    int flag = sgn(cross(a, b));
19    if(flag == 0) return dis(a) < dis(b);
20    else return flag == 1;
21}
22
23int sta[maxn], top = 0;
24void push(int x){sta[top++] = x;}
25
26int main(){
27    // Fastin;
28    int n; while(~scnaf("%d", &n) && n){
29        top = 0; int id = -1;
30        for(int i = 1; i <= n ; i++){
31            int x, y; scnaf("%d %d", &x, &y);
32            p[i].x = x; p[i].y = y;
33            if(id == -1 || (p[id].x > p[i].x) || (p[id].x == p[i].x && p[id].y > p[i].y)) id = i;
34        }
35
36        //不特判计算几何的都是xx!
37        if(n == 1){puts("0.00"); continue;}
38        if(n == 2){printf("%.2f\n", dis(p[1] - p[2])); continue;}
39
40        for(int i = 1; i <= n; i++) if(i != id) p[i] = p[i] - p[id];
41        p[id].x = p[id].y = 0;
42        sort(p + 1, p + 1 + n, cmp);
43
44        push(1); push(2);
45        for(int i = 3; i <= n; i++){
46            while(1){
47                if(sgn(cross(p[i] - p[sta[top - 2]], p[i] - p[sta[top - 1]])) >= 0){
48                    push(i); break;
49                }
50                else top--;
51            }
52        }
53
54        double ans = 0;
55        for(int i = 1; i < top; i++) ans += dis(p[sta[i]] - p[sta[i - 1]]);
56        ans += dis(p[sta[0]] - p[sta[top - 1]]);
57        printf("%.2f\n", ans);
58    }
59    return 0;
60}

复杂度$O(nlogn)$

求周长需要循环地求一遍栈中相邻两个元素的距离！不要漏求sta[0]与sta[top - 1]！

3 图论

最短路

01bfs

1while(双端队列非空){
2  取出队首元素now
3  for(now的相邻节点){
4    更新距离
5    if(边权为0) 添加到队首
6    else 添加到队尾
7  }
8}

当图中边权仅为0或1时，可以使用01bfs解决单源最短路问题。

时间复杂度$O(V+E)$

tarjan

scc

 1const int maxn = 2e5 + 10;
 2
 3star edge[maxn << 1];
 4int head[manx], top = 0;
 5
 6void add(int u, int v){
 7    edge[top].to = v;
 8    edge[top].next = head[u];
 9    head[u] = top++;
10}
11
12stack<int> sta;
13int dfn[maxn], low[maxn], cnt = 1, in[maxn];
14void tarjan(int u){
15
16    dfn[u] = low[u] = cnt++;
17    sta.push(u); in[u] = 1;
18    for(int i = head[u]; ~i; i = edge[i].next){
19        int to = edge[i].to;
20        if(!dfn[to]){
21            tarjan(to);
22            low[u] = min(low[to], low[u]);
23        }
24        else if(in[to]){
25            low[u] = min(low[u], dfn[to]);
26        }
27    }
28
29    //输出以u节点为根的scc
30    if(dfn[u] == low[u]){
31        while(1){
32            assert(!sta.empty());
33
34            int v = sta.top(); sta.pop();
35            printf("%d ", v); in[v] = 0;
36
37            if(v == u){puts(""); break;}
38        }
39    }
40}
41
42int main(){
43    // Fastin;
44    clr(head, -1);
45    int n, m; scanf("%d %d", &n, &m);
46    for(int i = 0 ; i< m; i++){
47        int u, v; scanf("%d %d", &u, &v);
48        add(u, v);
49    }
50
51    tarjan(1);
52    return 0;
53}

异或MST （Boruvka算法）

 1const int maxn = 2e5 + 10;
 2const int N = 30;
 3const int inf = ~0u >> 1;
 4
 5int n, w[maxn], c[maxn];;
 6
 7int ch[maxn * N][2], sze = 1;
 8
 9void insert(int x){
10    int p = 0;
11    for(int i = N - 1; i >= 0; i--){
12        int id = (x >> i) & 1;
13        if(ch[p][id] == 0) ch[p][id] = sze++;
14        p = ch[p][id];
15    }
16}
17
18int query(int x){
19    int p = 0, ans = 0;
20    for(int i = N - 1; i >= 0; i--){
21        int id = (x >> i) & 1;
22        if(ch[p][id] > 0) p = ch[p][id];
23        else{
24            ans |= 1 << i;
25            p = ch[p][id ^ 1];
26        }
27    }
28    return ans;
29}
30
31ll ans = 0;
32void sove(int d, int l, int r){
33    if(l < 1 || r > n || l > r || d < 0) return;
34    
35    int L = l - 1, R = r + 1;
36    for(int i = l; i <= r; i++)
37        if(w[i] & 1 << d) c[--R] = w[i];
38        else c[++L] = w[i];
39    for(int i = l; i <= r; i++) w[i] = c[i];
40    
41    sove(d - 1, l, L);
42    sove(d - 1, R, r);
43    if(L < l || R > r) return;
44    
45    for(int i = l; i <= L; i++) insert(w[i]);
46    int m = inf;
47    for(int i = R; i <= r; i++) m = min(m, query(w[i]));
48    ans += m;
49    
50    for(int i = 0; i < sze; i++) ch[i][0] = ch[i][1] = 0;
51    sze = 1;
52}
53
54int main(){
55//    Fastin;
56    scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", w + i);
57    sove(N - 1, 1, n);
58    printf("%lld\n", ans);
59    return 0;
60}

模板规定节点从1开始标号，点权$w_i<2^{30}$，具体题目应该结合范围进行具体分析。

图的匹配

二分图最大匹配

匈牙利算法

 1const int manx = 510;
 2
 3int n, n1, n2, m;
 4int head[maxn << 1], top = 0;
 5struct star{int to, next;};
 6star edge[maxn * maxn];
 7void add(int u, int v){
 8    edge[top].to = v;
 9    edge[top].next = head[u];
10    head[u] = top++;
11}
12
13int vis[maxn << 1], match[maxn << 1];
14bool find(int u){
15    for(int i = head[u]; ~i; i = edge[i].next) if(!vis[edge[i].to]){
16        int to = edge[i].to; vis[to] = 1;
17        if(!match[to] || find(match[to])){
18            match[to] = u;
19            return 1;
20        }
21    }
22    return 0;
23}
24
25
26int hungary(){
27    int ans = 0;
28    for(int i = 1; i <= n; i++){
29        clr(vis, 0);
30        if(find(i)) ans++;
31    }
32    return ans;
33}
34
35int ans[maxn];
36
37int main(){
38//    Fastin;
39    clr(head, -1);
40 		//读入n1, n2, m, 表示两边点集的数量和边数，取n = max(n1, n2)作为序号的偏移量。
41    scanf("%d %d %d", &n1, &n2, &m); n = max(n1, n2);
42    for(int i = 0; i < m; i++){
43        int u, v; scanf("%d %d", &u, &v);
44        add(u, v + n);
45    }
46    
47    printf("%d\n", hungary());
48    for(int i = 1; i <= n2; i++) ans[match[i + n]] = i;
49    prt(ans + 1, n1);
50    return 0;
51}

匈牙利算法，两边点集大小均为maxn，因而有关数组需要开至2倍甚至更多。

复杂度$O(nm)$

每次为ai分配路径的时候都要对vis数组初始化，多组数据的时候复杂度会变成O(Tmaxn), 记得改掉memset！

最大流(Dinic实现)

 1const itn maxn = 1200 + 10;
 2const int maxe = 120000 + 10;
 3const ll inf = 1ll << 60;
 4
 5struct star {
 6    int to, next, w;
 7};
 8int head[maxn], top = 0;
 9star edge[maxe << 1];
10
11void add(int u, int v, int w) {
12    edge[top].to = v;
13    edge[top].next = head[u];
14    edge[top].w = w;
15    head[u] = top++;
16}
17
18int d[maxn], cur[maxn];
19ll dfs(int s, int t, ll flow) {
20    if (flow == 0 || s == t)
21        return flow;
22
23    ll res = 0, f;
24    for (int i = cur[s]; ~i; i = edge[i].next) {
25        cur[s] = i;
26        if (d[edge[i].to] == d[s] + 1) {
27            f = dfs(edge[i].to, t, min(flow, (ll)edge[i].w));
28            edge[i].w -= f;
29            edge[i ^ 1].w += f;
30            res += f;
31            flow -= f;
32            if (flow == 0)
33                break;
34        }
35    }
36    return res;
37}
38
39queue<int> q, q0;
40bool bfs(int s, int t) {
41    clr(d, 0);
42    q = q0;
43    q.push(s);
44    cur[s] = head[s];
45    d[s] = 1;
46    while (!q.empty()) {
47        int now = q.front();
48        q.pop();
49        for (int i = head[now]; ~i; i = edge[i].next)
50            if (!d[edge[i].to] && edge[i].w > 0) {
51                cur[edge[i].to] = head[edge[i].to];
52                d[edge[i].to] = d[now] + 1;
53                if (edge[i].to == t)
54                    return true;
55                q.push(edge[i].to);
56            }
57    }
58    return false;
59}
60
61ll dinic(int s, int t) {
62    ll ans = 0;
63    while (bfs(s, t)) ans += dfs(s, t, inf);
64    return ans;
65}
66
67
68int main(){
69//    Fastin;
70    clr(head, -1);
71     //读入n1, n2, m, 表示两边点集的数量和边数，取n = max(n1, n2)作为序号的偏移量。
72    int n1, n2, m, n;
73    scanf("%d %d %d", &n1, &n2, &m); n = max(n1, n2);
74    for(int i = 0; i < m; i++){
75        int u, v; scanf("%d %d", &u, &v);
76        add(u, v + n, 1);
77        add(v + n, u, 0);
78    }
79    for(int i = 1; i <= n1; i++){add(0, i, 1); add(i, 0, 0);}
80    for(int i = 1; i <= n2; i++){add(i + n, 2 * n + 1, 1); add(2 * n + 1, i + n, 0);}
81    
82    printf("%lld\n", dinic(0, 2 * n + 1));
83    return 0;
84}

可以证明，Dinic实现二分图的最大流复杂度$O(\sqrt n m)$，比朴素的匈牙利算法要快上一些。

不过如果使用了网络流算法可能就不能找出匹配方案了。

二分图最大权匹配

 1const int maxn = 410;
 2const int inf = 0x3f3f3f3f;
 3int a[maxn][maxn];
 4
 5int n;
 6int match[maxn];
 7int ex[2][maxn], vis[2][maxn];;
 8int slack[maxn];
 9
10int dfs(int now){
11    vis[0][now] = 1;
12    for(int i = 0; i < n; i++) if(!vis[1][i]){
13        int gap = ex[0][now] + ex[1][i] - a[now][i];
14        if(gap == 0){
15            vis[1][i] = 1;
16            if(match[i] == -1 || dfs(match[i])){ match[i] = now; return 1; }
17        }
18        else slack[i] = min(slack[i], gap);
19    }
20    return 0;
21}
22
23ll km(){
24    for(int i = 0; i < n; i++){match[i] = -1; ex[0][i] = ex[1][i] = 0;}
25    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) ex[0][i] = max(ex[0][i], a[i][j]);
26    
27    for(int i = 0; i < n; i++){
28        for(int i = 0; i < n; i++) slack[i] = inf;
29        
30        for(int i = 0; i < n; i++) vis[0][i] = vis[1][i] = 0;
31        if(dfs(i)) continue;
32        while(1){
33            int d = inf; for(int i = 0; i < n; i++) if(!vis[1][i]) d = min(d, slack[i]);
34            int pos = -1;
35            for(int i = 0; i < n; i++){
36                if(vis[0][i]) ex[0][i] -= d;
37                if(vis[1][i]) ex[1][i] += d;
38                else{
39                    slack[i] -= d;
40                    if(slack[i] == 0) pos = i;
41                }
42            }
43            assert(pos != -1);
44            if(match[pos] == -1) break;
45            int u = match[pos];
46            vis[0][u] = vis[1][pos] = 1;
47            for(int i = 0; i < n; i++) if(!vis[1][i]) slack[i] = min(slack[i], ex[0][u] + ex[1][i] - a[u][i]);
48        }
49        for(int i = 0; i < n; i++) vis[0][i] = vis[1][i] = 0;
50        dfs(i);
51    }
52    ll res = 0;
53    for(int i = 0; i < n; i++) res += a[match[i]][i];
54    return res;
55}
56
57int ans[maxn];
58int main(){
59//    Fastin;
60    int n1, n2, m; scanf("%d %d %d", &n1, &n2, &m);
61    n = max(n1, n2);
62    for(int i = 0; i < m; i++){
63        int u, v, w; scanf("%d %d %d", &u, &v, &w);
64        u--; v--; a[u][v] = w;
65    }
66    printf("%lld\n", km());
67    
68    for(int i = 0; i < n2; i++){
69        if(match[i] == -1) continue;
70        if(a[match[i]][i] == 0) ans[match[i]] = 0;
71        else ans[match[i]] = i + 1;
72    }
73    for(int i = 0; i < n1; i++) printf("%d ", ans[i]);
74    printf("\n");
75    return 0;
76}

读入左右点数和边数，接下来跟m行有向边及其边权。

点数范围400，边权1e9。

找增广路径的dfs不能放在while循环中，不然成为假算法$O(n^4)$。

为了修改标记使一条可行增广路存在只需要修改slack tag即可，因为只需要在while循环中更新slack即可。

流算法

最大流

dinic (当前弧优化)

 1const itn maxn = 1200 + 10;
 2const int maxe = 120000 + 10;
 3const ll inf = 1ll << 60;
 4
 5struct star {
 6    int to, next, w;
 7};
 8int head[maxn], top = 0;
 9star edge[maxe << 1];
10
11void add(int u, int v, int w) {
12    edge[top].to = v;
13    edge[top].next = head[u];
14    edge[top].w = w;
15    head[u] = top++;
16}
17
18int d[maxn], cur[maxn];
19
20ll dfs(int s, int t, ll flow) {
21    if (flow == 0 || s == t)
22        return flow;
23
24    ll res = 0, f;
25    for (int i = cur[s]; ~i; i = edge[i].next) {
26        cur[s] = i;
27        if (d[edge[i].to] == d[s] + 1) {
28            f = dfs(edge[i].to, t, min(flow, (ll)edge[i].w));
29            edge[i].w -= f;
30            edge[i ^ 1].w += f;
31            res += f;
32            flow -= f;
33            if (flow == 0)
34                break;
35        }
36    }
37    return res;
38}
39
40queue<int> q, q0;
41bool bfs(int s, int t) {
42    clr(d, 0);
43    q = q0;
44    q.push(s);
45    cur[s] = head[s];
46    d[s] = 1;
47    while (!q.empty()) {
48        int now = q.front();
49        q.pop();
50        for (int i = head[now]; ~i; i = edge[i].next)
51            if (!d[edge[i].to] && edge[i].w > 0) {
52                cur[edge[i].to] = head[edge[i].to];
53                d[edge[i].to] = d[now] + 1;
54                if (edge[i].to == t)
55                    return true;
56                q.push(edge[i].to);
57            }
58    }
59    return false;
60}
61
62ll dinic(int s, int t) {
63    ll ans = 0;
64    while (bfs(s, t)) ans += dfs(s, t, inf);
65    return ans;
66}
67
68int main() {
69    //    Fastin;
70    clr(head, -1);
71    int n, m, s, t;
72    scanf("%d %d %d %d", &n, &m, &s, &t);
73    for (int i = 0, u, v, w; i < m; i++) {
74        scanf("%d %d %d", &u, &v, &w);
75        add(u, v, w);
76        add(v, u, 0);
77    }
78    printf("%lld\n", dinic(s, t));
79    return 0;
80}

$O(n^2 m)$

isap (gap优化)

 1const itn maxn = 1200 + 10;
 2const int maxe = 120000 + 10;
 3const ll inf = 1ll << 60;
 4
 5struct star {
 6    int to, next, w;
 7};
 8int n, m, s, t;
 9int head[maxn], top = 0;
10star edge[maxe << 1];
11
12void add(int u, int v, int w) {
13    edge[top].to = v;
14    edge[top].next = head[u];
15    edge[top].w = w;
16    head[u] = top++;
17}
18
19int d[maxn], cur[maxn], gap[maxn];
20
21queue<int> q;
22void bfs(int s, int t) {
23    q.push(t);
24    gap[d[t] = 1]++;
25    cur[t] = head[t];
26    while (!q.empty()) {
27        int now = q.front();
28        q.pop();
29        for (int i = head[now]; ~i; i = edge[i].next)
30            if (!d[edge[i].to]) {
31                gap[d[edge[i].to] = d[now] + 1]++;
32                cur[edge[i].to] = head[edge[i].to];
33                q.push(edge[i].to);
34            }
35    }
36}
37
38ll dfs(int x, int s, int t, ll flow) {
39    if (x == t)
40        return flow;
41
42    ll res = 0, f;
43    for (int i = cur[x]; ~i; i = edge[i].next) {
44        cur[x] = i;
45        if (d[x] == d[edge[i].to] + 1) {
46            f = dfs(edge[i].to, s, t, min(flow, (ll)edge[i].w));
47            edge[i].w -= f;
48            edge[i ^ 1].w += f;
49            flow -= f;
50            res += f;
51            if (flow == 0)
52                return res;
53        }
54    }
55    if (!(gap[d[x]]--))
56        d[s] = n + 1;
57    gap[++d[x]]++;
58    cur[x] = head[x];
59    return res;
60}
61
62ll isap(int s, int t) {
63    bfs(s, t);
64    ll ans = dfs(s, s, t, inf);
65    while (d[s] <= n) ans += dfs(s, s, t, inf);
66    return ans;
67}
68
69int main() {
70    //    Fastin;
71    clr(head, -1);
72    scanf("%d %d %d %d", &n, &m, &s, &t);
73    for (int i = 0, u, v, w; i < m; i++) {
74        scanf("%d %d %d", &u, &v, &w);
75        add(u, v, w);
76        add(v, u, 0);
77    }
78    printf("%lld\n", isap(s, t));
79    return 0;
80}

$O(n^2 m)$

最高标号预流推进HLPP

  1#include <bits/stdc++.h>
  2#define ll long long
  3using namespace std;
  4const int inf = INT_MAX;
  5const ll INF = (0x3f3f3f3f3f3f3f3fll);
  6const int maxn = 1.2e3 + 5;
  7struct HLPP {
  8    struct Edge {
  9        int v, rev;
 10        ll cap;
 11    };
 12    int n, sp, tp, lim, ht, lcnt;
 13    ll exf[maxn];
 14    vector<Edge> G[maxn];
 15    vector<int> hq[maxn], gap[maxn], h, sum;
 16    void init(int nn, int s, int t) {
 17        sp = s, tp = t, n = nn, lim = n + 1, ht = lcnt = 0;
 18        for (int i = 1; i <= n; ++i) G[i].clear(), exf[i] = 0;
 19    }
 20    void add_edge(int u, int v, ll cap) {
 21        G[u].push_back({ v, int(G[v].size()), cap });
 22        G[v].push_back({ u, int(G[u].size()) - 1, 0 });
 23    }
 24    void update(int u, int nh) {
 25        ++lcnt;
 26        if (h[u] != lim)
 27            --sum[h[u]];
 28        h[u] = nh;
 29        if (nh == lim)
 30            return;
 31        ++sum[ht = nh];
 32        gap[nh].push_back(u);
 33        if (exf[u] > 0)
 34            hq[nh].push_back(u);
 35    }
 36    void relabel() {
 37        queue<int> q;
 38        for (int i = 0; i <= lim; ++i) hq[i].clear(), gap[i].clear();
 39        h.assign(lim, lim), sum.assign(lim, 0), q.push(tp);
 40        lcnt = ht = h[tp] = 0;
 41        while (!q.empty()) {
 42            int u = q.front();
 43            q.pop();
 44            for (Edge &e : G[u])
 45                if (h[e.v] == lim && G[e.v][e.rev].cap)
 46                    update(e.v, h[u] + 1), q.push(e.v);
 47            ht = h[u];
 48        }
 49    }
 50    void push(int u, Edge &e) {
 51        if (!exf[e.v])
 52            hq[h[e.v]].push_back(e.v);
 53        ll df = min(exf[u], e.cap);
 54        e.cap -= df, G[e.v][e.rev].cap += df;
 55        exf[u] -= df, exf[e.v] += df;
 56    }
 57    void discharge(int u) {
 58        int nh = lim;
 59        if (h[u] == lim)
 60            return;
 61        for (Edge &e : G[u]) {
 62            if (!e.cap)
 63                continue;
 64            if (h[u] == h[e.v] + 1) {
 65                push(u, e);
 66                if (exf[u] <= 0)
 67                    return;
 68            } else if (nh > h[e.v] + 1)
 69                nh = h[e.v] + 1;
 70        }
 71        if (sum[h[u]] > 1)
 72            update(u, nh);
 73        else {
 74            for (; ht >= h[u]; gap[ht--].clear())
 75                for (int &i : gap[ht]) update(i, lim);
 76        }
 77    }
 78    ll hlpp() {
 79        exf[sp] = INF, exf[tp] = -INF, relabel();
 80        for (Edge &e : G[sp]) push(sp, e);
 81        for (; ~ht; --ht) {
 82            while (!hq[ht].empty()) {
 83                int u = hq[ht].back();
 84                hq[ht].pop_back();
 85                discharge(u);
 86                if (lcnt > (n << 2))
 87                    relabel();
 88            }
 89        }
 90        return exf[tp] + INF;
 91    }
 92} hp;
 93signed main() {
 94    ios::sync_with_stdio(false);
 95    cin.tie(0), cout.tie(0);
 96    int n, m, s, t, u, v, w;
 97    cin >> n >> m >> s >> t;
 98    hp.init(n, s, t);
 99    while (m--) {
100        cin >> u >> v >> w;
101        hp.add_edge(u, v, w);
102    }
103    cout << hp.hlpp() << '\n';
104    return 0;
105}

loj127

偷其板，不知其所以然。

~~甚至不知其然qaq~~

$O(n^2 \sqrt m)$

费用流 (dijstra)

 1const ll inf = 0x3f3f3f3f3f3f3f3f;
 2const int maxn = 410;
 3const int maxe = 2e4 + 10;
 4struct star{
 5    int from, to, next; ll c, w;
 6};
 7int n, m;
 8int head[maxn], top = 0;
 9star edge[maxe << 1];
10
11void add(int u, int v, int c, int w){
12    edge[top].from = u;
13    edge[top].to = v;
14    edge[top].c = c;
15    edge[top].w = w;
16    edge[top].next = head[u];
17    head[u] = top++;
18}
19
20ll dis[maxn], h[maxn];
21int pre[maxn];
22struct NODE{
23    int u; ll d;
24    bool operator <(const NODE &b)const{
25        return d > b.d;
26    }
27};
28priority_queue<NODE> pq, pq0;
29ll mcmf(int s, int t, ll f, ll &flow){
30    ll res = 0;
31    while(f){
32        clr(dis, 0x3f); dis[s] = 0;
33        pq = pq0; pq.push({s, dis[s]});
34        while(!pq.empty()){
35            NODE temp = pq.top(); pq.pop();
36            int u = temp.u; ll d = temp.d;
37            if(dis[u] < d) continue;
38            for(int i = head[u]; ~i; i = edge[i].next){
39                int to = edge[i].to;
40                if(edge[i].c > 0 && dis[to] > dis[u] + edge[i].w + h[u] - h[to]){
41                    dis[to] = dis[u] + edge[i].w + h[u] - h[to];
42                    pre[to] = i;
43                    pq.push({to, dis[to]});
44                }
45            }
46        }
47        if(dis[t] == inf) break;
48        for(int i = 1; i <= n; i++) h[i] += dis[i];
49        
50        ll d = f;
51        for(int now = t; now != s; now = edge[pre[now]].from) d = min(d, edge[pre[now]].c);
52        for(int now = t; now != s; now = edge[pre[now]].from){
53            edge[pre[now]].c -= d;
54            edge[pre[now] ^ 1].c += d;
55        }
56        f -= d; flow += d; res += d * h[t];
57    }
58    return res;
59}
60
61int main(){
62//    Fastin;
63    clr(head, -1);
64    scanf("%d %d", &n, &m);
65    for(int i = 0; i < m; i++){
66        int u, v, c, w; scanf("%d %d %d %d", &u, &v, &c, &w);
67        add(u, v, c, w); add(v, u, 0, -w);
68    }
69    ll flow = 0;
70    ll res = mcmf(1, n, inf, flow);
71    printf("%lld %lld\n", flow, res);
72    return 0;
73}

loj102 单组数据最慢700ms左右

$V<=400, E<=15000$

时间复杂度$O(FElogV)$

线段树优化建图

 1#define mid ((l + r) >> 1)
 2
 3const int maxn = 5e5 + 10;
 4const int maxe = 4e7 + 10;
 5int M;
 6
 7int n, m, p;
 8struct {int to, next, w;}edge[maxe];
 9int head[maxe], top = 0;
10void add(int u, int v, int w){
11    edge[top].to = v;
12    edge[top].w = w;
13    edge[top].next = head[u];
14    head[u] = top++;
15}
16
17
18int cnt = 0, pos[maxn], ls[maxn << 3], rs[maxn << 3];
19int build(int l, int r){
20    int now = cnt++;
21    if(l == r){
22        add(now, now + M, 0);
23        return pos[l] = now;
24    }
25    ls[now] = build(l, mid);
26    add(now, ls[now], 0); add(ls[now] + M, now + M, 0);
27    rs[now] = build(mid + 1, r);
28    add(now, rs[now], 0); add(rs[now] + M, now + M, 0);
29    return now;
30}
31
32
33void update(int p, int l, int r, int L, int R, int u, int type){
34    if(L <= l && r <= R){
35        if(type) add(p + M, u, 1); else add(u, p, 0);
36        return ;
37    }
38    if(L <= mid) update(ls[p], l, mid, L, R, u, type);
39    if(R > mid) update(rs[p], mid + 1, r, L, R, u, type);
40}
41
42int dis[5000000];
43deque<int> q;
44void bfs(){
45    clr(dis, 0x3f);
46    while(!q.empty()) q.pop_back();
47    
48    dis[pos[p]] = 0; q.push_back(pos[p]);
49    while(!q.empty()){
50        int now = q.front(); q.pop_front();
51        
52        for(int i = head[now]; ~i; i = edge[i].next){
53            int to = edge[i].to; if(dis[to] != 0x3f3f3f3f) continue;
54            dis[to] = dis[now] + edge[i].w;
55            if(edge[i].w) q.push_back(to);
56            else q.push_front(to);
57        }
58    }
59}
60
61
62int main(){
63//    Fastin;
64    clr(head, -1);
65    scanf("%d %d %d", &n, &m, &p);
66    M = n << 2; build(1, n);
67    for(int i = 0; i < m; i++){
68        int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
69        //加入虚点i + 2M与i + 1 + 2M;
70        update(0, 1, n, a, b, 2 * i + 2 * M, 1); update(0, 1, n, c, d, 2 * i + 2 * M, 0);
71        update(0, 1, n, c, d, 2 * i + 2 * M + 1, 1); update(0, 1, n, a, b, 2 * i + 2 * M + 1, 0);
72    }
73    bfs();
74    for(int i = 1; i <= n; i++) printf("%d\n", dis[pos[i]]);
75    return 0;
76}

给出n个节点、m种边。

对于某一种边而言，有4个参数：a, b, c, d，表示对于所有的$a \leq x \leq b, c \leq y \leq d$都有一条无向边$<x, y>$相连。

询问对于某个指定点p而言，到其他所有点的最短距离

数据范围 $n \leq 5e5, m \leq 1e5$

4 可持久化

可持久化01-Trie

最基本的版本如下，根据不同的题目可以添加不同的辅助数组。

 1const int N = 30;
 2const itn maxn = 1e5 * N  +10;
 3struct TRIE{
 4    int version = 0, top = 0;
 5    int ch[maxn][2], root[maxn];;
 6    
 7    void insert(int x){
 8        int rot = root[version];
 9        root[++version] = ++top;
10        for(int i = N - 1; i >= 0; i--){
11            int id = (x >> i) & 1;
12            ch[top][id] = top + 1; //新建
13            ch[top][!id] = ch[rot][!id]; //继承
14            top++; rot = ch[rot][id];
15        }
16    }
17};

多维护一个size数组记录当前节点下有多少个串，可用于在任意区间中查找区间中某个数异或上某个给定x的最大值。

 1const int N = 24;
 2const itn maxn = 1e5  +10;
 3
 4struct TRIE{
 5    int version = 0, top = 0;
 6    int ch[maxn][2], root[maxn];;
 7    int size[maxn];
 8    
 9    void insert(int x){
10        int rot = root[version];
11        root[++version] = ++top;
12        for(int i = N - 1; i >= 0; i--){
13            int id = (x >> i) & 1;
14            ch[top][id] = top + 1;
15            ch[top][!id] = ch[rot][!id];
16            size[top] = size[rot] + 1;
17            top++; rot = ch[rot][id];
18        }
19        size[top] = size[rot] + 1;
20    }
21    
22  	//查找[L + 1, R]的结果
23    int query(int L, int R, itn x){
24        int l = root[L], r = root[R];
25        int ans = 0;
26        for(int i = N - 1; i >= 0; i--){
27            int id = (x >> i) & 1;
28            if(size[ch[r][!id]] - size[ch[l][!id]] > 0){
29                ans |= 1 << i;
30                r = ch[r][!id]; l = ch[l][!id];
31            }
32            else{
33                r = ch[r][id];
34                l = ch[l][id];
35            }
36        }
37        return ans;
38    }
39};

可持久化权值线段树静态区间第k大查询

 1#define mid ((l + r) >> 1)
 2const int maxn = 2e5 + 10;
 3const int N = 5;
 4int a[maxn], c[maxn];
 5unordered_map<int, int> mp;
 6int ls[maxn << N], rs[maxn << N], root[maxn], num[maxn << N], top = 0;
 7
 8int build(int l, int r){
 9    int p = top++;
10    if(l == r) return p;
11    ls[p] = build(l, mid);
12    rs[p] = build(mid + 1, r);
13    return p;
14}
15
16int update(int p, int l, int r, int k){
17    int now = top++;
18    ls[now] = ls[p]; rs[now] = rs[p]; num[now] = num[p] + 1;
19    if(l == r) return now;
20    if(k <= mid) ls[now] = update(ls[p], l, mid, k);
21    else rs[now] = update(rs[p], mid + 1, r, k);
22    return now;
23}
24
25int query(int r1, int r2, int l, int r, int k){
26    //[L + 1, R]
27    if(l == r) return l;
28    
29    int x = num[ls[r2]] - num[ls[r1]];
30    if(k <= x) return query(ls[r1], ls[r2], l, mid, k);
31    else return query(rs[r1], rs[r2], mid + 1, r, k - x);
32}
33
34int main(){
35//    Fastin;
36    int n, m; scanf("%d%d", &n, &m);
37    for(int i = 1; i <= n; i++){
38        scanf("%d", a + i);
39        c[i] = a[i];
40    }
41    sort(c + 1, c + 1 + n);
42    int N = (int)(unique(c + 1, c + 1 + n) - (c + 1));
43    for(int i = 1; i <= N; i++) mp[c[i]] = i;
44    
45    root[0] = build(1, N);
46    for(int i = 1; i <= n; i++)
47        root[i] = update(root[i - 1], 1, N, mp[a[i]]);
48    for(int i = 0; i < m; i++){
49        int l, r, k; scanf("%d %d %d", &l, &r, &k);
50        printf("%d\n", c[query(root[l - 1], root[r], 1, N, k)]);
51    }
52    return 0;
53}

BIT套权值线段树带单点修改的区间第k大查询

  1const int maxn = 6e4 + 10;
  2
  3int n, m, N;
  4int a[maxn], b[maxn];
  5struct NODE{int type, x, y, z;};
  6NODE node[maxn];
  7
  8int hsh(int x){return (int)(lower_bound(b + 1, b + N, x) - b);}
  9
 10int s[maxn], rt[maxn], ls[maxn << 5], rs[maxn << 5], st[maxn << 5], top = 0;
 11
 12int build(int l, int r){
 13    int now = top++, mid = (l + r) >> 1;
 14    if(l == r) return now;
 15    ls[now] = build(l, mid);
 16    rs[now] = build(mid + 1, r);
 17    return now;
 18}
 19
 20//旧版本的节点标号为p，拥有区间[l, r]；现要在k位置加入x，返回新节点的标号
 21int update(int p, int l, int r, int k, int x){
 22    int now = top++;
 23    ls[now] = ls[p]; rs[now] = rs[p]; st[now] = st[p] + x;
 24    if(l == r) return now;
 25    
 26    int mid = (l + r) >> 1;
 27    if(k <= mid) ls[now] = update(ls[p], l, mid, k, x);
 28    else rs[now] = update(rs[p], mid + 1, r, k, x);
 29    return now;
 30}
 31
 32int use[maxn];
 33int sum(int x){
 34    int res = 0;
 35    while(x){
 36        res += st[ls[use[x]]];
 37        x -= lowbit(x);
 38    }
 39    return res;
 40}
 41
 42//当前在线段树的[l, r]位置上，左、右根节点分别为r1、r2，查询下标在(L, R]第k小的数字
 43int query(int l, int r, int r1, int r2, int L, int R, int k){
 44    if(l == r) return l;
 45    
 46    int mid = (l + r) >> 1;
 47    int res = sum(R) - sum(L) + st[ls[r2]] - st[ls[r1]];
 48    if(k <= res){
 49        for(int i = L; i; i -= lowbit(i)) use[i] = ls[use[i]];
 50        for(int i = R; i; i -= lowbit(i)) use[i] = ls[use[i]];
 51        return query(l, mid, ls[r1], ls[r2], L, R, k);
 52    }
 53    else{
 54        for(int i = L; i; i -= lowbit(i)) use[i] = rs[use[i]];
 55        for(int i = R; i; i -= lowbit(i)) use[i] = rs[use[i]];
 56        return query(mid + 1, r, rs[r1], rs[r2], L, R, k - res);
 57    }
 58}
 59
 60void update(int i, int k, int x){
 61    while(i <= N){
 62        s[i] = update(s[i], 1, N, k, x);
 63        i += lowbit(i);
 64    }
 65}
 66
 67
 68int main(){
 69//    Fastin;
 70    TTT{
 71        top = 0;
 72        scanf("%d %d", &n, &m);
 73        for(int i = 1; i <= n; i++){
 74            scanf("%d", a + i);
 75            b[i] = a[i];
 76        }
 77        N = n + 1;
 78        for(int i = 0; i < m; i++){
 79            char op[2]; scanf("%s", op);
 80            int x, y, z;
 81            if(op[0] == 'Q'){
 82                scanf("%d %d %d", &x, &y, &z);
 83                node[i] = {0, x, y, z};
 84            }
 85            else{
 86                scanf("%d %d", &x, &y);
 87                node[i] = {1, x, y};
 88                b[N++] = y;
 89            }
 90        }
 91        sort(b + 1, b + N);
 92        N = (int)(unique(b + 1, b + N) - (b + 1));
 93        
 94        
 95        rt[0] = build(1, N);
 96        for(int i = 1; i <= n; i++){
 97            rt[i] = update(rt[i - 1], 1, N, hsh(a[i]), 1);
 98            s[i] = 0;
 99        }
100        
101        for(int i = 0; i < m; i++){
102            //修改node[i].x位置的值为node[i].y;
103            if(node[i].type){
104                update(node[i].x, hsh(a[node[i].x]), -1);
105                update(node[i].x, hsh(node[i].y), 1);
106                a[node[i].x] = node[i].y;
107            }
108            //查询[node[i].x, node[i].y]中第k小的值
109            else{
110                int l = node[i].x - 1, r = node[i].y;
111                for(int i = l; i; i -= lowbit(i)) use[i] = s[i];
112                for(int i = r; i; i -= lowbit(i)) use[i] = s[i];
113                printf("%d\n", b[query(1, N, rt[l], rt[r], l, r, node[i].z)]);
114            }
115        }
116    }
117    return 0;
118}

ZOJ 2112

在rt[0]构建一个空线段树，构建两串权值线段树，L96-99构建原始版本的静态的、前缀的权值线段树；另一串构建$Δ$线段树，利用bit进行维护这一串线段树。更新时对log个线段树进行单点更新，总花费$O(log^2n)$；查询时一层一层进行查询：查询bit上log个线段树节点所有的左儿子，如果这一层差值的和与静态值之和小于等于k，就将bit上log个子树的节点标号向左儿子移动，递归地类似于普通第k大查询进行处理即可。

实际使用时注意仔细研究一下数据范围！

5 树

树链剖分

求lca

 1const int maxn = 5e5 + 10;
 2
 3int n, q, rot;
 4struct star{int from, to, next;};
 5int head[manx];
 6star edge[maxn << 1]; int top = 0;
 7void add(itn u, int v){
 8    edge[top].from = u;
 9    edge[top].to = v;
10    edge[top].next = head[u];
11    head[u] = top++;
12}
13
14//默认标号从1开始，给重儿子打上标记。
15int son[maxn], par[maxn], sze[maxn], dep[maxn];
16void tag(int now){
17    sze[now] = 1;
18    for(int i = head[now]; ~i; i = edge[i].next){
19        int to = edge[i].to; if(to == par[now]) continue;
20
21        par[to] = now; dep[to] = dep[now] + 1;
22        tag(to); 
23        sze[now] += sze[to];
24        if(sze[to] > sze[son[now]]) son[now] = to;
25    }
26}
27
28//将该重链的起点作为dsu中一个联通块的根节点
29int tp[maxn];
30void build(int now, int t){
31    //存在儿子，即非叶子
32    tp[now] = t;
33    if(son[now]) build(son[now], t);
34    for(int i = head[now]; ~i; i = edge[i].next){
35        int to = edge[i].to; if(to == par[now] || to == son[now]) continue;
36        build(to, to);
37    }
38}
39
40
41int lca(int u, int v){
42    while(tp[u] != tp[v]){
43        if(dep[tp[u]] > dep[tp[v]]) u = par[tp[u]];
44        else v = par[tp[v]];
45    }
46    return dep[u] < dep[v]? u: v;
47}
48
49int main(){
50    // Fastin;
51
52    clr(head, -1);
53    scanf("%d %d %d", &n, &q, &rot);
54    for(int i = 0; i < n - 1; i++){
55        int u, v; scanf("%d %d", &u, &v);
56        add(u, v); add(v, u);
57    }
58    tag(rot); build(rot, rot);
59    
60    for(int i = 0; i < q; i++){
61        int u, v; scanf("%d %d", &u, &v);
62        printf("%d\n", lca(u, v));
63    }
64}

速度很快，应该是吊打st和倍增。

支持路径修改/查询、子树修改查询

  1const int maxn = 1e5 + 10;
  2
  3int n, q, rot, M;
  4int w[maxn];
  5
  6struct star{int from, to, next;};
  7int head[maxn];
  8star edge[maxn << 1]; int top = 0;
  9void add(itn u, int v){
 10    edge[top].from = u;
 11    edge[top].to = v;
 12    edge[top].next = head[u];
 13    head[u] = top++;
 14}
 15
 16int son[maxn], par[maxn], sze[maxn], dep[maxn];
 17//默认标号从1开始，给重儿子打上标记。
 18void getson(int now){
 19    sze[now] = 1;
 20    for(int i = head[now]; ~i; i = edge[i].next){
 21        int to = edge[i].to; if(to == par[now]) continue;
 22
 23        par[to] = now; dep[to] = dep[now] + 1;
 24        getson(to); 
 25        sze[now] += sze[to];
 26        if(sze[to] > sze[son[now]]) son[now] = to;
 27    }
 28}
 29
 30int tp[maxn];
 31//将该重链的起点作为dsu中一个联通块的根节点
 32void getlink(int now, int t){
 33    //存在儿子，即非叶子
 34    tp[now] = t;
 35    if(son[now]) getlink(son[now], t);
 36    for(int i = head[now]; ~i; i = edge[i].next){
 37        int to = edge[i].to; if(to == par[now] || to == son[now]) continue;
 38        getlink(to, to);
 39    }
 40}
 41
 42//dfn为dfn序，pos为某个节点在dfn中的位置;
 43int r[maxn], pos[maxn], cnt = 0;
 44void dfs(int now){
 45    pos[now] = cnt; cnt++;
 46    if(son[now]) dfs(son[now]);
 47    for(int i = head[now]; ~i; i = edge[i].next){
 48        int to = edge[i].to; if(to == par[now] || to == son[now]) continue;
 49        dfs(to);
 50    }
 51    r[now] = cnt - 1;
 52}
 53
 54#define ls (p << 1)
 55#define rs ((p << 1) | 1)
 56#define mid ((l + r) >> 1)
 57//在dfn上的修改&查询,利用pos映射
 58ll st[maxn << 2], tag[maxn << 2];
 59void up(int p){st[p] = st[ls] + st[rs]; st[p] %= M;}
 60void down(int p, int l, int r){
 61    if(tag[p]){
 62        tag[p] %= M;
 63        tag[ls] += tag[p]; tag[rs] += tag[p];
 64        tag[ls] %= M; tag[rs] %= M;
 65        st[ls] += (mid - l + 1) * tag[p] % M; st[ls] %= M;
 66        st[rs] += (r - mid) * tag[p]; st[rs] %= M;
 67        tag[p] = 0;
 68    }
 69}
 70void update(int p, int l, int r, int L, int R, int x){
 71    assert(L <= R);
 72
 73    if(L <= l && r <= R){
 74        st[p] += (r - l + 1) * x; st[p] %= M;
 75        tag[p] += x; tag[p] %= M;
 76        return ;
 77    }
 78    down(p, l, r);
 79    if(L <= mid) update(ls, l, mid, L, R, x);
 80    if(R > mid) update(rs, mid + 1, r, L, R, x);
 81    up(p);
 82}
 83
 84ll query(int p, int l, int r, int L, int R){
 85    if(L <= l && r <= R) return st[p];
 86    down(p, l, r);
 87    ll ans = 0;
 88    if(L <= mid) ans += query(ls, l, mid, L, R); ans %= M;
 89    if(R > mid) ans += query(rs, mid + 1, r, L, R);
 90    return ans % M;
 91}
 92
 93void updatepath(int u, int v, int x){
 94    while(tp[u] != tp[v]){
 95        if(dep[tp[u]] > dep[tp[v]]){
 96            //u所在的重链更深
 97            update(1, 0, cnt - 1, pos[tp[u]], pos[u], x);
 98            u = par[tp[u]];
 99        }
100        else{
101            update(1, 0, cnt - 1, pos[tp[v]], pos[v], x);
102            v = par[tp[v]];
103        }
104    }
105    if(dep[u] > dep[v]) swap(u, v);
106    udpate(1, 0, cnt - 1, pos[u], pos[v], x);
107}
108
109ll pathquery(int u, int v){
110    ll ans = 0;
111    while(tp[u] != tp[v]){
112        if(dep[tp[u]] > dep[tp[v]]){
113            ans += query(1, 0, cnt - 1, pos[tp[u]], pos[u]);
114            ans %= M;
115            u = par[tp[u]];
116        }
117        else{
118            ans += query(1, 0, cnt - 1, pos[tp[v]], pos[v]);
119            ans %= M;
120            v = par[tp[v]];
121        }
122    }
123    if(dep[u] > dep[v]) swap(u, v);
124    ans += query(1, 0, cnt - 1, pos[u], pos[v]);
125    ans %= M;
126    return ans;
127}
128
129int main(){
130    // Fastin;
131    clr(head, -1);
132    scanf("%d %d %d %d", &n, &q, &rot, &M);
133    for(int i = 1; i <= n; i++) scanf("%d", w + i);
134    for(int i = 0; i < n - 1; i++){
135        int u, v; scnaf("%d %d", &u, &v);
136        add(u, v); add(v, u);
137    }
138
139    getson(rot); getlink(rot, rot); dfs(rot); 
140    for(int i = 1; i <= n; i++) update(1, 0, cnt - 1, pos[i], pos[i], w[i]);
141
142    for(int i = 0; i < q; i++){
143        int op; scnaf("%d", &op);
144        int x, y, z; 
145        if(op == 1){
146            scanf("%d %d %d", &x, &y, &z);
147            updatepath(x, y, z);
148        }
149        else if(op == 2){
150            scanf("%d %d", &x, &y); printf("%lld\n", pathquery(x, y) % M);
151        }
152        else if(op == 3){
153            scanf("%d %d", &x, &y); udpate(1, 0, cnt - 1, pos[x], r[x], y);
154        }
155        else{
156            scanf("%d", &x); printf("%lld\n", query(1, 0, cnt - 1, pos[x], r[x]));
157        }
158    }
159}

为了充分利用重链和dfn序，在dfs时优先遍历重链，这样即可保证重链上的节点在dfn序列上连续。

修改路径时只需要参考前述求lca的跳点规则，一段段地在线段树上进行区间修改可。

而修改路径更为简单，只需要记录一下子树在dfn序列上的辖域即可。

点分治

计数树上两点之间路径长度为k的对数（开桶加速多组查询）

 1const int maxn = 1e4 + 10;
 2int n, m;
 3struct star{int to, next, w;};
 4int head[maxn], top = 0;
 5star edge[maxn << 1];
 6void add(int u, int v, int w){
 7    edge[top].to = v;
 8    edge[top].next = head[u];
 9    edge[top].w = w;
10    head[u] = top++;
11}
12
13//调用getroot前应该初始化S！！！
14int root = 0, S;
15int vis[maxn], sze[maxn], mx[maxn];;
16void getroot(int u, int par){
17    sze[u] = 1; mx[u] = 0;
18    for(int i = haed[u]; ~i; i = edge[i].next){
19        int to = edge[i].to; if(vis[to] || to == par) continue;
20        getroot(to, u);
21        sze[u] += sze[to];
22        mx[u] = max(mx[u], sze[to]);
23    }
24    mx[u] = max(mx[u], S - sze[u]);
25    if(mx[u] < mx[root]) root = u;
26}
27
28vector<int> dis;
29void dfs(int u, int par, int d){
30    if(d > 10000000) return ;
31    for(int i = head[u]; ~i; i = edge[i].next){
32        int to = edge[i].to; if(vis[to] || to == par) continue;
33        dis.push_back(d + edge[i].w);
34        dfs(to, u, d + edge[i].w);
35    }
36}
37
38int tong[10000010];
39int k[maxn], ans[maxn];
40//获取经过u的答案，路径长度有基础偏移值d
41void fun(int u, int d, int x){
42    dis.clear(); dis.push_back(d); dfs(u, 0, d);
43    for(int i = 0; i < (int)dis.size(); i++) if(dis[i] <= 10000000) tong[dis[i]]++;
44
45    for(int i = 0; i < (int)dis.size(); i++){
46        for(int j = 0; j < m; j++){
47            if(dis[i] + dis[i] < k[j]) ans[j] += (tong[k[j] - dis[i]]) * x;
48            if(dis[i] + dis[i] == k[j]) ans[j] += (tong[dis[i]] - 1) * x;
49        }
50    }
51    for(int i = 0; i < (int)dis.size(); i++) if(dis[i] <= 10000000) tong[dis[i]]--;
52}
53
54//u是重心，考察以经过u的路径长度
55void sove(int u){
56    //封锁u节点，分治地寻找子树.
57    vis[u] = 1; fun(u, 0, 1);
58    for(int i = head[u]; ~i; i = edge[i].next){
59        int to = edge[i].to; if(vis[to]) continue;
60        //删去那些根本不经过u的点对
61        fun(to, edge[i].w, -1);
62
63        S = sze[to]; root = 0;
64        getroot(to, u);
65        sove(root);
66    }
67}
68
69int main(){
70//    Fastin;
71    clr(head, -1);
72
73    scanf("%d %d", &n, &m);
74    for(int i = 0; i < n - 1; i++){
75        int u, v, w; scanf("%d %d %d", &u, &v, &w);
76        add(u, v, w); add(v, u, w);
77    }
78    
79    for(int i = 0; i < m; i++) scanf("%d", k + i);
80
81    mx[0] = n; root = 0;
82    S = n; clr(vis, 0);
83    getroot(1, 0);
84    sove(root);
85    for(int i = 0; i < m; i++) puts(ans[i]? "AYE": "NAY");
86    return 0;
87}

时间复杂度$O(nlogn)$

实际使用桶加速时需要根据题意修改桶的大小。
main函数中对于mx[0]的初始化必不可少
每次调用getroot前都应对S(当前子树总大小)进行初始化。
如果权值过大不能开桶，可以通过二分查找等方式多一个$log$地进行查询计数
找重心时S的更新应该如下才对？（不懂.gif

1if(sze[to] < sze[u]) S = sze[to];
2else S = sze[to] - sze[u];

点分树

多组查询与某点距离小于等于k的所有点权和并支持单点修改

  1#define mid ((l + r) >> 1)
  2
  3const int manx = 1e5 + 10;
  4//根据dfn数组的长度决定N(即N = log2(cnt), cnt = maxn << 1)
  5const int N = 20;
  6const double eps = 1e-6;
  7
  8int n, q;
  9int w[manx];
 10//动态开点的单点修改、区间求和线段树
 11//维护两个st，一个是u子树对u的贡献，另一个是u子树对par[u]的贡献（如果有的话）
 12const int M = maxn * N * 4;
 13struct SEG{
 14    int root[maxn];
 15    int st[M], ls[M], rs[M], top = 0;
 16    int build(int l, int r){
 17        int now = top++;
 18        if(l == r) return now;
 19        ls[now] = build(l, mid);
 20        rs[now] = build(mid + 1, r);
 21        return now;
 22    }
 23    void up(int p){st[p] = st[ls[p]] + st[rs[p]];}
 24    void add(int p, int l, int r, int k, int x){
 25        assert(k >= l && k <= r);
 26        if(l == r && l == k){
 27            st[p] += x;
 28            return ;
 29        }
 30        if(k <= mid) add(ls[p], l, mid, k, x);
 31        else add(rs[p], mid + 1, r, k, x);
 32        up(p);
 33    }
 34    
 35    int query(int p, int l, int r, int L, int R){
 36        if(R < L) return 0;
 37        if(L <= l && r <= R) return st[p];
 38        int ans = 0;
 39        if(L <= mid) ans += query(ls[p], l, mid, L, R);
 40        if(R > mid) ans += query(rs[p], mid + 1, r, L, R);
 41        return ans;
 42    }
 43}seg[2];
 44
 45
 46vector<pair<int, int>> E;
 47struct TREE{
 48    int head[maxn], par[manx], top = 0;
 49    struct star{int to, next;};
 50    star edge[maxn << 1];
 51
 52    TREE(){clr(head, -1); top = 0;}
 53
 54    void add(int u, int v){
 55        edge[top].to = v;
 56        edge[top].next = head[u];
 57        head[u] = top++;
 58    }
 59    void add(vector<pair<int, int>> &E){
 60        for(auto e: E){
 61            add(e.first, e.second);
 62            par[e.second] = e.first;
 63        }
 64    }
 65
 66    int mx[maxn], sze[maxn], vis[maxn], root = 0, S;
 67    void getroot(int now, int par){
 68        sze[now] = 1; mx[now] = 0;
 69        for(int i = head[now]; ~i; i = edge[i].next){
 70            int to = edge[i].to; if(to == par || vis[to]) continue;
 71            getroot(to, now);
 72            sze[now] += sze[to];
 73            mx[now] = max(mx[now], sze[to]);
 74        }
 75        mx[now] = max(mx[now], S - sze[now]);
 76        if(mx[root] > mx[now]) root = now;
 77    }
 78    //当前分治中心为now，封锁住通往par的路径，函数返回重心
 79    int divide(int now, int par){
 80        root = 0; getroot(now, par);
 81        int rt = root; vis[rt] = 1;
 82        for(int i = head[rt]; ~i; i = edge[i].next){
 83            int to = edge[i].to; if(to == par || vis[to]) continue;
 84            S = sze[to];
 85            E.push_back({rt, divide(to, rt)});
 86        }
 87        return rt;
 88    }
 89    //将树重构为点分树，点分数的边存放在E中，供tree[1].add调用；返回重构树的根
 90    int rebuild(){
 91        S = mx[0] = n;
 92        return divide(1, 0);
 93    }
 94    
 95    //初始化dfn、pos数组，得到每个节点的深度dep
 96    int dfn[maxn << 1], pos[manx], cnt = 0;
 97    int dep[maxn];
 98    void dfs(int now, int par){
 99        dfn[cnt] = now; pos[now] = cnt; cnt++;
100        for(int i = head[now]; ~i; i = edge[i].next){
101            int to = edge[i].to; if(to == par) continue;
102            dep[to] = dep[now] + 1;
103            dfs(to, now);
104            dfn[cnt++] = now;
105        }
106    }
107    
108    int st[maxn << 1][N];
109    //通过深度数组获取st表, st维护区间中深度最小的节点标号
110    void getst(){
111        dfs(1, 0);
112        for(int i = 0; i < cnt; i++) st[i][0] = dfn[i];
113        for(int j = 1; j < N; j++){
114            for(int i = 0; i < cnt; i++){
115                int nxt = i + (1 << (j - 1));
116                if(nxt >= cnt) st[i][j] = st[i][j - 1];
117                else if(dep[st[i][j - 1]] < dep[st[nxt][j - 1]]) st[i][j] = st[i][j - 1];
118                else st[i][j] = st[nxt][j - 1];
119            }
120        }
121    }
122    //O1获取两点之间的距离
123    int getdis(int x, int y){
124        if(x == y) return 0;
125        int l = min(pos[x], pos[y]), r = max(pos[x], pos[y]);
126        int k = (int)(log2(r - l) + eps);
127        int lca = st[l][k];
128        if(dep[lca] > dep[st[r - (1 << k) + 1][k]]) lca = st[r - (1 << k) + 1][k];
129        return dep[x] + dep[y] - 2 * dep[lca];
130    }
131    //获取子树大小并初始化线段树
132    void ini(int now, int par){
133        sze[now] = 1;
134        for(int i = head[now]; ~i; i = edge[i].next){
135            int to = edge[i].to; if(to == par) continue;
136            ini(to, now);
137            sze[now] += sze[to];
138        }
139        seg[0].root[now] = seg[0].build(0, sze[now]);
140        seg[1].root[now] = seg[1].build(0, sze[now] + 1);
141    }
142}tree[2];
143
144
145//第k个城市上发生x的增量，当前处理到now节点，保证now节点一定是k的祖先
146void add(int now, int k, int x){
147    int dis = tree[0].getdis(now, k);
148    seg[0].add(seg[0].root[now], 0, tree[1].sze[now], dis, x);
149    if(tree[1].par[now]){
150        dis = tree[0].getdis(tree[1].par[now], k);
151        seg[1].add(seg[1].root[now], 0, tree[1].sze[now] + 1, dis, x);
152        add(tree[1].par[now], k, x);
153    }
154}
155
156//查询距离k城市距离小于等于x的价值和，当前处理到now
157int query(int now, int k, int x){
158    int ans = 0;
159    int d = tree[0].getdis(now, k);
160    ans += seg[0].query(seg[0].root[now], 0, tree[1].sze[now], 0, x - d);
161    if(tree[1].par[now]){
162        int D = tree[0].getdis(tree[1].par[now], k);
163        ans -= seg[1].query(seg[1].root[now], 0, tree[1].sze[now] + 1, 0, x - D);
164        ans += query(tree[1].par[now], k, x);
165    }
166    return ans;
167}
168
169int main(){
170//     Fastin;
171    scanf("%d %d", &n, &q);
172    for(int i = 1; i <= n; i++) scanf("%d", w + i);
173    for(int i = 0; i < n - 1; i++){
174        int u, v; scnaf("%d %d", &u, &v);
175        tree[0].add(u, v); tree[0].add(v, u);
176    }
177    
178    tree[0].getst();
179    
180    int root = tree[0].rebuild();
181    tree[1].add(E);
182
183    tree[1].ini(root, 0);
184    
185    for(int i = 1; i <= n; i++) add(i, i, w[i]);
186    
187    int ans = 0;
188    whlie(q--){
189        int op, x, y; scanf("%d %d %d", &op, &x, &y);
190	      //强制在线
191        x ^= ans; y ^= ans;
192        if(op){
193            add(x, x, y - w[x]);
194            w[x] = y;
195        }
196        else printf("%d\n", ans = query(x, x, y));
197    }
198
199    return 0;
200}

主要数据结构
- tree[0]: 原树
  - 利用mx[maxn]、sze[maxn]、vis[maxn]、root、S对树进行重构，将重构结果的边暂时保存在vector<pair<int, int» E中，等待之后存放到tree[1]中
  - 利用dfn[maxn « 1]、pos[maxn]、cnt、dep[maxn]、st[maxn « 1][N]建立st表，提供接口getdis进行O1查询距离。ST表的大小应当与dfn相同！同时注意建立ST表时边界越界的问题！
- tree[1]: 原树重构后得到的点分树
  - 利用ini()函数获取点分树上所有子树的大小，将该大小作为线段树的边界，同时完成动态开点的线段树的初始化。
- seg[0]: 动态开点的权值线段树(单点修改、区间查询)
  - 通过seg[0].root数组作为tree[1]中每个节点的入口
  - 对于某个节点u而言，权值线段树的值域区间为[0, tree[1].sze[u]]，存储的内容为tree[1]中u节点所有孩子对u的贡献
  - 需要的空间为n * logn * 4
- seg[1]: 动态开点的权值线段树(单点修改、区间查询)
  - 通过seg[1].root数组作为tree[1]中每个节点的入口
  - 对于某个节点u而言，权值线段树的值域区间为[0, tree[1].sze[u] + 1] (+1是必要的)，存储的内容为tree[1]中u节点所有孩子对par[u]（如果存在的话）的贡献
  - 需要的空间为n * logn * 4
使用指南
- 读入原树到tree[0]后，调用tree[0].getst()初始化st表
- 调用tree[0].rebuild()重构原树，新树的边存放在E中，再开变量root存放函数的返回值(即新树的根)
- 调用tree[1].add(E)将E中的有向边加入到tree[1]中
- 调用tree[1].ini(root)从新树的根开始，完成新树上套线段树的建立
- 调用add函数将原树的所有点权加入到线段树中，完成线段树的初始化
- 读入q次查询，根据查询的类型调用add/query进行操作即可。

pruefer序列

 1const int maxn = 5e6 + 10;
 2int n;
 3int par[maxn], prufer[maxn], du[maxn];
 4
 5void encode(){
 6    int ptr = -1;
 7    for(int i = 1; i <= n; i++) if(ptr == -1 && du[i] == 1) ptr = i;
 8    
 9    int leaf = ptr;
10    for(int i = 0; i < n - 2; i++){
11        int next = prufer[i] = par[leaf];
12        if(--du[next] == 1 && next < ptr) leaf = next;
13        else{
14            ptr++;
15            while(du[ptr] != 1) ptr++;
16            leaf = ptr;
17        }
18    }
19}
20
21void rebuild(){
22    int ptr = 0;
23    while(du[ptr] != 1) ptr++;
24    
25    int leaf = ptr;
26    for(int i = 0; i < n - 2; i++){
27        int next = par[leaf] = prufer[i];
28        if(--du[next] == 1 && next < ptr) leaf = next;
29        else{
30            ptr++;
31            while(du[ptr] != 1) ptr++;
32            leaf = ptr;
33        }
34    }
35    par[leaf] = n;
36}
37
38void hsh(int a[maxn], int n){
39    ll ans = 0;
40    for(int i = 0; i < n; i++) ans ^= (i + 1) * 1ll * a[i];
41    printf("%lld\n", ans);
42}
43
44int main(){
45//    Fastin;
46    
47    int op;
48    scanf("%d %d", &n, &op);
49    if(op == 1){
50        for(int i = 1; i <= n - 1; i++){
51            scanf("%d", par + i);
52            du[par[i]]++; du[i]++;
53        }
54        encode();
55        hsh(prufer, n - 2);
56    }
57    else{
58        for(int i = 1; i <= n; i++) du[i] = 1;
59        for(int i = 0; i < n - 2; i++){
60            scanf("%d", prufer + i);
61            du[prufer[i]]++;
62        }
63        rebuild();
64        hsh(par + 1, n - 1);
65    }
66    return 0;
67}

使用指南

读入点数n和操作数op
op = 1 读入节点$[1, …,n-1]$的父亲，调用encode后将prufer序列保存在$prufer[0, n - 2)$中
op = 2 读入长为n-2的prufer序列，调用rebuild后将节点$[1, …, n -1]$的父亲存储在$par[1, .. n -1]$中

TIPS

因为prufer序列构造的特性，节点n一定是留到最后的那个节点，所以程序中读入/输出的par序列均是以n节点为根时的父子关系。

计数相关定理

凯莱公式

完全图$K_n$有$n^{n-2}$棵生成树。

证明显然。

图联通方案数

一个n节点的带标号无向图有k个联通块。添加k-1条边使得图联通的方案数为$n^{k-2} * \prod s_i$.

证明：

尝试对k个联通块构造prufer序列。

由于每个联通块的度未知，因而设$d_i$为联通块i的度。$d_i$满足$\sum d_i = 2(k-1)$

则对于给定d序列后构造prufer序列的方案数为$(^{\space \space \space \space \space \space \space \space k-2}_{(d_1-1)!…(d_k-1)!})$

而对于某个联通块$s_i$而言，其连接方式为$s_i^{d_i}$种，因而对于给定d序列后图联通的方案数是$(^{\space \space \space \space \space \space \space \space k-2}_{(d_1-1)!…(d_k-1)!})*s_i^{d_i}$

接下来枚举d序列，即$\sum_{d_i≥1,\sum d_i=2k-2}(^{\space \space \space \space \space \space \space \space k-2}_{(d_1-1)!…(d_k-1)!})*\prod _{1 \leq i \leq k}s_i^{d_i}$

利用多元二项式定理: $(x_1+…+x_m)^p=\sum_{c_i≥0, \sum c_i=p}(^{\space \space \space \space p}_{c_1, …, c_m}) * \prod x_i^{c_i}$, 并换元$e_i=d_i-1$。$\sum e_i=k-2$

则原式成为$\sum_{e_i≥0, \sum e_i = k-2} (^{\space \space k-2}_{e_1, …, e_k})*\prod s_i^{e_i+1}$

化简得$(s_1+…+s_k)^{k-2} * \prod s_i$

即$n^{k-2} * \prod s_i$

6 数学

异或线性基

 1const int maxn = 200 + 10;
 2ll a[maxn];
 3
 4const int L = 63;
 5ll d[L];
 6bool add(ll x){
 7    for(int i = L - 1; i >= 0; i--) if(x & 1ll << i){
 8        if(d[i] == -1){d[i] = x; return true;}
 9        x ^= d[i];
10    }
11    return false;
12}
13
14int main(){
15//    Fast;
16    int t; scanf("%d", &t); while(t--){
17        memset(d, -1, sizeof d);
18        
19        int n; scanf("%d", &n);
20        for(int i = 0; i < n; i++) scanf("%lld", a + i);
21        char s[maxn]; scanf("%s", s);
22        int flag = 0;
23        for(int i = n - 1; i >= 0; i--){
24            if(add(a[i]) && s[i] == '1'){
25                flag = 1;
26                break;
27            }
28        }
29        printf("%d\n", flag);
30    }
31    return 0;
32}

多项式

FTT

 1struct COM{
 2    double x, y;
 3    COM operator *(const COM &b){
 4        return {x * b.x - y * b.y, x * b.y + y * b.x};
 5    }
 6    COM operator -(const COM &b){
 7        return {x - b.x, y - b.y};
 8    }
 9    COM operator +(const COM &b){
10        return {x + b.x, y + b.y};
11    }
12};
13
14const int maxn = 1e6 + 10;
15
16int n, m, sum, N, wei;
17COM a[maxn << 2], b[maxn << 2];
18
19int inv[maxn << 2];
20
21//将0到N-1的多项式表示转化为点值表示
22void fft(COM *a, int op){
23    for(int i = 0; i < N; i++) if(i < inv[i]) swap(a[inv[i]], a[i]);
24    
25    //逆fft将范德蒙德行列式的每一项取共轭再除以n
26    for(int i = wei - 1; i >= 0; i--){
27        int d = 1 << (wei - i);
28        COM wn = {cos(2 * pi / d), op * sin(2 * pi / d)};
29        //j遍历第i层的开头
30        for(int j = 0; j < N; j += d){
31            //对j开头的一小段进行更新
32            COM w = {1, 0};
33            for(int k = 0; k < d / 2; k++){
34                COM x, y;
35                x = a[j + k]; y = a[j + k + d / 2] * w;
36                a[j + k] = x + y; a[j + k + d / 2] = x - y;
37                w = w * wn;
38            }
39            
40        }
41    }
42}
43
44//#define LOCAL
45int main(){
46#ifdef LOCAL
47    freopen("in.txt", "r", stdin);
48#endif
49    scanf("%d %d", &n, &m);
50    for(int i = 0; i <= n; i++) scanf("%lf", &a[i].x);
51    for(int i = 0; i <= m; i++) scanf("%lf", &b[i].x);
52    
53    sum = n + m + 1; N = 1; wei = 0;
54    while(N < sum){N *= 2; wei++;}
55    for(int j = 0; j < 1 << wei; j++)
56        inv[j] = inv[j >> 1] >> 1 | (j & 1) << (wei - 1);
57    fft(a, 1); fft(b, 1);
58    for(int i = 0; i < N; i++) a[i] = a[i] * b[i];
59    fft(a, -1);
60    for(int i = 0; i < n + m + 1; i++) printf("%d ", (int)(a[i].x / N + 0.5));
61    return 0;
62}

输入n、m，接n+1和m+1个整数，分别表示n次多项式和m次多项式从低到高的系数。

输出n+m+1个系数。

NTT

 1
 2const int maxn = 1e6 + 10;
 3const int M = 998244353;
 4const int p = 3, invp = 332748118;
 5
 6int n, m, sum, N, wei;
 7ll a[maxn << 2], b[maxn << 2];
 8
 9int inv[maxn << 2];
10
11int quick_pow(int a, int p){
12    ll ans = 1, res = a;
13    while(p){
14        if(p & 1) ans *= res; ans %= M;
15        res *= res; res %= M;
16        p >>= 1;
17    }
18    return ans % M;
19}
20
21//
22//逆fft将范德蒙德行列式的每一项取共轭再除以n
23void fft(ll *a, int op){
24    for(int i = 0; i < N; i++) if(i < inv[i]) swap(a[inv[i]], a[i]);
25
26    for(int i = wei - 1; i >= 0; i--){
27        int d = 1 << (wei - i);
28        ll gn = quick_pow(op == 1? p: invp, (M - 1) / d);
29        //j遍历第i层的开头
30        for(int j = 0; j < N; j += d){
31            //对j开头的小段进行更新
32            ll g = 1;
33            for(int k = 0; k < d / 2; k++){
34                ll x, y;
35                x = a[j + k] % M;
36                y = a[j + k + d / 2] * g; y %= M;
37                a[j + k] = (x + y) % M; a[j + k + d / 2] = (x - y + M) % M;
38                g = g * gn; g %= M;
39            }
40        }
41    }
42}
43
44//#define LOCAL
45int main(){
46#ifdef LOCAL
47    freopen("in.txt", "r", stdin);
48#endif
49    scanf("%d %d", &n,  &m);
50    for(int i = 0; i <= n; i++) scanf("%lld", a + i);
51    for(int i = 0; i <= m; i++) scanf("%lld", b + i);
52
53    sum = n + m + 1; N = 1; wei = 0;
54    while(N < sum){N *= 2; wei++;}
55    for(int j = 0; j < 1 << wei; j++)
56        inv[j] = inv[j >> 1] >> 1 | (j & 1) << (wei - 1);
57    
58    fft(a, 1); fft(b, 1);
59    for(int i = 0; i < N; i++) a[i] = (a[i] * b[i]) % M;
60    fft(a, -1);
61    int invn = quick_pow(N, M - 2);
62    for(int i = 0; i < n + m + 1; i++) printf("%lld ", (a[i] * invn + M) % M);
63    printf("\n");
64    return 0;
65}

输入n、m，接n+1和m+1个整数，分别表示n次多项式和m次多项式从低到高的系数。

输出n+m+1个系数。

高斯整数

 1struct GaussianInteger{
 2    ll x, y;
 3    ll norm(){return x * x + y * y;}
 4    GaussianInteger operator + (const GaussianInteger &b){
 5        return {x + b.x, y + b.y};
 6    }
 7    GaussianInteger operator - (const GaussianInteger &b){
 8        return {x - b.x, y - b.y};
 9    }
10    GaussianInteger operator * (const GaussianInteger &b){
11        return {x * b.x - y * b.y, x * b.y + y * b.x};
12    }
13    //(专用! 因为此处b保证大于0)四舍五入除法
14    //高斯整数商的实部虚部在某个整数的**(-1/2, 1/2]**区间中。
15    ll D(ll a, ll b){
16        if(a >= 0) return (a % b) * 2 < b? a / b: a / b + 1;
17        a = -a; return -((a % b) * 2 <= b? a / b: a / b + 1);
18    }
19    GaussianInteger operator / (const GaussianInteger &b){
20        return {D(x * b.x + y * b.y, x * b.x + y * b.y), D(y * b.x - x * b.y, x * b.x + y * b.y)};
21    }
22    GaussianInteger operator % (const GaussianInteger &b){
23        GaussianInteger a = {x, y};
24        return a - a / b * b;
25    }
26};
27typedef GaussianInteger NODE;
28NODE gcd(NODE a, NODE b){return !b.norm()? a: gcd(b, a % b);}

线性代数

Gauss-Jordan消元法

 1/*
 2使用指南：
 3    读入"整形"增广矩阵a，修改行列信息equ、var。
 4    从零开始编号，则行为[0, equ - 1], 列为[0, var];
 5    返回值：
 6        返回0说明有整数解，结果存放在x数组中
 7        返回-2说明有浮点解，需要修改数据类型再运算
 8        返回-1时无解
 9        返回正数k时说明有k个自由变元，自由变元存放在flag中；
10Tips:
11    处理过程可能爆int
12*/
13
14const int maxn = 1e2;
15//有equ个等式，var个变量，那么增广矩阵有equ行，var + 1列；模版中从0开始标号。
16int equ, var;
17int a[maxn][maxn];
18//x是解集，flag标记是否自由
19int x[maxn], flag[maxn];
20
21int gauss(){
22    int i, j;
23    for(i = 0, j = 0; i < equ && j < var; i++, j++){
24        int l = i;
25        for(int k = i + 1; k < equ; k++) if(abs(a[k][j] > a[l][j])) l = k;
26        if(l != i) swap(a[l], a[i]);
27        //i行及以下的该列全为0，转而处理下一列。
28        if(a[i][j] == 0){
29            i--; continue;
30        }
31        for(int k = i + 1; k < equ; k++) if(a[k][j]){
32            int lcm = abs(a[k][j] * a[i][j]) / gcd(abs(a[k][j]), abs(a[i][j]));
33            int pa = lcm / a[k][j], pb = lcm / a[i][j];
34            for(int col = j; col <= var; col++) a[k][col] = a[k][col] * pa - a[i][col] * pb;
35        }
36    }
37    //循环完成后，i是有效行数，也就是秩（？）；
38
39
40    //(I)存在(0, 0, ... ,0, k!=0)的结构存在，即无解,返回-1
41    for(int k = i; k < equ; k++) if(a[k][var] != 0) return -1;
42    
43    //(II)存在自由变元，返回变元数量，并且在flag数组中标记出所有的自由变元。
44    if(j < var){
45        //i是秩，[0, i - 1]均为非全零的行
46        for(int k = i - 1; k >= 0; k--){
47            int cnt = 0, free_id = -1;
48            for(int col = 0; col < var; col++) if(a[k][col] && flag[col]){
49                cnt++;
50                free_id = col;
51            }
52            //一定存在至少一个自由变元，不然一定会被向下过程消去。
53            assert(free_id != -1);
54
55            //有两个及以上变元，那么无法确定这些变元
56            if(cnt >= 2) continue;
57
58            // 注释原因:求解变元会涉及到小数？故注释掉，实际操作时根据具体情况处理
59            // //只剩一个变元free_id，可以求解出来。
60            // int temp = a[k][var];
61            // for(int col = 0; col < var; col++) if(a[k][col] && col != free_id) temp -= a[k][col] * x[col];
62            // x[free_id] = tmep / a[k][free_id];
63
64            flag[free_id] = 0;
65        }
66        return var - i;
67    }
68    
69    //(III)求解方程，此时保证有唯一解:如果全部为正整数解，返回0，如果出现浮点数解，返回-2；
70    for(int i = var - 1; i >= 0; i--){
71        int tmep = a[i][var];
72        for(int j = i + 1; j < var; j++) if(a[i][j]) tmep -= a[i][j] * x[j];
73        if(temp % a[i][i]) return -2;
74        x[i] = temp / a[i][i];
75    }
76    return 0;
77}

修改算法中的+-为异或就可以变成异或加的高斯消元法。

逆矩阵高斯消元

 1/*
 2使用指南：
 3    读入矩阵大小n和初始矩阵在a[i][j]中, i ,j ∈[0, ... ,n - 1】
 4    返回在模M意义下的整数矩阵在a[i][j + n]中, i ,j ∈[0, ... ,n - 1】
 5*/
 6
 7const int maxn = 1e2;
 8const int M = 1e9 + 7;
 9
10int n; ll a[maxn][maxn << 1];
11
12void prt(){
13    for(int i = 0; i < n; i++){
14        for(int j = 0 ;j < 2 * n; j++) printf("%-10lld ",a[i][j]);
15            printf("\n");
16    }
17    puts("");
18}
19bool inverse(){
20    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) a[i][j + n] = 0;
21    for(int i = 0; i < n; i++) a[i][i + n] = 1;
22    prt();
23
24    for(int i = 0; i < n; i++){
25        int l = i;
26        for(int k = i + 1; k < n; k++) if(abs(a[k][i] > a[l][i])) l = k;
27        if(l != i) swap(a[l], a[i]);
28        prt();
29
30        if(!a[i][i]) return 0;
31        ll inv = qp(a[i][i], M - 2, M);
32        for(int k = 0; k < 2 * n; k++) a[i][k] = a[i][k] * inv % M;
33        prt();
34        for(int j = 0; j < n; j++) if(j != i){
35            ll t = a[j][i];
36            for(int k = 0; k < 2 * n; k++) a[j][k] = ((a[j][k] - t * a[i][k]) % M + M) % M;
37            prt();
38        }
39    }
40    return 1;
41}

没有经历过较强数据的测试，使用时需谨慎！⚠️！！！

求逆元使用的是quick_pow，当模数M不是素数时应该使用exgcd求素数。

行列式

 1int n; ll a[maxn][maxn];
 2ll det(){
 3    ll ans = 1, temp = 1;
 4    for(int i = 0; i < n; i++){
 5        int l = i;
 6        for(int j = i + 1; j < n; j++) if(abs(a[j][i]) > abs(a[l][i])) l = j;
 7        if(l != i){
 8            swap(a[i], a[l]);
 9            ans = -ans;
10        }
11        if(!a[i][i]) return 0;
12
13        for(int j = 0; j < n; j++) if(j != i && a[j][i]){
14            ll lcm = a[i][i] * a[j][i] / gcd(abs(a[i][i]), abs(a[j][i]));
15            ll ta = lcm / a[j][i], tb = lcm / a[i][i];
16            for(int k = 0; k < n; k++) a[j][k] = ta * a[j][k] - tb * a[i][k];
17            temp *= ta;
18        }
19    }
20    for(int i = 0; i < n; i++) ans *= a[i][i];
21    return ans / temp;
22}

没有经历过较强数据的测试，使用时需谨慎！⚠️！！！

自适应辛普森求定积分

 1double f(double x){
 2    //填入积分函数
 3    return 0;
 4}
 5
 6double simpson(double l, double r){
 7    return (r - l) * (f(l) + f(r) + 4 * f((l + r) / 2)) / 6;
 8}
 9
10double solve(double L, double R, double ans) {
11    double mid = (L + R) / 2, l = simpson(L, mid), r = simpson(mid, R);
12    if (fabs(l + r - ans) <= eps) return ans; 
13    return solve(L, mid, l) + solve(mid, R, r);
14}

gcd & exgcd(拓展欧几里德)

1template<typename T>
2T gcd(T x, T y){return !x? y: gcd(y % x, x);}
3template<typename T>
4void exgcd(T a, T b, T &x, T &y){
5    if(!b){x = 1; y = 0;return;}
6    exgcd(b, a % b, y, x); y -= a / b * x;
7}

线性筛

 1int euler(int *prime, int *vis, int n){
 2    int top = 0;
 3    for(int i = 0; i <= n; i++) vis[i] = 0;
 4    for(int i = 2; i <= n; i++){
 5        if(!vis[i]) prime[top++] = i;
 6        for(int j = 0; j < top && i * prime[j] <= n; j++){
 7            vis[i * prime[j]] = 1;
 8            if(i % prime[j] == 0) break;
 9        }
10    }
11    return top;
12}

7 数据结构

区间合并线段树

 1struct Tree{
 2    int l, r, ll, rr, all;
 3}tree[maxn << 2];
 4
 5//初始化区间线段树
 6void build(int p, int l, int r){
 7    tree[p].l = l; tree[p].r = r;
 8    tree[p].ll = tree[p].rr = tree[p].all = r - l + 1;
 9    if(r == l) return;
10    
11    build(ls, l, mid);
12    build(rs, mid + 1, r);
13}
14
15void up(int p){
16	//更新连续左区间
17    if(tree[ls].ll == tree[ls].r - tree[ls].l + 1) tree[p].ll = tree[ls].ll + tree[rs].ll;
18    else tree[p].ll = tree[ls].ll;
19    
20    //更新连续右区间
21    if(tree[rs].rr == tree[rs].r - tree[rs].l + 1) tree[p].rr = tree[ls].rr + tree[rs].rr;
22    else tree[p].rr = tree[rs].rr;
23    
24    //更新全区间
25    tree[p].all = max(tree[ls].all, max(tree[rs].all, tree[ls].rr + tree[rs].ll));
26}
27
28
29//将x所在的元素置为k(k = 0/1)；当前节点为p
30void update(int p, int x, int k){
31    if(tree[p].l == tree[p].r && tree[p].l == x){
32        tree[p].all = tree[p].ll = tree[p].rr = k;
33        return;
34    }
35    if(x <= (tree[p].l + tree[p].r) >> 1) update(ls, x, k);
36    else update(rs, x, k);
37    up(p);
38}
39
40ll que(int p, int x){
41    if(tree[p].l == tree[p].r) return tree[p].all;
42    
43    //x处于中心位置的区间则更新之
44    if(x >= tree[ls].r - tree[ls].rr + 1 && x <= tree[rs].l + tree[rs].ll - 1)
45        return tree[ls].rr + tree[rs].ll;
46    //x处于左边其他某个位置
47    else if(x < tree[ls].r - tree[ls].rr + 1) return que(ls, x);
48    //x处于右边其他某个位置
49    else return que(rs, x);
50}

线段树哈希

  1#define ls (p << 1)
  2#define rs ((p << 1) | 1)
  3#define mid ((l + r) >> 1)
  4
  5const int maxn = 5e5 + 10;
  6//数值对mod取模
  7const int mod = 65536;
  8//哈希的基底和模数
  9const int pp = 999983;
 10const int M = 1000237529;
 11
 12//注意mod和M！实际运用时不要写错了！
 13
 14//st为哈希和线段树; st1为极值线段树，用于维护对mod取模的相关信息。
 15int a[maxn];
 16ll tag[maxn << 2], st1[maxn << 2], st[maxn << 2];
 17//po[i] = pp ^ i; pre[i] = po[0] + po[1] + ... + po[i]，用于对区间快速更新哈希和
 18ll po[maxn], pre[maxn];
 19
 20void up(int p, int l, int r){
 21    st[p] = st[ls] + st[rs] * po[mid - l + 1] % M; st[p] %= M;
 22    st1[p] = max(st1[ls], st1[rs]);
 23}
 24
 25void build(int p, int l, int r, int k, int x){
 26    if(l == r && l == k){
 27        st[p] = st1[p] = x;
 28        return ;
 29    }
 30    if(k <= mid) build(ls, l, mid, k, x);
 31    else build(rs, mid + 1, r, k, x);
 32    up(p, l, r);
 33}
 34
 35void down(int p, int l, int r){
 36    if(tag[p]){
 37        tag[ls] += tag[p];
 38        tag[rs] += tag[p];
 39        
 40        st[ls] += pre[mid - l] * tag[p] % M; st[ls] %= M;
 41        st[rs] += pre[r - mid - 1] * tag[p] % M; st[rs] %= M;
 42        
 43        st1[ls] += tag[p];
 44        st1[rs] += tag[p];
 45        
 46        tag[p] = 0;
 47    }
 48}
 49
 50void update(int p, int l, int r, int L, int R, int x){
 51    if(L <= l && r <= R){
 52        st[p] += pre[r - l] * x % M; st[p] %= M;
 53        st1[p] += x; tag[p] += x;
 54        return ;
 55    }
 56    down(p, l, r);
 57    if(L <= mid) udpate(ls, l, mid, L, R, x);
 58    if(R > mid) update(rs, mid + 1, r, L , R, x);
 59    up(p, l, r);
 60}
 61
 62void purify(int p, int l, int r){
 63    if(st1[p] < mod) return;
 64    
 65    if(l == r){
 66        st[p] %= mod; st1[p] %= mod;
 67        return ;
 68    }
 69    down(p, l, r);
 70    if(st1[ls] >= mod) purify(ls, l, mid);
 71    if(st1[rs] >= mod) purify(rs, mid + 1, r);
 72    up(p, l, r);
 73}
 74
 75ll hsh(int p, int l, int r, int L, int R){
 76    if(L <= l && r <= R) return st[p];
 77    down(p, l, r);
 78    
 79    if(R <= mid) return hsh(ls, l, mid, L, R);
 80    else if(L > mid) return hsh(rs, mid + 1, r, L, R);
 81    else{
 82      /*
 83      需要注意！
 84      往子树递归时[L, R]要变化成[L, mid](不重要)和[mid + 1, R](重要)！
 85      */
 86        ll ans = hsh(ls, l, mid, L, mid);
 87        ans += hsh(rs, mid + 1, r, mid + 1, R) * po[mid - L + 1] % M;
 88        ans %= M;
 89        return ans;
 90    }
 91}
 92
 93int main(){
 94    //Fastin;
 95    po[0] = 1;
 96    for(int i = 1; i < maxn; i++) po[i] = po[i - 1] * 1ll * pp % M;
 97    pre[0] = 1;
 98    for(int i = 1; i < maxn; i++) pre[i] = pre[i - 1] + po[i], pre[i] %= M;
 99    
100    int n, m; scanf("%d %d", &n, &m);
101    for(int i = 1; i <= n; i++){
102        scanf("%d", a + i);
103        build(1, 1, n, i, a[i]);
104    }
105    
106    while(m--){
107        int op; scanf("%d", &op);
108        if(op == 1){
109            int l, r, x; scanf("%d %d %d", &l, &r, &x);
110            update(1, 1, n, l, r, x);
111          //每次更新完后都会将超出范围的叶子结点进行更新，实际应用时需要考虑复杂度是否支持！
112            purify(1, 1, n);
113        }
114        else{
115            int l, r, k; scanf("%d %d %d", &l, &r, &k);
116            
117            ll res1 = hsh(1, 1, n, l, l + k - 1);
118            ll res2 = hsh(1, 1, n, r, r + k - 1);
119            puts(res1 == res2? "yes": "no");
120        }
121    }
122    return 0;
123}

INPUT

数据长度n 操作次数m

$a_1, a_2,…,a_n$

$op_1, l_1, r_1, x_1$

$op_2, l_2, r_2, x_2$

…

$op_m, l_m, r_m, x_m$

功能

op为1，对区间[li, ri] += xi, 并对指定模数mod取模
op为2，查询以li和ri为起点的两端长度均为x的区间的哈希和，以此来判断序列是否相同。

线段树合并

子树最多出现次数颜色和的查询

 1/*
 2 动态开点线段树：
 3    - 插入一个节点
 4    - 合并两棵树
 5 维护出现最多的次数的颜色的和，记录两个值(出现次数，颜色和)
 6 */
 7#define mid ((l + r) >> 1)
 8const int maxn = 1e5 + 10;
 9const int M = 1e5 * 20 * 4;
10
11int n;
12int haed[maxn], top = 0, root[maxn];
13star edge[maxn << 2];
14void add(int u, int v){
15    edge[top].to = v;
16    edge[top].next = head[u];
17    head[u] = top++;
18}
19
20struct NODE{int mx; ll sum;};
21NODE st[M];
22int ls[M], rs[M], cnt = 1;
23//cnt必须从1开始！这是由merge的实现所决定的！
24//加入一个单点作为初始化
25void update(int &p, int l, int r, int k){
26    if(!p) p = cnt++;
27    if(l == r && l == k){
28        st[p].mx = 1; st[p].sum = k;
29        return ;
30    }
31    if(k <= mid){
32        update(ls[p], l, mid, k);
33        st[p] = st[ls[p]];
34    }
35    else{
36        update(rs[p], mid + 1, r, k);
37        st[p] = st[rs[p]];
38    }
39}
40
41void up(int p){
42    if(st[ls[p]].mx > st[rs[p]].mx) st[p] = st[ls[p]];
43    else if(st[ls[p]].mx < st[rs[p]].mx) st[p] = st[rs[p]];
44    else{
45        st[p].mx = st[ls[p]].mx;
46        st[p].sum = st[ls[p]].sum + st[rs[p]].sum;
47    }
48}
49//将r1与r2对应的两棵结构相同的线段树进行合并，返回值为合并后的树的标号
50int merge(int r1, int r2, int l, int r){
51    if(!r1) return r2;
52    if(!r2) return r1;
53    
54    if(l == r){
55        st[r1].mx += st[r2].mx;
56        return r1;
57    }
58    ls[r1] = merge(ls[r1], ls[r2], l, mid);
59    rs[r1] = merge(rs[r1], rs[r2], mid + 1, r);
60    up(r1);
61    return r1;
62}
63
64ll ans[maxn];
65void dfs(int now, int par){
66    for(int i = head[now]; ~i; i = edge[i].next){
67        int to = edge[i].to; if(to == par) continue;
68        dfs(to, now);
69        root[now] = merge(root[now], root[to], 1, n);
70    }
71    ans[now] = st[root[now]].sum;
72}
73
74
75int main(){
76//    Fastin;
77    clr(head, -1);
78    scanf("%d", &n);
79    for(int i = 1; i <= n; i++){
80        int c; scnaf("%d", &c);
81        udpate(root[i], 1, n, c);
82    }
83    for(int i = 0; i < n - 1; i++){
84        int u, v; scanf("%d %d", &u, &v);
85        add(u, v); add(v, u);
86    }
87    dfs(1, 0);
88    prt(ans + 1, n);
89    
90    return 0;
91}

给出一棵n节点的树，每个节点具有一个颜色。

输出在以1为根时，每个节点及其子树上所有节点中最多数量的颜色的和。

$n \leq 1e5, c_i \leq n$

每插入一个节点，会产生logn个新节点，因而总共至多产生nlogn个新节点。

而在每一次merge时，会合并掉一个节点，合并的复杂度是$O(1)$，所以至多进行nlogn次合并。

因而线段树合并的总体复杂度是$O(nlogn)$

segment tree beats

  1#define ls (p << 1)
  2#define rs ((p << 1) | 1)
  3#define mid ((l + r) >> 1)
  4
  5const int maxn = 1e6 + 10;
  6
  7int a[manx];
  8//st中记录区间和，mx记录最值，cnt记录最值的数量，smx记录第二极值的大小。
  9ll st[maxn << 2]; int mx[maxn << 2], cnt[maxn << 2], smx[maxn << 2];
 10
 11void up(int p){
 12    st[p] = st[ls] + st[rs];
 13    if(mx[ls] > mx[rs]){
 14        mx[p] = mx[ls];
 15        cnt[p] = cnt[ls];
 16        smx[p] = max(mx[rs], smx[ls]);
 17    }
 18    else if(mx[ls] < mx[rs]){
 19        mx[p] = mx[rs];
 20        cnt[p] = cnt[rs];
 21        smx[p] = max(mx[ls], smx[rs]);
 22    }
 23    else{
 24        mx[p] = mx[ls];
 25        cnt[p] = cnt[ls] + cnt[rs];
 26        smx[p] = max(smx[ls], smx[rs]);
 27    }
 28}
 29void fun(int p, int x){
 30    st[p] -= 1ll * cnt[p] * (mx[p] - x);
 31    mx[p] = x;
 32}
 33void down(int p){
 34    if(mx[ls] > mx[p] && mx[p] > smx[ls]) fun(ls, mx[p]);
 35    if(mx[rs] > mx[p] && mx[p] > smx[rs]) fun(rs, mx[p]);
 36}
 37void build(int p, int l, int r){
 38    if(l == r){
 39        st[p] = mx[p] = a[l];
 40        cnt[p] = 1;
 41        smx[p] = -1;
 42        return ;
 43    }
 44    build(ls, l, mid);
 45    build(rs, mid + 1, r);
 46    up(p);
 47}
 48
 49void update(int p, int l, int r, int L, int R, int x){
 50    if(mx[p] <= x) return;
 51    if(L <= l && r <= R){
 52        if(smx[p] < x){
 53            fun(p, x); return ;
 54        }
 55    }
 56    
 57    down(p);
 58    if(L <= mid) update(ls, l, mid, L, R, x);
 59    if(R > mid) update(rs, mid + 1, r, L, R, x);
 60    up(p);
 61}
 62
 63int getmx(int p, int l, int r, int L, int R){
 64    if(L <= l && r <= R) return mx[p];
 65    down(p);
 66    int ans = 0;
 67    if(L <= mid) ans = max(ans, getmx(ls, l, mid, L, R));
 68    if(R > mid) ans = max(ans, getmx(rs, mid + 1, r, L, R));
 69    return ans;
 70}
 71ll getsum(int p, int l, int r, int L, int R){
 72    if(L <= l && r <= R) return st[p];
 73    
 74    down(p);
 75    ll ans = 0;
 76    if(L <= mid) ans += getsum(ls, l, mid, L, R);
 77    if(R > mid) ans += getsum(rs, mid + 1, r, L, R);
 78    return ans;
 79}
 80
 81
 82int main(){
 83    // Fastin;
 84    TTT{
 85        int n, m; scanf("%d %d", &n, &m);
 86        for(int i = 1; i <= n; i++) scnaf("%d", a + i);
 87        build(1, 1, n);
 88
 89        while(m--){
 90            int op; scanf("%d", &op);
 91            int x, y, z;
 92            scanf("%d %d", &x, &y);
 93            if(op == 0){
 94                scnaf("%d", &z);
 95                update(1, 1, n, x, y, z);
 96            }
 97            else if(op == 1){
 98                printf("%d\n", getmx(1, 1, n, x, y));
 99            }
100            else{
101                printf("%lld\n", getsum(1, 1, n, x, y));
102            }
103        }
104    }
105    return 0;
106}

hdu 5306模板

给出长度为$n$的序列，要求支持如下操作:

给出$l ,r, x$，令$a_i = min(a_i, x), i = l, …, r$
给出$l, r$，查询区间中的最大值/区间和

听说不进行区间加减的话复杂度均摊$O(nlogn)$

8 DP

依赖背包（树上背包）

向上转移

状态转移时暴力枚举儿子的所有状况，将其更新到父亲中。

时间复杂度$O(N*M^2)$

向下传递

 1const int manx = 1e2 + 10;
 2
 3int n, W, v[maxn], w[maxn];
 4int dp[maxn][maxn];
 5star edge[maxn << 1];
 6int head[maxn], top = 0;
 7
 8void add(int u, int v){
 9    edge[top].to = v;
10    edge[top].next = head[u];
11    head[u] = top++;
12}
13
14//dp[i][j]表示i子树中重量为j下的最大价值
15void dfs(int u, int par){
16    dp[u][0] = 0;
17    for(int i = head[u]; ~i; i = edge[i].next){
18        int to = edge[i].to; if(to == par) continue;
19
20        for(int i = 0; i <= W; i++) dp[to][i] = dp[u][i];
21        dfs(to, u);
22        for(int i = W; i >= w[to]; i--) if(dp[to][i - w[to]] != -1)
23            dp[u][i] = max(dp[u][i], dp[to][i - w[to]] + v[to]);
24    } 
25}
26
27int main(int argc, char *argv[]){
28    // Fastin; 
29    clr(head, -1); clr(dp, -1);
30    
31    scanf("%d %d", &n, &W);
32    for(int i = 1; i <= n; i++){
33        int x, y, z; scanf("%d %d %d", &x, &y, &z); if(z == -1) z = 0;
34        w[i] = x; v[i] = y;
35        add(z, i);
36    }
37    
38    dfs(0, -1);
39    int ans = 0; for(int i = 0; i <= W; i++) ans = max(ans, dp[0][i]);
40    printf("%d\n", ans);
41
42    return 0;
43}

状态数组$dp[i][j]$表示不允许选取i本身的最大价值，所以在对i的儿子遍历时，其实是将所有儿子的情况更新到dp[i]中。每次将dp[i]的状态传递给儿子，儿子递归的更新完后再更新回dp[i]

如果采取这样的方法，必须使用超级源点！

时间复杂度$O(N*M)$

dfn序上更新背包

  1#include <iostream>
  2       
  3#include <algorithm>
  4#include <list>
  5#include <string>
  6#include <vector>
  7#include <stack>
  8#include <queue>
  9#include <set>
 10#include <map>
 11#include <unordered_map>
 12#include <unordered_set>
 13#include <random>
 14#include <chrono>
 15      
 16#include <cstdio>
 17#include <cstring>
 18#include <cmath>
 19#include <ctime>
 20#include <cstdlib>
 21#include <cassert>
 22 
 23#define manx maxn
 24#define whlie while
 25#define itn int
 26#define fro for
 27#define asn ans
 28#define scnaf scanf
 29#define sacnf scanf
 30#define pritnf printf
 31#define haed head
 32#define tmep temp
 33#define udpate update
 34#define cosnt const
 35
 36#define Fastin freopen("/home/rqdmap/Desktop/codes/in", "r", stdin)
 37#define Fastout freopen("/home/rqdmap/Desktop/codes/main.out", "w", stdout)
 38#define lowbit(x) ((x) & (-x))
 39#define clr(a, x) memset((a), x, sizeof (a))
 40#define TTT int __; scanf("%d", &__); for(int _ = 1; _ <= __; _++)
 41#define DEBUG printf("DEBUG LINE: %d\n", __LINE__)
 42#define NL puts("")
 43using namespace std;
 44typedef unsigned long long ull;
 45typedef long long ll;
 46 
 47/*------------------------------------------------------------------------------------*/
 48clock_t startTime;
 49double getCurrentTime() {
 50	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
 51}
 52template<typename T>
 53void prt(T *a, int n, bool withid = 0){
 54    if(!withid) for(int i = 0; i < n; i++) cout << a[i] << ((i == n - 1)? '\n':' ');
 55    else for(int i = 0; i < n; i++) cout << i << ": " << a[i] << '\n';
 56}
 57 
 58template<typename T>
 59T ceil(T a, T b){return (a + b - 1) / b;}
 60template<typename T>
 61T gcd(T x, T y){return !x? y: gcd(y % x, x);}
 62template<typename T>
 63void exgcd(T a, T b, T &x, T &y){
 64    if(!b){x = 1; y = 0;return;}
 65    exgcd(b, a % b, y, x); y -= a / b * x;
 66}
 67ll qp(ll a, ll p){
 68    if(p < 0) return 0;
 69    ll ans = 1; while(p){if(p & 1) ans = ans * a ; a = a * a; p >>= 1;}
 70    return ans;
 71}
 72ll qp(ll a, ll p, ll M){
 73    ll ans = 1; while(p){ if(p & 1) ans = ans * a % M; a = a * a % M; p >>= 1;}
 74    return (ans % M + M) % M;
 75}
 76int euler(int *prime, int *vis, int n){
 77    int top = 0;
 78    for(int i = 0; i <= n; i++) vis[i] = 0;
 79    for(int i = 2; i <= n; i++){
 80        if(!vis[i]) prime[top++] = i;
 81        for(int j = 0; j < top && i * prime[j] <= n; j++){
 82            vis[i * prime[j]] = 1;
 83            if(i % prime[j] == 0) break;
 84        }
 85    }
 86    return top;
 87}
 88struct star{int to, next, w;}; 
 89/*------------------------------------------------------------------------------------*/
 90
 91const int maxn = 2e3 + 10;
 92const int maxe = 1e6 + 10;
 93const int K =  2e3 + 10;
 94const int M = 1e9 + 7;
 95
 96int n, W;
 97int head[maxn], top = 0;
 98int w[maxn];
 99star edge[maxe << 1];
100void add(int u, int v){
101    edge[top].to = v;
102    edge[top].next = head[u];
103    head[u] = top++;
104}
105
106int mx[maxn], root, vis[maxn], S, sze[maxn];
107void getroot(int now, int par){
108    sze[now] = 1; mx[now] = 0;
109    for(int i = head[now]; ~i; i = edge[i].next){
110        int to = edge[i].to; if(vis[to] || to == par) continue;
111        getroot(to, now);
112        sze[now] += sze[to];
113        mx[now] = max(mx[now], sze[to]);
114    }
115    mx[now] = max(mx[now], S - mx[now]);
116    if(mx[now] < mx[root]) root = now;
117}
118
119int dfn[maxn], cnt = 0;
120void dfs(int now, int par){
121    dfn[cnt++] = now; sze[now] = 1;
122    for(int i = haed[now]; ~i; i = edge[i].next){
123        int to = edge[i].to; if(vis[to] || par == to) continue;
124        dfs(to, now);
125        sze[now] += sze[to];
126    }
127}
128ll ans = 0;
129ll dp[maxn][K];
130vector<int> vec;
131int mp[K * K];
132
133void fun(int now){
134    cnt = 0; dfs(now, -1);
135
136    for(int i = 0; i <= cnt; i++) for(int j = 0; j < vec.size(); j++) dp[i][j] = 0;
137    dp[cnt][0] = 1;
138
139    for(int i = cnt - 1; i >= 0; i--){
140        int u = dfn[i];
141        for(int j = 0; j < vec.size(); j++){
142            if(vec[j] / w[u]){
143                int pos = mp[vec[j] / w[u]];
144                //从当前子树中更新背包的计数
145                dp[i][pos] += dp[i + 1][j];
146                dp[i][pos] %= M;
147            }
148            //继承右兄弟的计数方案，为随后传递给父亲不断积累
149            dp[i][j] += dp[i + sze[u]][j];
150            dp[i][j] %= M;
151        }
152    }
153    for(int i = 0; i < (itn)vec.size(); i++) ans = (ans + dp[0][i]) % M;
154    ans = (ans + M - 1) % M;
155}
156
157void sove(int now){
158    vis[now] = 1; 
159    fun(now);
160    
161    for(int i = head[now]; ~i; i = edge[i].next){
162        int to = edge[i].to; if(vis[to]) continue;
163
164        S = sze[to]; root = 0;
165        getroot(to, now);
166        sove(root);
167    }
168}
169
170int main(){
171    // Fastin; 
172    TTT{
173        ans = 0;
174        clr(head, -1); top = 0;
175        scanf("%d %d", &n, &W);
176        for(int i = 1; i <= n; i++) scnaf("%d", w + i);
177        for(int i = 0; i < n - 1; i++){
178            int u, v; scanfclrv, u);
179        }
180        vec.clear(); clr(mp, 0);
181        for(int i = 1; i <= W; i++){
182            int res = W / i; 
183            if(vec.empty() || *vec.rbegin() != res) vec.push_back(res);
184        }
185        for(int i = 0; i < vec.size(); i++) mp[vec[i]] = i;
186
187        root = 0;
188        S = mx[0] = n;
189        clr(vis, 0); clr(dp, -1);
190        getroot(1, 0); sove(root);
191
192        printf("%lld\n", ans);
193    }
194
195    return 0;
196}

给出一颗依赖树，每个节点都表示一个有若干重量的物品。

一个连通块的总重量定义为连通块内所有节点的重量积。

问总重量不超过$W$的连通块个数。

这是一道综合的例题：点分治后在每个连通块中的dfn序列上进行背包更新，更新时不遍历所有可能的重量，而是遍历乘积压缩后的状态。

为了学习dfn序更新背包的知识，着重研究fun数组即可。

$dp[i][j]$由两部分构成，一部分是dfn[i]节点本身子树构成的总重量w满足$\frac W w=j$的计数方案，另一部分递归地继承dfs树上i的右兄弟的若干信息。

因而除了根节点的dp数组为其真实情况以外，其余节点的dp数组均有一些继承右兄弟而来的计数方案，这些方案在最终这一串兄弟们回归到父亲后统一进行贡献。

10 技术

1 快读

 1template <typename _t>
 2inline void read(_t &x){
 3    x = 0; _t fu = 1; char ch = getchar();
 4    while(ch < '0' || ch > '9'){if(ch == '-') fu = - 1; ch = getchar();}
 5    while(ch >= '0' && ch <= '9'){
 6        x = (x << 3) + (x << 1) + (ch & 15);
 7        ch = getchar();
 8    }
 9    x *= fu ;
10}

2 对拍(linux)

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4
 5const int maxn = 1e3 + 10;
 6
 7string s;
 8char str[][100] = {"", "main.cpp", "std.cpp", "data.cpp"};
 9
10int main(int argc, char * argv[]) {
11    if(argc != 4 && argc != 1){
12        fprintf(stderr, "Input $main $std $data!\n");
13        exit(0);
14    }
15
16    if(argc == 4){
17        for(int i = 1; i <= 3; i++) strcpy(str[i], argv[i]);
18    }
19    
20    s = (string){"g++ "} + str[1] + " -o main";
21    system(s.c_str());
22    puts("原始程序编译完成.");
23
24    s = (string){"g++ "} + str[2] + " -o std";
25    system(s.c_str());
26
27    s = (string){"g++ "} + str[3] + " -o data";
28    system(s.c_str());
29    puts("数据生成器编译完成");
30
31    int cnt = 0;
32    while(1){
33        system("./data > in");
34        system("./main < in > main.out");
35        system("./std < in > std.out");
36
37        if(system("diff main.out std.out")){
38            puts("Differences occur!");
39            puts("--------------Input data:--------------");
40            system("cat in");
41            break;
42        }
43        printf("No.%d's OK.\n", cnt++);
44    }
45    return 0;
46}