跳转至

整体二分

——爆改cdq。

整体二分可以在 O((n+q)log⁡Vlog⁡⁡n)O((n+q)\log V \log ⁡n) 的时间复杂度内离线、批量处理区间第 kk 排名问题。如果一个一个二分答案处理询问，那每次询问都要遍历整个区间 log⁡V\log V 遍，复杂度将达到 O(nqlog⁡V)O(nq\log V)，是我们不能接受的。

注意到每次二分 check() 都会遍历整个数组（区间），但只进行了一次查询，效率低下。我们希望可以将有需要的询问放在一起查询，并且只修改数组中有用的位置。因此，我们可以把数组的每个位置看成一个单点修改操作，和查询操作混合之后送入 cdq 分治中“整体”地进行二分。

大体思路和 cdq 相同：

  • 每次递归传入操作集合 op 和区间 [l,r][l,r]，表示修改操作的 val 和查询操作的答案都位于值域 [l,r][l,r] 内； （开始时序列默认为空，每一个初始数字视为一个修改）
  • 统计值域左半区间内的修改对所有查询的贡献； （将所有 val≤midval\le mid 的修改按时间顺序加入树状数组，查询操作即在树状数组上做区间查询）
  • 判断查询应下放到左右哪个区间； （如果区间查询的结果 cntcnt 满足 k≤cntk\le cnt，说明第 kk 小的数字一定小于等于 midmid，否则一定大于 midmid）
  • 分割操作至左右两区间，递归调用； （注意，如果判断查询的答案在值域右半区间，则应把左半区间的贡献计入，执行 k -= cnt）

核心：

  • 通过 cdq 压掉值域维度，使树状数组可以用来维护数组下标；

易错点

把查询下方到右区间时，要把左区间的贡献减去。

剪枝优化

因为整体二分是值域上的递归，若不剪枝，时间复杂度会达到 O(2V)O(2V)。所以要判断操作集合是否为空，若为空则直接返回即可。这样能保证每个操作都只会产生一条 log⁡V\log V 的路径，从而将递归时间复杂度限制在 O(qlog⁡V)O(q\log V)。

海亮 OJ 题单

P3834 【模板】可持久化线段树 2

求给定序列的区间第 kk 小。

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<vector>
using namespace std;
const int N = 2E5 + 10;
const int A = 1e9;

struct Op {
    int x, y, k;
    int id, tp;
};

int n, Q;
int ans[N];

namespace BIT {
    int sum[N];
    inline int lowbit(int x) { return x & -x; }
    inline void modify(int p, int v) {
        for(int i = p; i <= n; i += lowbit(i)) {
            sum[i] += v;
        }
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) {
            res += sum[i];
        }
        return res;
    }
    inline int query(int l, int r) {
        return query(r) - query(l - 1);
    }
}

void solve(vector<Op> &op, int l, int r) {
    if(op.empty()) return;
    if(l == r) {
        for(Op o : op) {
            if(o.tp == 0) {
                ans[o.id] = l;
            }
        }
        return;
    }
    int mid = (l + r) >> 1;
    for(Op o : op) {
        if(o.tp == 1 && o.x <= mid) BIT::modify(o.id, 1); 
    }
    vector<Op> lop, rop;
    for(Op o : op) {
        if(o.tp == 0) {
            int cnt = BIT::query(o.x, o.y);
            if(cnt >= o.k) lop.push_back(o);
            else rop.push_back({o.x, o.y, o.k - cnt, o.id, o.tp});
        } else {
            if(o.x <= mid) lop.push_back(o);
            else rop.push_back(o); 
        }
    }
    for(Op o : op) {
        if(o.tp == 1 && o.x <= mid) BIT::modify(o.id, -1);
    }
    solve(lop, l, mid);
    solve(rop, mid + 1, r);
}

vector<Op> op;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> Q;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        op.push_back({x, 0, 0, i, 1}); 
    }
    for(int i = 1; i <= Q; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        op.push_back({l, r, k, i, 0});
    }

    solve(op, -A, A);

    for(int i = 1; i <= Q; i++) {
        cout << ans[i] << '\n'; 
    }

    return 0;
}

P2617 Dynamic Rankings

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include<iostream>
#include<vector>
using namespace std;
const int N = 1E5 + 10;
const int A = 1E9; 

struct Op {
    int x, y, k;
    int id, tp;
};

int n, m;
int ans[N];

namespace BIT {
    int sum[N];
    inline int lowbit(int x) { return x & -x; }
    inline void modify(int p, int v) {
        for(int i = p; i <= n; i += lowbit(i)) {
            sum[i] += v;
        } 
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) {
            res += sum[i];
        }
        return res;
    } 
    inline int query(int l, int r) {
        return query(r) - query(l - 1);
    }
}

void cdq(vector<Op> &op, int l, int r) {
    if(op.empty()) return; 
    if(l == r) {
        for(Op o : op) {
            if(o.tp == 0) ans[o.id] = l;
        }
        return;
    }
    int mid = (l + r) >> 1;
    vector<Op> lop, rop;
    for(Op o : op) {
        if(o.tp == 0) {
            int lcnt = BIT::query(o.x, o.y);
            if(o.k <= lcnt) lop.push_back(o);
            else rop.push_back({o.x, o.y, o.k - lcnt, o.id, o.tp}); 
        } else if(o.x <= mid) {
            BIT::modify(o.id, o.tp);
            lop.push_back(o);
        } else {
            rop.push_back(o);
        }
    }
    for(Op o : op) {
        if(o.tp && o.x <= mid) {
            BIT::modify(o.id, -o.tp);
        }
    }
    cdq(lop, l, mid);
    cdq(rop, mid + 1, r);
} 

int a[N];
vector<Op> op;

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        op.push_back({a[i], 0, 0, i, 1});
    }

    int nq = 0;
    while(m--) {
        char c;
        int l, r, x, y, k;
        cin >> c;
        if(c == 'Q') {
            cin >> l >> r >> k;
            op.push_back({l, r, k, ++nq, 0}); 
        } else {
            cin >> x >> y;
            op.push_back({a[x], 0, 0, x, -1});
            op.push_back({y, 0, 0, x, 1});
            a[x] = y;
        }
    }

    cdq(op, 0, A);

    for(int i = 1; i <= nq; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

P3332 [ZJOI2013] K大数查询

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int N = 5E4 + 10;

struct Op {
    int l, r, k;
    int id, tp;
};

int n, m;
int ans[N];

namespace BIT {
    int sum[N], sum2[N];
    inline int lowbit(int x) { return x & -x; }
    inline void modify(int p, int v) {
        for(int i = p; i <= n + 5; i += lowbit(i)) {
            sum[i] += v;
            sum2[i] += p * v;
        }
    } 
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) {
            res += -sum2[i] + sum[i] * (p + 1);
        }
        return res;
    }
    inline void modify(int l, int r, int v) {
        modify(l, v);
        modify(r + 1, -v);
    }
    inline int query(int l, int r) {
        return query(r) - query(l - 1);
    }
}

struct Operation {
    int o, l, r, c;
} q[N];

void cdq(vector<Op> &op, int l, int r) {
    if(op.empty()) return;
    if(l == r) {
        for(Op o : op) {
            if(o.tp == 0) ans[o.id] = l;
        }
        return;
    }
    int mid = (l + r) >> 1;
    vector<Op> lop, rop; 
    for(Op o : op) {
        if(o.tp == 1) {
            if(o.k > mid) {
                BIT::modify(o.l, o.r, 1);
                rop.push_back(o);
            } else {
                lop.push_back(o); 
            }
        } else {
            int cnt = BIT::query(o.l, o.r);
            if(cnt >= o.k) {
                rop.push_back(o);
            } else {
                lop.push_back({o.l, o.r, o.k - cnt, o.id, o.tp});
            }
        }
    }
    for(Op o : op) {
        if(o.tp == 1 && o.k > mid) BIT::modify(o.l, o.r, -1); 
    }
    cdq(lop, l, mid);
    cdq(rop, mid + 1, r);
}

vector<Op> op;

signed main() {

    cin >> n >> m;

    int nq = 0;
    for(int i = 1; i <= m; i++) {
        int o, l, r, c;
        cin >> o >> l >> r >> c;
        if(o == 1) {
            op.push_back({l, r, c, 0, 1});
        } else {
            op.push_back({l, r, c, ++nq, 0});
        }
    } 

    cdq(op, -N, N);

    for(int i = 1; i <= nq; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

P1527 [国家集训队] 矩阵乘法

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include<iostream>
#include<vector>
using namespace std;
const int N = 510;
const int A = 1e9;

const int Q = 6E4 + 10;

struct Op {
    int x1, y1, x2, y2, k;
    int id, tp;
};

int n, q;
int ans[Q];

namespace BIT {
    inline int lowbit(int x) { return x & -x; }
    int sum[N][N];
    inline void modify(int x, int y, int v) {
        for(int i = x; i <= n; i += lowbit(i)) {
            for(int j = y; j <= n; j += lowbit(j)) {
                sum[i][j] += v;
            }
        } 
    }
    inline int query(int x, int y) {
        int res = 0;
        for(int i = x; i > 0; i -= lowbit(i)) {
            for(int j = y; j > 0; j -= lowbit(j)) {
                res += sum[i][j]; 
            } 
        }
        return res;
    }
    inline int query(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
    }
}

void cdq(vector<Op> &op, int l, int r) {
    if(op.empty()) return;
    if(l == r) {
        for(Op o : op) {
            ans[o.id] = l;
        } 
        return;
    }
    int mid = (l + r) >> 1;
    vector<Op> lop, rop;
    for(Op o : op) {
        if(o.tp == 0) {
            int cnt = BIT::query(o.x1, o.y1, o.x2, o.y2);
            if(o.k <= cnt) {
                lop.push_back(o);
            } else rop.push_back({o.x1, o.y1, o.x2, o.y2, o.k - cnt, o.id, o.tp});
        } else {
            if(o.k <= mid) {
                BIT::modify(o.x1, o.y1, 1);
                lop.push_back(o);
            } else rop.push_back(o);
        }
    } 
    for(Op o : op) {
        if(o.tp == 1 && o.k <= mid) BIT::modify(o.x1, o.y1, -1);
    }
    cdq(lop, l, mid);
    cdq(rop, mid + 1, r);
} 

vector<Op> op;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            op.push_back({i, j, 0, 0, x, 0, 1});
        } 
    }

    for(int i = 1; i <= q; i++) {
        int x1, y1, x2, y2, k;
        cin >> x1 >> y1 >> x2 >> y2 >> k;
        op.push_back({x1, y1, x2, y2, k, i, 0});
    }

    cdq(op, 0, A);

    for(int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

P7424 [THUPC2017] 天天爱射击

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include<iostream>
#include<vector>
using namespace std;
const int N = 2E5 + 10;
const int A = 2E5;

struct Op {
    int x, y, k;
    int id, tp;
};

int n, m;
int ans[N];

namespace BIT {
    inline int lowbit(int x) { return x & -x; }
    int sum[N];
    inline void modify(int p, int v) {
        for(int i = p; i <= A + 5; i += lowbit(i)) {
            sum[i] += v;
        }
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) {
            res += sum[i];
        }
        return res;
    } 
    inline int query(int l, int r) {
        return query(r) - query(l - 1); 
    }
}

void cdq(vector<Op> &op, int l, int r) {
    if(op.empty()) return;
    if(l == r) {
        for(Op o : op) {
            if(o.tp == 0) ans[o.id] = l;
        }
        return;
    }
    int mid = (l + r) >> 1;
    vector<Op> lop, rop;
    for(Op o : op) {
        if(o.tp == 1) {
            if(o.k <= mid) {
                BIT::modify(o.x, 1);
                lop.push_back(o);
            } else rop.push_back(o);
        } else {
            int cnt = BIT::query(o.x, o.y);
            if(o.k <= cnt) lop.push_back(o);
            else rop.push_back({o.x, o.y, o.k - cnt, o.id, o.tp}); 
        }
    }
    for(Op o : op) {
        if(o.tp == 1 && o.k <= mid) BIT::modify(o.x, -1);
    } 
    cdq(lop, l, mid);
    cdq(rop, mid + 1, r);
} 

vector<Op> op;

struct Query {
    int l, r, k;
} q[N];

int cnt[N];

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> q[i].l >> q[i].r >> q[i].k;
    }

    for(int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        op.push_back({x, 0, i, 0, 1});
    }

    for(int i = 1; i <= n; i++) {
        op.push_back({q[i].l, q[i].r, q[i].k, i, 0});
    }

    cdq(op, 1, A + 1);

    for(int i = 1; i <= n; i++) {
        cnt[ans[i]]++;
    }

    for(int i = 1; i <= m; i++) {
        cout << cnt[i] << '\n';
    }

    return 0;
}

P3527 [POI2011] MET-Meteors

首先破环为链：

  • 对于操作区间（指陨石落下的区间）满足 l≤rl\le r 的情况，此时 [l,r][l,r] 就是修改区间，无需额外处理；
  • 对于操作区间 l>rl>r 的情况，将其拆为 [1,r]∪[l,m][1,r]\cup[l,m] 即可；

这样问题就转化到了链上。

我们视每次陨石为一次（区间）修改操作，每个国家的 pip_i 为（查询第 kk 小）一个查询操作，进行整体二分。可以这么理解：将每次陨石拆成单块的陨石（比如一次降落三块，就拆成 1+1+11+1+1）；然后每个国家就是在查询落到本国家的时间第 pip_i 小的陨石是第几次降落下来的。

但是一个国家的空间站是分散的，不是一个连续的区间，如何统计？

但是我们注意到每一个位置只会有一个国家的空间站，也就是说，所有国家的空间站的总数为 mm。对于每一个查询，我们可以枚举这个国家的所有空间站。这样即使我们枚举了所有国家，均摊时间复杂度也不会超过 O(m)O(m)。

因此，在二分时：

  • 对于修改操作：使用树状数组区间处理所有 ti≤midt_i\le mid（降落时间小于 midmid）的修改操作；
  • 对于查询操作：暴力枚举该国家的所有空间站，单点查询每一个空间站在本次递归中收获了多少陨石，直接进行累加，和 pip_i 比较，决定将查询操作下方到左区间还是右区间。

时间复杂度分析

对于每个修改操作（陨石下落），会产生从根到叶子的一条路径，长为 log⁡V\log V；在每个节点（二分的一个区间）处会进行两次树状数组的操作，时间复杂度 O(log⁡n)O(\log n)；因此修改操作产生的总时间复杂度为 O(klog⁡nlog⁡V)O(k\log n \log V)；

对于每个查询操作，在每个节点处会产生 O(mnlog⁡n)O(\frac{m}{n}\log n) 的时间复杂度（mn\frac{m}{n} 表示每个国家分到的平均空间站数量），因此总的均摊时间复杂度为 O(mlog⁡nlog⁡V)O(m\log n \log V)；

综上，代码的总时间复杂度为 O((m+k)log⁡nlog⁡V)O\big((m+k)\log n \log V\big)，可以通过本题。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include<iostream>
#include<vector>
#define int long long
using namespace std;
const int N = 3E5 + 10;

struct Op {
    int x, y, k;
    int id, tp;
};

int n, m, k;
int a[N], p[N];
int ans[N];

vector<int> pos[N]; 

namespace BIT {
    inline int lowbit(int x) { return x & -x; }
    __int128 sum[N];
    inline void modify(int p, int v) {
        for(int i = p; i <= m + 5; i += lowbit(i)) {
            sum[i] += v;
        }
    }
    inline int query(int p) {
        __int128 res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) {
            res += sum[i];
        } 
        return res;
    }
    inline void modify(int l, int r, int v) {
        modify(l, v);
        modify(r + 1, -v);
    }
}

void cdq(vector<Op> &op, int l, int r) {
    if(op.empty()) return;
    if(l == r) {
        for(Op o : op) {
            if(o.tp == 0) ans[o.id] = l; 
        }
        return;
    }
    int mid = (l + r) >> 1;
    vector<Op> lop, rop;
    for(Op o : op) {
        if(o.tp == 1) {
            if(o.id <= mid) {
                BIT::modify(o.x, o.y, o.k);
                lop.push_back(o);
            } else {
                rop.push_back(o);
            }
        } else {
            __int128 sum = 0;
            for(int i : pos[o.x]) {
                sum += BIT::query(i); 
            }
            if(o.k <= sum) lop.push_back(o);
            else rop.push_back({o.x, o.y, o.k - sum, o.id, o.tp});
        }
    } 
    for(Op o : op) {
        if(o.tp == 1 && o.id <= mid) BIT::modify(o.x, o.y, -o.k);
    } 
    cdq(lop, l, mid);
    cdq(rop, mid + 1, r);
}

vector<Op> op;

signed main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i); 
    }
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
    }

    cin >> k;
    for(int i = 1; i <= k; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        if(l <= r) {
            op.push_back({l, r, k, i, 1});
        } else {
            op.push_back({l, m, k, i, 1});
            op.push_back({1, r, k, i, 1}); 
        }
    } 

    for(int i = 1; i <= n; i++) {
        op.push_back({i, 0, p[i], i, 0});
    }

    cdq(op, 1, k + 5);

    for(int i = 1; i <= n; i++) {
        if(ans[i] <= k) cout << ans[i] << '\n';
        else cout << "NIE\n"; 
    }

    return 0;
}

P3242 [HNOI2015] 接水果

整体二分套扫描线。

题目要求查询 被路径* u→vu\rightarrow v 包含的路径中，权值第 kk 小的权值，考虑整体二分。

*注：本文中提到的所有路径 u→vu\rightarrow v，默认满足 dfn[u]<dfn[v]dfn[u]<dfn[v]；若题目输入不满足此条件，执行 swap(x, y) 即可。

查询第 kk 小，考虑整体二分。经过 cdq 之后，我们需要解决一个子问题：实现以下两种操作：

  • 向集合中加入一条路径；
  • 给定路径 u→vu\rightarrow v，统计集合中被路径 u→vu\rightarrow v 包含的路径数量；

我们发现，路径 u1→v1u_1\rightarrow v_1 包含路径 u→vu\rightarrow v，本质上是对两端节点 u1u_1 和 v1v_1 做了 dfn 序的约束。u1u_1 和 v1v_1 的 dfn 序的约束相互独立，这是一种二维数点问题，考虑使用扫描线求解。

当 xx 和 yy 满足 lca(x,y)=xlca(x,y) = x 时（返祖链），记 lca2(x,y)lca2(x, y) 表示 lca(x,y)lca(x,y) 向 yy 方向的直系儿子。

具体的，对于一个修改（盘子） x→yx\rightarrow y，会对所有 包含它 的查询产生 11 的贡献：

  • 当 lca(x,y)=xlca(x,y)=x 时，会贡献到满足以下条件的查询：
{dfn[x1]∈[1,dfn[lca2(x,y)]−1]dfn[y1]∈[dfn[y],dfn[y]+sz[y]−1] \begin{cases} dfn[x_1]\in\big[1,dfn[lca2(x, y)]-1\big]\\ dfn[y_1]\in\big[dfn[y],dfn[y]+sz[y]-1\big] \end{cases}

或

{dfn[x1]∈[dfn[lca2(x,y)]+sz[lca2],n]dfn[y1]∈[dfn[y],dfn[y]+sz[y]−1] \begin{cases} dfn[x_1]\in\big[dfn[lca2(x,y)]+sz[lca2],n\big]\\ dfn[y_1]\in\big[dfn[y],dfn[y]+sz[y]-1\big] \end{cases}
  • 当 lca(x,y)≠xlca(x,y)\ne x 时（lcalca 不会等于 yy，因为 xx 的 dfn 序比 yy 小），会贡献到满足以下条件的查询：
{dfn[x1]∈[dfn[x],dfn[x]+sz[x]−1]dfn[y1]∈[dfn[y],dfn[y]+sz[y]−1] \begin{cases} dfn[x_1]\in\big[dfn[x],dfn[x]+sz[x]-1\big]\\ dfn[y_1]\in\big[dfn[y],dfn[y]+sz[y]-1\big] \end{cases}

这种约束可以直接使用扫描线统计贡献。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
struct cOp {
    int a; // 第一维的 dfn 序，是排序关键字
    int b1; // 第二维的 dfn 序，是树状数组的下标的下界 
    int b2; // 上界 
    int w; // 修改、查询的贡献系数 
    int id; // 查询时答案存储的位置 
    int tp; // 0 表示查询，1 表示修改 
    inline bool operator<(const cOp &other) const {
        if(a != other.a) return a < other.a;
        return tp > other.tp;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int x = o.x, y = o.y, lca = LCA::lca(x, y);
if(lca == x) {
    int lca2 = LCA::lca(x, y, 1);
    cop.push_back({0,                 dfn[y],                dfn[y] + sz[y] - 1,     1, 0, 1});
    cop.push_back({dfn[lca2],         dfn[y],                dfn[y] + sz[y] - 1,    -1, 0, 1});
    cop.push_back({dfn[y],            dfn[lca2] + sz[lca2],  n + 5,                  1, 0, 1});
    cop.push_back({dfn[y] + sz[y],    dfn[lca2] + sz[lca2],  n + 5,                 -1, 0, 1});
} else {
    cop.push_back({dfn[x],            dfn[y], dfn[y] + sz[y] - 1,  1, 0, 1});
    cop.push_back({dfn[x] + sz[x],    dfn[y], dfn[y] + sz[y] - 1, -1, 0, 1});
}
代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int N = 4E4 + 10;
const int LOGN = 16;
const int A = 1E9;

struct Edge {
    int v;
    int next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

struct Op {
    int x, y, k;
    int id, tp;
};

struct cOp {
    int a; // 第一维的 dfn 序，是排序关键字
    int b1; // 第二维的 dfn 序，是树状数组的下标的下界 
    int b2; // 上界 
    int w; // 修改、查询的权值 
    int id; // 查询时答案存储的位置 
    int tp; // 0 表示查询，1 表示修改 
    inline bool operator<(const cOp &other) const {
        if(a != other.a) return a < other.a;
        return tp > other.tp;
    }
};

int n, p, q;

int dfn[N], fa[N], sz[N], dt;

namespace LCA {

    int dep[N], anc[N][LOGN];

    void init(int u, int f) {
        dep[u] = dep[f] + 1;
        anc[u][0] = f;
        dfn[u] = ++dt;
        fa[u] = f;
        sz[u] = 1;
        for(int i = 1; i < LOGN; i++) {
            anc[u][i] = anc[ anc[u][i - 1] ][i - 1];
        }
        for(int i = head[u]; i; i = pool[i].next) {
            int v = pool[i].v;
            if(v == f) continue;
            init(v, u);
            sz[u] += sz[v];
        }
    }

    int lca(int x, int y, bool MODE = 0) {
        if(dep[x] < dep[y]) swap(x, y);
        for(int i = LOGN - 1; i >= 0; i--) {
            if(dep[anc[x][i]] > dep[y]) x = anc[x][i]; 
        }
        if(anc[x][0] == y) {
            if(MODE) return x;
            else return y;
        }
        x = anc[x][0];
        for(int i = LOGN - 1; i >= 0; i--) {
            if(anc[x][i] != anc[y][i]) {
                x = anc[x][i];
                y = anc[y][i];
            }
        }
        if(MODE) return x;
        return anc[x][0];
    }

}

namespace BIT {
    inline int lowbit(int x) { return x & -x; }
    int sum[N], sum2[N];
    inline void modify(int p, int v) {
        for(int i = p; i <= n + 5; i += lowbit(i)) {
            sum[i] += v;
            sum2[i] += v * p;
        }
    }
    inline void modify(int l, int r, int v) {
        modify(l, v);
        modify(r + 1, -v);
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) {
            res += sum[i] * (p + 1) - sum2[i];
        }
        return res;
    }
    inline int query(int l, int r) {
        return query(r) - query(l - 1);
    }
}

vector<cOp> cop;
int ans[N], res[4 * N];

void cdq(vector<Op> &op, int l, int r) {
    if(op.empty()) return;
    if(l == r) {
        for(Op o : op) {
            if(o.tp == 0) {
                ans[o.id] = l;
            }
        }
        return;
    }
    int mid = (l + r) >> 1;
    cop.clear();
    for(int i = 0; i < (int)op.size(); i++) {
        Op o = op[i];
        if(o.tp == 1) {
            if(o.k <= mid) {
                int x = o.x, y = o.y, lca = LCA::lca(x, y);
                if(lca == x) {
                    int lca2 = LCA::lca(x, y, 1);
                    cop.push_back({0,                 dfn[y],                 dfn[y] + sz[y] - 1,     1, 0, 1});
                    cop.push_back({dfn[lca2],        dfn[y],                 dfn[y] + sz[y] - 1, -1, 0, 1});
                    cop.push_back({dfn[y],             dfn[lca2] + sz[lca2],     n + 5,                    1, 0, 1});
                    cop.push_back({dfn[y] + sz[y],     dfn[lca2] + sz[lca2],     n + 5,                    -1, 0, 1});
                } else {
                    cop.push_back({dfn[x],             dfn[y], dfn[y] + sz[y] - 1,  1, 0, 1});
                    cop.push_back({dfn[x] + sz[x],     dfn[y], dfn[y] + sz[y] - 1, -1, 0, 1});
                }
            } 
        } else {
            int x = o.x, y = o.y;
            cop.push_back({dfn[x], dfn[y], dfn[y], 1, i, 0});
        }
    }
    sort(cop.begin(), cop.end());
    for(int i = 0; i < (int)op.size(); i++) {
        res[i] = 0;
    }
    for(cOp o : cop) {
        if(o.tp == 1) {
            BIT::modify(o.b1, o.b2, o.w);
        } else {
            res[o.id] += BIT::query(o.b1, o.b2);
        }
    }
    for(cOp o : cop) {
        if(o.tp == 1) {
            BIT::modify(o.b1, o.b2, -o.w);
        }
    }
    vector<Op> lop, rop;
    for(int i = 0; i < (int)op.size(); i++) {
        Op o = op[i];
        if(o.tp == 0) {
            if(o.k <= res[i]) lop.push_back(o);
            else rop.push_back({o.x, o.y, o.k - res[i], o.id, o.tp});
        } else {
            if(o.k <= mid) lop.push_back(o);
            else rop.push_back(o); 
        }
    }
    cdq(lop, l, mid);
    cdq(rop, mid + 1, r); 
}

vector<Op> op;

signed main() {

    cin >> n >> p >> q;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    LCA::init(1, 0);

    for(int i = 1; i <= p; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if(dfn[a] > dfn[b]) swap(a, b);
        op.push_back({a, b, c, 0, 1});
    }

    for(int i = 1; i <= q; i++) {
        int u, v, k;
        cin >> u >> v >> k;
        if(dfn[u] > dfn[v]) swap(u, v);
        op.push_back({u, v, k, i, 0});
    }

    cdq(op, 0, A);

    for(int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}