操作树学习笔记

First Post:

Last Update:

Word Count:
2.9k

Read Time:
14 min

引入

有些题目有这样的特点：

  1. 允许离线
  2. 需要回退历史版本

这种情况下，我们可以离线所有操作，建立操作树，每个版本对应一个节点，其父亲就是其来源的版本。对于修改操作，回溯时回退即可。

当然，如果强制在线的话还是上可持久化数据结构吧。

例题

[HBCPC2024] Enchanted

第一次见到这个 trick 是在这个题。

不考虑操作树的话，剩下的和 Mark and Professor Koro 还是很像的。

对于这种两个相同的数合并成 +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
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e6+10,mod=1e9+7;
int n,m,seed,P,Q;	
int a[maxn],ans[maxn];
struct Query{
    int op,x,y,k;
}q[maxn];
struct BIT{
    #define lb(x) (x&(-x))
    int tr[maxn];
    inline void add(int x,int val){while(x<=n) tr[x]+=val,x+=lb(x);}
    inline int query(int x){int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
    #undef lb(x)
}b;
vector<int> g[maxn];
inline int rnd(){
    seed=(7*seed+13)%19260817;
    return seed;
}
inline void dfs(int u){
    int op=q[u].op,x=q[u].x,y=q[u].y,k=q[u].k;
    if(op==1){
        int res=b.query(y)-b.query(x-1);
        ans[u]=floor(__lg(res))+1;
    }
    if(op==2){
        int res=b.query(y)-b.query(x-1);
        res>>=(k-1);
        int bs=(1ll<<(k+1));
        while(res&1) ans[u]=(ans[u]+bs)%mod,bs<<=1,res>>=1;
    }
    if(op==3){
        b.add(x,(1ll<<(q[u].y-1))-(1ll<<(a[x]-1)));
        swap(a[x],q[u].y);
    }
    for(auto v:g[u]) dfs(v);
    if(op==3){
        b.add(x,(1ll<<(q[u].y-1))-(1ll<<(a[x]-1)));
        swap(a[x],q[u].y);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>seed>>P>>Q;
    for(re int i=1;i<=n;++i) a[i]=rnd()%Q+1,b.add(i,1ll<<(a[i]-1));
    for(re int i=1,op,x,y,k;i<=m;++i){
        op=rnd()%P+1;
        if(op==1){
            x=rnd()%n+1,y=rnd()%n+1;
            if(x>y) swap(x,y);
        }
        if(op==2){
            x=rnd()%n+1,y=rnd()%n+1,k=rnd()%Q+1;
            if(x>y) swap(x,y);
        }
        if(op==3) x=rnd()%n+1,y=rnd()%Q+1;
        if(op==4) x=rnd()%i;
        q[i]={op,x,y,k};
        op==4?g[x].push_back(i):g[i-1].push_back(i);
    }
    dfs(0);
    for(re int i=1;i<=m;++i) if(q[i].op==1||q[i].op==2) cout<<ans[i]<<'\n';
    return 0;
}

「TOCO Round 1」History

考虑建立操作树，操作三就解决了。

操作一是单点修改，比较简单。

考虑操作二如何实现。

看到相同深度想到 bfs 序，那么这些点事实上就是 的 级祖先的子树内和 在相同深度的点。

不难发现这些点的 bfs 序是连续的。

然后考虑怎么得到 级祖先的子树内和 在相同深度的点。

可以发现，这些点的 dfs 序也是连续的。

所以我们把所有和 在相同深度的点拿出来，然后二分找到 dfs 序在 的点，那么操作二就变成了区间查询。

别忘了把 级祖先的子树内和 在相同深度的点扣掉，因为这些点并不合法。

复杂度

有些细节，例如 可以不合法，而且还能为 0，都需要特判。

upd：这里写的麻烦了，没必要开 vector 把所有深度的所有点存下来，可能当时写的时候还没太懂。

我们求出每个深度对应的 bfs 序区间，然后把 bfs 序和 dfs 序对应起来。

这样在查某个深度的时候，只需要在 bfs序的区间上二分即可。

具体实现可以看[Cnoi2019] 雪松果树。

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
#include"bits/stdc++.h"
#define re register
#define int long long
#define lb(x) (x&(-x))
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e5+10;
int n,m,cnt,tim;
int a[maxn];
int head[maxn],ans[maxn];
int fa[maxn][18];
int c[maxn];
vector<int> g[maxn],Dep[maxn];
struct edge{
    int to,nxt;
}e[maxn<<1];
struct Query{
    int op,x,y;
}q[maxn];
struct node{
    int dfn,bfn,siz,dep,seq;
}t[maxn];
struct BIT{
    int tr[maxn];
    inline void add(int x,int val){++x;while(x<=n+1) tr[x]+=val,x+=lb(x);}
    inline int query(int x){++x;int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
}b;
inline void add(int u,int v){
    e[++cnt]={v,head[u]};
    head[u]=cnt;
}
inline void bfs(int s){
    queue<pii> q;
    q.push({s,1});
    while(!q.empty()){
        int u=q.front().fi,dep=q.front().se;
        q.pop();
        t[u].bfn=++tim,Dep[dep].push_back(t[u].dfn),t[u].dep=dep;
        for(re int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(!t[v].bfn) q.push({v,dep+1});
        }
    }
}
inline void dfs1(int u,int ft){
    t[u].siz=1;fa[u][0]=ft;
    t[u].dfn=++tim;t[tim].seq=u;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==ft) continue;
        dfs1(v,u);
        t[u].siz+=t[v].siz;
    }
}
inline void init(){
    for(re int j=1;j<=17;++j){
        for(re int u=1;u<=n;++u){
            fa[u][j]=fa[fa[u][j-1]][j-1];
        }
    }
}
inline int find(int u,int dep){
    for(re int i=17;i>=0;--i) if(dep>=(1ll<<i)) u=fa[u][i],dep-=(1ll<<i);
    return u;
}
inline void dfs(int u){
    int op=q[u].op,x=q[u].x,y=q[u].y;
    if(op==1) a[x]?b.add(t[x].bfn,-1):b.add(t[x].bfn,1),a[x]^=1;
    if(op==2&&!(y&1)){
        if(y==0) ans[u]=a[x];
        else{
            int fa=find(x,y/2),dep=t[x].dep;
            if(fa){
                int l=Dep[dep][lower_bound(Dep[dep].begin(),Dep[dep].end(),t[fa].dfn)-Dep[dep].begin()];
                int r=Dep[dep][upper_bound(Dep[dep].begin(),Dep[dep].end(),t[fa].dfn+t[fa].siz-1)-Dep[dep].begin()-1];
                l=t[l].seq,r=t[r].seq;
                ans[u]+=(b.query(t[r].bfn)-b.query(t[l].bfn-1));	
            }
            if(fa) fa=find(x,y/2-1);
            if(fa){
                int l=Dep[dep][lower_bound(Dep[dep].begin(),Dep[dep].end(),t[fa].dfn)-Dep[dep].begin()];
                int r=Dep[dep][upper_bound(Dep[dep].begin(),Dep[dep].end(),t[fa].dfn+t[fa].siz-1)-Dep[dep].begin()-1];
                l=t[l].seq,r=t[r].seq;
                ans[u]-=(b.query(t[r].bfn)-b.query(t[l].bfn-1));
            }	
        }
    }
    for(auto v:g[u]) dfs(v);
    if(op==1) a[x]?b.add(t[x].bfn,-1):b.add(t[x].bfn,1),a[x]^=1;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1,u,v;i<n;++i) cin>>u>>v,add(u,v),add(v,u);
    cin>>m;
    for(re int i=1;i<=m;++i){
        cin>>q[i].op>>q[i].x;
        if(q[i].op==2) cin>>q[i].y;
        q[i].op==3?g[q[i].x].push_back(i):g[i-1].push_back(i);
    }
    dfs1(1,0);tim=0;bfs(1);init();
    dfs(0);
    for(re int i=1;i<=m;++i) if(q[i].op==2) cout<<ans[i]<<'\n';
    return 0;
}

Persistent Bookcase *2200

建操作树后暴力 bitset 维护即可。

对一行取反可以先把一个全为 1 的 bitset 处理出来，然后异或这个 bitset 即可。

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
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e3+10,maxq=1e5+10;
int n,m,Q,now;
int ans[maxq];
bitset<maxn> a[maxn],A;
vector<int> g[maxq];
struct query{
    int op,x,y;
}q[maxq];
inline void dfs(int u){
    int op=q[u].op,x=q[u].x,y=q[u].y;
    bool sta=0;
    if(op==1){
        sta=a[x][y];
        if(!a[x][y]) ++now;
        a[x][y]=1;
    }
    if(op==2){
        sta=a[x][y];
        if(a[x][y]) --now;
        a[x][y]=0;
    }
    if(op==3){
        int res=a[x].count();
        a[x]^=A;
        now+=a[x].count()-res;
    }
    ans[u]=now;
    for(auto v:g[u]) dfs(v);
    if(op==1){
        if(!sta) --now;
        a[x][y]=sta;
    }
    if(op==2){
        if(sta) ++now;
        a[x][y]=sta;
    }
    if(op==3){
        int res=a[x].count();
        a[x]^=A;
        now+=a[x].count()-res;
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>Q;
    for(re int i=1;i<=m;++i) A[i]=1;
    for(re int i=1,op,x,y;i<=Q;++i){
        cin>>op;
        if(op==1||op==2) cin>>x>>y;
        else cin>>x;
        q[i]={op,x,y};
        op==4?g[x].push_back(i):g[i-1].push_back(i); 
    }
    dfs(0);
    for(re int i=1;i<=Q;++i) cout<<ans[i]<<'\n';
    return 0;
}

可持久化并查集

没有强制在线，所以考虑操作树。

维护个可撤销并查集就行了。

没写代码。

TTM - To the moon

没有强制在线，所以考虑操作树。

然后线段树维护就行了。

然而当初做这道题是为了学主席树如何区间修改（标记永久化）。

[Ynoi2014] 等这场战争结束之后

如果没有回撤，那么这是[HNOI2012] 永无乡，并查集+线段树合并即可。

那我暴力线段树合并+分裂行不行？不行，因为每次撤销都可以卡成 次分裂，那就寄了。

那我 LCT 上维护 set 行不行？不行，理由同上。

我们真的需要 LCT 维护这个东西吗？事实上不用，因为我们只关心连通性，所以可撤销并查集就足够了。

那 kth 怎么解决？线段树用不了了，那就值域分块！

我们对每个联通块维护所有整块的信息，合并时暴力合并。

查询也很简单，因为相当于查全局 kth，直接枚举每个整块，然后找到落在哪个块时就枚举这个块里的值。

枚举值的时候要判断这个值对应的点是否在联通块内，所以要给值和点对应一个关系（下面提到了）。

时间复杂度 ，空间复杂度 。

块长取 时最优。

时间复杂度 ，空间复杂度

代码倒是没有很难写，主要是卡空间卡的要死。

卡空间的一些技巧：

  1. 块长调大点
  2. 能开 short 的数组开 short
  3. 别用 vector 存图，用链式前向星
  4. 能不存的就别存，例如每个块的起始终点之类的

还有一些需要注意的点：

  1. 离散化时，相同的数不能视为一个，因为在查询时，我们查到一个整块的里面时，需要知道每个值对应的下标是否在当前连通块里，所以编号要注意。
  2. 别写 UB 或你弄不懂到底会怎么运行的代码。例如我参考的题解里写了一句 a[i]+=cnt[a[i]]++;，这东西你真能弄清吗。

因为一直卡不过去所以最后参考了题解，代码也跟题解差不多了，而且写的也很丑，所以不放代码了。

参考文章：

操作树学习笔记 - MYCui

≡