だから僕らは がんばって挑戦だよね

可持久化线段树 basic!

  • ~11.64K 字
  1. 1. 简介
  2. 2. 区间问题
    1. 2.1. 静态区间第 k 大
    2. 2.2. 带修区间第 k 大
  3. 3. 树上主席树
    1. 3.1. 板子
  4. 4. 异或/可持久化trie 相关
    1. 4.1. 平移后的异或问题

都是典中典，我之前还不是很会。

简介

对于一颗正常的线段树，如果要支持所有版本都既可以访问又可以修改（完全可持久化），对于每个版本保存一颗线段树是不可接受的。

发现每次修改操作修改的点的个数只有 log⁡n\log n 个，于是通过记录根节点保存插入后修改的节点和未修改的节点，就可以实现可持久化。

区间问题

大概就是两个区间范围限制，一个用值域搞掉，一个用根节点搞掉。

静态区间第 k 大

考虑全局第 k 大怎么用线段树做，对值域建线段树，然后在线段树上二分。如果问题为求 [1,r][1,r] 的第 k 大，那么找到插入 rr 时的版本就行了。

回到原问题，发现我们统计的信息是前缀和，在二分时将 [1,l−1][1,l-1] 和 [1,r][1,r] 的相减就行了。

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
int a[N];
int n,q;

class persistent_segtree{
    private:
        class tree{
            public:
                int l,r,c;
        }tr[N<<5];
        int idx;
    public:
        int rt[N];
        void build(int &u,int l,int r){
            u = ++idx;
            if(l==r)
                return;
            int mid = (l+r)>>1;
            build(tr[u].l,l,mid);
            build(tr[u].r,mid+1,r);
        }
        void modify(int u,int &v,int l,int r,int x,int c){
            v = ++idx,tr[v] = tr[u];
            tr[v].c += c;
            if(l==r)
                return;
            int mid = (l+r)>>1;
            if(x<=mid)
                modify(tr[u].l,tr[v].l,l,mid,x,c);
            else
                modify(tr[u].r,tr[v].r,mid+1,r,x,c);
        }
        int query_Kth(int u,int v,int l,int r,int K){
            if(l==r)
                return l;
            int mid = (l+r)>>1,c = tr[tr[v].l].c-tr[tr[u].l].c;
            if(c>=K)
                return query_Kth(tr[u].l,tr[v].l,l,mid,K);
            return query_Kth(tr[u].r,tr[v].r,mid+1,r,K-c);
        }
}tr;

vector<int> ha;
inline int h(int x){
    return lower_bound(ha.begin(),ha.end(),x)-ha.begin()+1;
}

int main(){
    n = in(),q = in();
    for(int k=1;k<=n;k++)
        ha.push_back(a[k]=in());
    sort(ha.begin(),ha.end());
    ha.erase(unique(ha.begin(),ha.end()),ha.end());
    int m = ha.size();
    tr.build(tr.rt[0],1,m);
    for(int k=1;k<=n;k++){
        int x = h(a[k]);
        tr.modify(tr.rt[k-1],tr.rt[k],1,m,x,1);
    }
    while(q--){
        int l = in(),r = in(),K = in();
        out(ha[tr.query_Kth(tr.rt[l-1],tr.rt[r],1,m,K)-1]);
        putchar('\n');
    }
    return 0;
}

带修区间第 k 大

和静态一样，利用前缀和的性质。暴力修改前缀和是不可接受的，考虑用树状数组维护主席树的根节点，每次取出树状数组的 log⁡n\log n 个节点计算前缀和即可。

时间复杂度 O(nlog⁡2n)O(n \log^2 n)，空间 O(nlog⁡n)O(n \log n)。

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
class persistent_segtree{
    private:
        class tree{
            public:
                int l,r,c;
        }tr[N<<6];
        int idx;

        inline void pushup(int x){tr[x].c = tr[tr[x].l].c+tr[tr[x].r].c;}
    public:
        int rt[N];

        void modife(int u,int &v,int l,int r,int x,int c){
            if(!v)v = ++idx;
            tr[v] = tr[u];
            if(l==r){
                tr[v].c += c;
                return;
            }
            int mid = (l+r)>>1;
            if(x<=mid)
                modife(tr[u].l,tr[v].l,l,mid,x,c);
            else
                modife(tr[u].r,tr[v].r,mid+1,r,x,c);
            pushup(v);
        }

        int query(vector<int> lp,vector<int> rp,int l,int r,int c){
            if(l==r)
                return l;
            int mid = (l+r)>>1,sum = 0;
            for(auto x:rp)
                sum += tr[tr[x].l].c;
            for(auto x:lp)
                sum -= tr[tr[x].l].c;
            if(c<=sum){
                for(auto &x:lp)
                    x = tr[x].l;
                for(auto &x:rp)
                    x = tr[x].l;
                return query(lp,rp,l,mid,c);
            }
            for(auto &x:lp)
                x = tr[x].r;
            for(auto &x:rp)
                x = tr[x].r;
            return query(lp,rp,mid+1,r,c-sum);
        }
}tr;
class inquiry{
    public:
        int l,r,k;
};
vector<inquiry> qus;
int a[N];
int n,m,q;

vector<int> ha;
inline int h(int x){return lower_bound(ha.begin(),ha.end(),x)-ha.begin()+1;}

inline void modife(int y,int c,bool del=true){
    if(del){
        for(int x=y;x<=n;x+=x&-x)
            tr.modife(tr.rt[x],tr.rt[x],1,m,a[y],-1);
    }
    a[y] = c;
    for(int x=y;x<=n;x+=x&-x)
        tr.modife(tr.rt[x],tr.rt[x],1,m,a[y],1);
}

inline int query(int l,int r,int c){
    vector<int> lp,rp;
    if(l>1)
        for(int x=l-1;x;x&=x-1)
            lp.push_back(tr.rt[x]);
    for(int x=r;x;x&=x-1)
        rp.push_back(tr.rt[x]);
    return tr.query(lp,rp,1,m,c);
}

int main(){
    n = in(),q = in();
    for(int k=1;k<=n;k++)
        ha.push_back(a[k]=in());
    for(int k=1;k<=q;k++){
        char ops = getchar();
        while(ops!='Q'&&ops!='C')
            ops = getchar();
        if(ops=='Q'){
            int l = in(),r = in(),c = in();
            qus.push_back({l,r,c});
            ha.push_back(c);
        }
        else{
            int x = in(),c = in();
            qus.push_back({x,0,c});
            ha.push_back(c);
        }
    }
    sort(ha.begin(),ha.end());
    ha.erase(unique(ha.begin(),ha.end()),ha.end());
    m = ha.size();
    for(int k=1;k<=n;k++)
        modife(k,a[k]=h(a[k]),false);
    for(auto [l,r,c]:qus){
        if(r){
            out(ha[query(l,r,c)-1]);
            putchar('\n');
        }
        else
            modife(l,h(c));
    }
    return 0;
}

树上主席树

板子

在树上用主席树做一个前缀和的东西，和区间类似，拿着 x,y,lca(x,y),fa(lca(x,y))x,y,lca(x,y),fa(lca(x,y)) 去二分即可。

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
int fa[N],siz[N],dep[N],son[N],top[N],idx;
vector<int> g[N];
int w[N];
int n,m,q;

class persistent_segtree{
    private:
        class starwish{
            public:
                int l,r,c;
        }tr[N<<8];
        int idx;
    public:
        int rt[N];
        void build(int &u,int l,int r){
            u = ++idx;
            if(l==r)
                return;
            int mid = (l+r)>>1;
            build(tr[u].l,l,mid);
            build(tr[u].r,mid+1,r);
        }

        void modify(int u,int &v,int l,int r,int x,int c){
            v = ++idx,tr[v] = tr[u];
            tr[v].c += c;
            if(l==r)
                return;
            int mid = (l+r)>>1;
            if(x<=mid)
                modify(tr[u].l,tr[v].l,l,mid,x,c);
            else
                modify(tr[u].r,tr[v].r,mid+1,r,x,c);
        }

        int Kth(int a,int b,int c,int d,int l,int r,int K){
            if(l==r)
                return l;
            int mid = (l+r)>>1,w = tr[tr[a].l].c+tr[tr[b].l].c-tr[tr[c].l].c-tr[tr[d].l].c;
            if(w>=K)
                return Kth(tr[a].l,tr[b].l,tr[c].l,tr[d].l,l,mid,K);
            return Kth(tr[a].r,tr[b].r,tr[c].r,tr[d].r,mid+1,r,K-w);
        }
}tr;

void dfs1(int u){
    siz[u]++;
    for(auto v:g[u]){
        if(v==fa[u])
            continue;
        fa[v] = u;
        dep[v] = dep[u]+1;
        dfs1(v);
        siz[u] += siz[v];
        if(siz[v]>siz[son[u]])
            son[u] = v;
    }
}

void dfs2(int u,int tp){
    top[u] = tp;
    if(son[u])
        dfs2(son[u],tp);
    for(auto v:g[u]){
        if(v==fa[u]||v==son[u])
            continue;
        dfs2(v,v);
    }
}

inline int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x = fa[top[x]];
    }
    if(dep[x]<dep[y])
        swap(x,y);
    return y;
}

vector<int> ha;
inline int h(int x){
    return lower_bound(ha.begin(),ha.end(),x)-ha.begin()+1;
}

void dfs3(int u){
    tr.modify(tr.rt[fa[u]],tr.rt[u],1,m,h(w[u]),1);
    for(auto v:g[u]){
        if(v==fa[u])
            continue;
        dfs3(v);
    }
}

int main(){
    n = in(),q = in();
    for(int k=1;k<=n;k++)
        ha.push_back(w[k]=in());
    sort(ha.begin(),ha.end());
    ha.erase(unique(ha.begin(),ha.end()),ha.end());
    m = ha.size();
    for(int k=1;k<n;k++){
        int a = in(),b = in();
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs1(1);
    dfs2(1,1);
    tr.build(tr.rt[0],1,m);
    dfs3(1);
    int lastans = 0;
    while(q--){
        int x = in()^lastans,y = in(),K = in();
        int d = lca(x,y);
        out(lastans=ha[tr.Kth(tr.rt[x],tr.rt[y],tr.rt[d],tr.rt[fa[d]],1,m,K)-1]);
        putchar('\n');
    }
    return 0;
}

异或/可持久化trie 相关

平移后的异或问题

其实就是区间操作的典题，不过用了可持久化 trie 的思想。

从高到底枚举 bb 的第 ii 位，如果区间内存在 [b+2ci xor1−x,b+2ci xor1−x+2k−1][b+2^{c_i \ xor 1}-x,b+2^{c_i \ xor 1}-x+2^k-1] 之间的数，那么 b xor(a+x)b \ xor (a+x) 的这一位可以为 11，因为这个区间里的数加 xx 后第 ii 位都是 ci xor1c_i \ xor 1。

可持久化 trie 是个和可持久化线段树差不多的东西。

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
class persistent_segtree{
    private:
        class tree{
            public:
                int l,r,c;
        }tr[N<<5];
        int rt[N],idx;

        inline void pushup(int x){tr[x].c = tr[tr[x].l].c+tr[tr[x].r].c;}
    public:
        inline int& operator [] (const int &x){return rt[x];}

        void build(int &u,int l,int r){
            u = ++idx;
            if(l==r)
                return;
            int mid = (l+r)>>1;
            build(tr[u].l,l,mid);
            build(tr[u].r,mid+1,r);
        }

        void modife(int u,int &v,int l,int r,int x,int c){
            v=++idx;
            tr[v] = tr[u];
            if(l==r){
                tr[v].c += c;
                return;
            }
            int mid = (l+r)>>1;
            if(x<=mid)
                modife(tr[u].l,tr[v].l,l,mid,x,c);
            else
                modife(tr[u].r,tr[v].r,mid+1,r,x,c);
            pushup(v);
        }

        int query(int u,int v,int l,int r,int L,int R){
            if(l>=L&&r<=R)
                return tr[v].c-tr[u].c;
            int mid = (l+r)>>1,ans = 0;
            if(L<=mid)
                ans += query(tr[u].l,tr[v].l,l,mid,L,R);
            if(R>mid)
                ans += query(tr[u].r,tr[v].r,mid+1,r,L,R);
            return ans;
        }
}tr;
int a[N];
int n,m;

inline bool query(int u,int v,int l,int r,int L,int R){
    L = max(l,L),R = min(r,R);
    if(L>R)
        return false;
    return tr.query(u,v,l,r,L,R);
}

int main(){
    n = in(),m = in();
    int v = 0;
    for(int k=1;k<=n;k++)
        v = max(v,a[k]=in());
    tr.build(tr[0],0,v);
    for(int k=1;k<=n;k++)
        tr.modife(tr[k-1],tr[k],0,v,a[k],1);
    while(m--){
        int b = in(),x = in(),l = in(),r = in(),ans = 0;
        for(int k=C;~k;k--){
            int tmp = ans+((((b>>k)&1)^1)<<k);
            if(query(tr[l-1],tr[r],0,v,tmp-x,tmp-x+(1<<k)-1))
                ans = tmp;
            else
                ans += ((b>>k)&1)<<k;
        }
        out(ans^b);
        putchar('\n');
    }
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可