可持久化线段树

可持久化线段树是动态开点的权值线段树，同时维护了历史信息

对于一个普通的权值线段树，当我们让 cntv + + 时，影响的节点个数是 logn，可持久化线段树的插入操作就是基于此。也就是，当我们插入新值时只需要动态的新建 logn 个节点即可，其他节点都可以复用上个版本。这样我们就可以在较小的时空复杂度维护所有的历史记录，然后利用前缀和的思想维护区间信息。

简单应用区间第 k 大

我们将 ai 依次插入，用 cnt 维护某值域值的个数。若要查 [l, r] 的第 k 大，因为维护了插入了 a[1, l − 1] 和 a[1, r] 时的所有的 cnt 信息，就可以利用前缀和思想算出，只插入 a[l, r] 的 cnt 信息。

具体来说，若有节点 p，其对应值域 [x, y]，在插入 a[1, l − 1] 后值的数量为 cntu，在插入 a[1, r] 后为 cntv，则 cntv − cntu 就是 i ∈ [l, r], ai ∈ [x, y] 的值的个数。

这就相当于对于一个区间 [l, r]，知道了每个值域段的 cnt 信息，之后就可以类似于二叉搜索树去找第 k 大。

题目链接 : 【模板】可持久化线段树 2

MYCODE

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int inf = 0x3f3f3f3f;

struct PresidentTree{
    int n, tot;
    vector<int> root, lp, rp, cnt;

    void init(int n_){
        tot = 0;
        n = n_;
        root = vector<int>(n + 1);
        lp = rp = cnt = vector<int>(4*n + 17*n);
    }
    
    void insert(int fa, int &u, int l, int r, int x){ // 父版本指针&新版指针
        u = ++tot;
        lp[u] = lp[fa], rp[u] = rp[fa];
        cnt[u] = cnt[fa] + 1;
        
        if(l == r) return;

        int mid = l + r >> 1;
        if(x <= mid) insert(lp[fa], lp[u], l, mid, x);
        else insert(rp[fa], rp[u], mid + 1, r, x);
    }
    
    int kth(int u, int v,int l, int r, int k){
        if(l == r) return l;
        int x = cnt[lp[v]] - cnt[lp[u]]; // 左子数量
        int mid = l + r >> 1;
        if(k <= x) return kth(lp[u], lp[v], l, mid, k);
        else return kth(rp[u], rp[v], mid+1, r, k-x);
    }
};

void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for(int i=1; i<=n; i++) cin >> a[i];

    auto tmp = a;
    sort(tmp.begin() + 1, tmp.end());
    tmp.erase(unique(tmp.begin() + 1, tmp.end()), tmp.end());
    for(int i=1; i<=n; i++){
        a[i] = lower_bound(tmp.begin() + 1, tmp.end(), a[i]) - tmp.begin();
    }
    
    PresidentTree pt;
    pt.init(n);
    for(int i=1; i<=n; i++){ // 第 i 个版本插入了 ai
        pt.insert(pt.root[i-1], pt.root[i], 1, tmp.size()-1, a[i]);
    }
    for(int i=0; i<q; i++){
        int l, r, k;
        cin >> l >> r >> k;
        int idx = pt.kth(pt.root[l-1], pt.root[r], 1, tmp.size()-1, k);
        cout << tmp[idx] << '\n';
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}

K - The 4rd Ucup. Stage 2: Grand Prix of Paris

题意

一个数组 a，可以对 ai(ai > 1) 进行操作，每次操作使 ai − 1，最多操作 k 次。每次询问给定 l, r, k，求区间内进行最多 k 次操作后最小的乘积是多少。

(n ≤ 2e5, q ≤ 5e5, 1 ≤ ai ≤ 998244353, k ≤ 1e18)

解析

首先得到贪心思路，肯定是从小的数一直操作直到 1，可以用调整法证明。

对一个区间，进行操作后是在值域上让前缀都变成一。因此需要维护区间上的值域前缀信息，自然想到可持久化线段树。在值域上，用 prod 维护区间积，用 sum 维护最多可操作次数，在树上往下走即可。

走的逻辑是，如果左区间 sum ≤ k，说明可以将左区间的值都变为 1，k 变为 k-sum 后处理右区间，如果左区间 sum > k，那么说明右区间不会进行操作，直接将右区间的乘积乘到 ans 上，然后处理左区间。直到区间长度为一，特殊处理最后的那个值即可。

TRICK : 分别维护分子分母，而不是直接更新到 ans 上可以省去一个求逆元的 log

MYCODE

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int inf = 0x3f3f3f3f;
constexpr int mo = 998244353;

struct PresidentTree{
    int n, tot;
    vector<int> root, lp, rp, cnt;
    vector<int> ori;
    vector<ll> sum;
    vector<ll> prod;

    void init(int n_, auto vec){
        tot = 0;
        n = n_;
        root = vector<int>(n + 1);
        lp = rp = cnt = vector<int>(4*n + 17*n);
        sum = vector<ll>(4*n + 17*n);
        prod = vector<ll>(4*n + 17*n, 1);
        ori = vec;
    }
    
    void insert(int fa, int &u, int l, int r, int x){ // 父版本指针&新版指针
        u = ++tot;
        lp[u] = lp[fa], rp[u] = rp[fa];
        cnt[u] = cnt[fa] + 1;
        sum[u] = sum[fa] + ori[x]-1;
        prod[u] = prod[fa] * ori[x] % mo;

        if(l == r) return;

        int mid = l + r >> 1;
        if(x <= mid) insert(lp[fa], lp[u], l, mid, x);
        else insert(rp[fa], rp[u], mid + 1, r, x);
    }
    
    void work(int u, int v, int l, int r, ll k, auto& num, auto& den){
        if(l == r){
            if(cnt[u] < cnt[v]){ // 保证这个地方确实有值
                num *= max(1ll, ori[l] - k); // l==r 时, 也可能出现, 该值存在 & k > sum 的情况
                num %= mo;
            }
            return;
        }

        int mid = l + r >> 1;
        ll x = sum[lp[v]] - sum[lp[u]];
        if(x <= k){
            work(rp[u], rp[v], mid+1, r, k-x, num, den);
        }
        else{
            num *= prod[rp[v]], num %= mo;
            den *= prod[rp[u]], den %= mo;
            work(lp[u], lp[v], l, mid, k, num, den);
        }
    }
};

ll qpow(ll a, ll x){
    ll ans = 1;
    while(x){
        if(x & 1) ans *= a;
        a *= a;
        x >>= 1;

        a %= mo;
        ans %= mo;
    }
    return ans;
}
ll inv(int x){
    return qpow(x, mo - 2);    
}

void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }

    vector<int> ori(n + 1);
    vector<int> p(n + 1);
    iota(p.begin()+1, p.end(), 1);
    sort(p.begin()+1, p.end(), [&](int x, int y){
        return a[x] < a[y];
    });
    for(int i=1; i<=n; i++){
        ori[i] = a[p[i]];
        a[p[i]] = i;
    }
    
    PresidentTree pt;
    pt.init(n, ori);
    for(int i=1; i<=n; i++){
        pt.insert(pt.root[i-1], pt.root[i], 1, n, a[i]);
    }
    
    for(int i=1; i<=q; i++){
        ll num = 1, den = 1;
        int l, r;
        ll k;
        cin >> l >> r >> k;
        pt.work(pt.root[l-1], pt.root[r], 1, n, k, num, den);
        cout << num * inv(den) % mo << '\n';
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; //cin >> t;
    while(t--) solve();
    
    return 0;
}