数据结构听课笔记

降维方法

TEST_73

对于一个森林，连通块的数量为点的数量减去边的数量。点的数量为 r−l+1r-l+1，考虑哪些边是存在于森林中的边。需要满足 3 个条件：

  • l≤a≤rl\le a\le r；
  • l≤b≤rl\le b\le r；
  • l≤id≤rl\le id\le r。

发现是三维数点，考虑优化。注意到这个限制与普通的三维数点的限制区别在于各个维度询问区间的 l,rl,r 都一样，则我们可以将其优化为二维数点：

  • l≤min⁡(a,b,id)≤rl\le \min(a,b,id)\le r；
  • l≤max⁡(a,b,id)≤rl\le \max(a,b,id)\le r。

类似地，满足此条件的 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
#include<iostream>
#include<algorithm>
using namespace std;
constexpr int N=1e6+10;
int n,m;
struct edge{
    int minn,maxn;
    inline bool operator<(const edge &a)const{return minn<a.minn;}
}e[N];
struct node{
    int x,l,r,id,k;
    inline bool operator<(const node &a)const{return x<a.x;}
}b[N<<1];
int tot,ans[N],tree[N];
#define lowbit(x) (x&-x)
inline void modify(int x){
    for(;x<=n;x+=lowbit(x)) ++tree[x];
}
inline int query(int x){
    int res=0;
    for(;x;x^=lowbit(x)) res+=tree[x];
    return res;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        e[i].minn=min({x,y,i});
        e[i].maxn=max({x,y,i});
    }
    sort(e+1,e+n);
    for(int i=1,l,r;i<=m;i++){
        cin>>l>>r;
        ans[i]=r-l+1;
        b[++tot]={r,l,r,i,1};
        if(l>1) b[++tot]={l-1,l,r,i,-1};
    }
    sort(b+1,b+1+tot);
    for(int i=1,j=1;i<n;i++){
        while(j<=tot&&b[j].x<e[i].minn){
            ans[b[j].id]-=(query(b[j].r)-query(b[j].l-1))*b[j].k;
            ++j;
        }
        modify(e[i].maxn);
        while(i==n-1&&j<=tot){
            ans[b[j].id]-=(query(b[j].r)-query(b[j].l-1))*b[j].k;
            ++j;
        }
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}

树上问题

dfs 序是帮助解决树上问题的有力工具。
树有时候有比序列更好的性质，不能直接认为树上问题严格强于序列问题。

树

如果不换根可以直接树剖线段树做，考虑换根后 rootroot 和 xx 的关系（以下的“uu 的子树”指以 11 为整棵树的根时 uu 为根的子树）：

  • 若 root=xroot=x，直接输出全局最小值；
  • 若 rootroot 在 xx 的子树中，设 yy 为 xx 向 rootroot 方向的儿子（以 11 为根），则答案为整棵树去除 yy 的子树部分后的最小值；
  • 否则答案与 root=1root=1 时相同。

只需求 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
#include<iostream>
#include<vector>
using namespace std;
constexpr int N=1e5+10,inf=2e9;
int n,q,fa[N],a[N];
vector<int> e[N];
int siz[N],son[N],dep[N];
void dfs1(int u){
    siz[u]=1;
    dep[u]=dep[fa[u]]+1;
    for(int v:e[u]){
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
int dfn[N],dfncnt,idfn[N],top[N],tree[N*3],P;
void dfs2(int u,int topf){
    dfn[u]=++dfncnt;
    idfn[dfncnt]=u;
    tree[P+dfncnt]=a[u];
    top[u]=topf;
    if(son[u]) dfs2(son[u],topf);
    for(int v:e[u]){
        if(v==son[u]) continue;
        dfs2(v,v);
    }
}
#define ls(u) (u<<1)
#define rs(u) (u<<1|1)
char op;
int x,y,root;
inline void modify(int x,int k){
    x+=P;tree[x]=k;
    for(x>>=1;x;x>>=1) tree[x]=min(tree[ls(x)],tree[rs(x)]);
}
inline int query(int l,int r){
    if(l>r) return inf;
    l+=P-1,r+=P+1;
    int res=inf;
    while(l^1^r){
        if(~l&1) res=min(res,tree[l^1]);
        if(r&1) res=min(res,tree[r^1]);
        l>>=1,r>>=1;
    }
    return res;
}
inline int kth(int x,int k){
    while(k>=dep[x]-dep[fa[top[x]]]){
        k-=dep[x]-dep[fa[top[x]]];
        x=fa[top[x]];
    }
    return idfn[dfn[x]-k];
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    P=1;while(P<=n+1) P<<=1;
    for(int i=1;i<=n;i++){
        cin>>fa[i]>>a[i];
        e[fa[i]].push_back(i);
    }
    dfs1(1);
    for(int i=1;i<=P+n+1;i++) tree[i]=inf;
    dfs2(1,1);
    for(int i=P-1;i;i--)
        if(rs(i)<=P+n+1) tree[i]=min(tree[ls(i)],tree[rs(i)]);
    root=1;
    while(q--){
        cin>>op;
        if(op=='V'){
            cin>>x>>y;
            modify(dfn[x],y);
        }
        else if(op=='E') cin>>root;
        else{
            cin>>x;
            if(x==root) cout<<query(1,n)<<'\n';
            else if(dfn[root]>=dfn[x]&&dfn[root]<=dfn[x]+siz[x]-1){
                int diff=dep[root]-dfn[x];
                int res=inf,s=kth(root,diff-1);
                res=min(res,query(1,dfn[s]-1));
                res=min(res,query(dfn[s]+siz[s],n));
                cout<<res<<'\n';
            }
            else cout<<query(dfn[x],dfn[x]+siz[x]-1)<<'\n';
        }
    }
    return 0;
}

Company

从 [l,r][l,r] 中删去一个点使得剩余 r−lr-l 个点的 LCA 深度最大。将 [l,r][l,r] 中的点按照 dfn 排序，删去的点必然是第一个点或最后一个点，ST 表求区间 LCA 即可。

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
#include<iostream>
#include<vector>
using namespace std;
constexpr int N=1e5+10;
int n,q;
vector<int> e[N];
int fa[N],siz[N],son[N],dep[N];
void dfs1(int u){
    siz[u]=1;
    dep[u]=dep[fa[u]]+1;
    for(int v:e[u]){
        dfs1(v);
        siz[u]+=siz[u];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
int top[N],dfn[N],dfncnt;
void dfs2(int u,int topf){
    top[u]=topf;
    dfn[u]=++dfncnt;
    if(son[u]) dfs2(son[u],topf);
    for(int v:e[u]){
        if(v==son[u]) continue;
        dfs2(v,v);
    }
}
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]];
    }
    return dep[x]<dep[y]?x:y;
}
int st[17][N],minn[17][N],maxn[17][N],l,r;
int querymin(int l,int r){
    int lg=__lg(r-l+1);
    if(dfn[minn[lg][l]]<dfn[minn[lg][r-(1<<lg)+1]]) return minn[lg][l];
    return minn[lg][r-(1<<lg)+1];
}
int querymax(int l,int r){
    int lg=__lg(r-l+1);
    if(dfn[maxn[lg][l]]>dfn[maxn[lg][r-(1<<lg)+1]]) return maxn[lg][l];
    return maxn[lg][r-(1<<lg)+1];
}
int querylca(int l,int r){
    int lg=__lg(r-l+1);
    return lca(st[lg][l],st[lg][r-(1<<lg)+1]);
}
int getlca(int l,int r,int del){
    if(del==l) return querylca(l+1,r);
    if(del==r) return querylca(l,r-1);
    return lca(querylca(l,del-1),querylca(del+1,r));
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=2;i<=n;i++){
        cin>>fa[i];
        e[fa[i]].push_back(i);
    }
    dep[0]=-1;
    dfs1(1);
    dfs2(1,1);
    for(int i=1;i<=n;i++) st[0][i]=minn[0][i]=maxn[0][i]=i;
    for(int i=1;i<=__lg(n);i++)
        for(int j=1;j+(1<<i)-1<=n;j++){
            st[i][j]=lca(st[i-1][j],st[i-1][j+(1<<(i-1))]);
            if(dfn[minn[i-1][j]]<dfn[minn[i-1][j+(1<<(i-1))]])
                minn[i][j]=minn[i-1][j];
            else minn[i][j]=minn[i-1][j+(1<<(i-1))];
            if(dfn[maxn[i-1][j]]>dfn[maxn[i-1][j+(1<<(i-1))]])
                maxn[i][j]=maxn[i-1][j];
            else maxn[i][j]=maxn[i-1][j+(1<<(i-1))];
        }
    while(q--){
        cin>>l>>r;
        int minx=querymin(l,r),maxx=querymax(l,r);
        int lcamin=getlca(l,r,minx),lcamax=getlca(l,r,maxx);
        if(dep[lcamin]>dep[lcamax]) cout<<minx<<' '<<dep[lcamin]<<'\n';
        else cout<<maxx<<' '<<dep[lcamax]<<'\n';
    }
    return 0;
}

[Ynoi Easy Round 2021] TEST_68

首先找出全局最大异或对，设这两个点为 u,vu,v，则 u,vu,v 的根链的并以外的点的答案都是全局最大异或对，而此时问题就转化成了一条路径上的问题，直接暴力求解即可。这里体现了支配的思想。

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
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
constexpr int N=5e5+10;
int n,nxt[N*62][2],ed[N*62],tot;
void insert(ll x,int id){
    int p=0;
    for(int i=60;i>=0;i--){
        int c=x>>i&1;
        if(!nxt[p][c]) nxt[p][c]=++tot;
        p=nxt[p][c];
    }
    ed[p]=id;
}
int find(ll x){
    int p=0;
    for(int i=60;i>=0;i--){
        int c=x>>i&1;
        if(nxt[p][c^1]) p=nxt[p][c^1];
        else p=nxt[p][c];
    }
    return ed[p];
}
void clear(){
    for(int i=0;i<=tot;i++) nxt[i][0]=nxt[i][1]=ed[i]=0;
    tot=0;
}
vector<int> e[N];
int fa[N],idx,idy;
ll a[N],maxn,ans[N];
bool flag[N];
void dfs(int u){
    if(flag[u]) ans[u]=maxn;
    insert(a[u],u);
    maxn=max(maxn,a[u]^a[find(a[u])]);
    int son=0;
    for(int v:e[u])
        if(!flag[v]) dfs(v);
        else son=v;
    if(son) dfs(son);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++) cin>>fa[i],e[fa[i]].push_back(i);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        int x=find(a[i]);
        insert(a[i],i);
        if((a[x]^a[i])>maxn){
            maxn=a[x]^a[i];
            idx=i,idy=x;
        }
    }
    for(int i=1;i<=n;i++) ans[i]=maxn;
    clear();
    while(idx) flag[idx]=1,ans[idx]=0,idx=fa[idx];
    maxn=0;
    dfs(1);
    clear();
    memset(flag,0,sizeof(bool)*(n+10));
    while(idy) flag[idy]=1,ans[idy]=0,idy=fa[idy];
    maxn=0;
    dfs(1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
    return 0;
}

『MdOI R1』Path

将路径异或通过根链差分转换为两点异或。要想使得路径上的点不交，只需在一个子树内选取两个点，再从子树外选取两个点，异或后加起来即为答案，子树外选点同上一道题，子树内选点可以用 dsu on tree。

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
#include<iostream>
#include<vector>
#include<cstring>
#include<cassert>
using namespace std;
constexpr int N=3e4+10,inf=2e9;
int n,a[N];
struct edge{int v,w;};
vector<edge> e[N];
struct Trie{
    int nxt[N*30][2],siz[N*30],ed[N*30],tot;
    inline void insert(int x,int id){
        int p=0;
        for(int i=29;i>=0;i--){
            int c=x>>i&1;
            if(!nxt[p][c]) nxt[p][c]=++tot;
            p=nxt[p][c];
            ++siz[p];
        }
        ed[p]=id;
    }
    inline void del(int x){
        int p=0;
        for(int i=29;i>=0;i--){
            int c=x>>i&1;
            p=nxt[p][c];
            --siz[p];
        }
    }
    inline int query(int x){
        int p=0;
        for(int i=29;i>=0;i--){
            int c=x>>i&1;
            if(siz[nxt[p][c^1]]) p=nxt[p][c^1];
            else p=nxt[p][c];
        }
        return ed[p];
    }
    void clear(){
        for(int i=0;i<=tot;i++) nxt[i][0]=nxt[i][1]=siz[i]=ed[i]=0;
        tot=0;
    }
}trie;
int maxin[N],maxout[N],fa[N];
int dfn[N],dfncnt,siz[N],idfn[N],son[N];
void dfs1(int u,int f){
    fa[u]=f;
    dfn[u]=++dfncnt;
    idfn[dfncnt]=u;
    siz[u]=1;
    for(auto [v,w]:e[u]){
        if(v==f) continue;
        a[v]=a[u]^w;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
bool flag[N];
int idx,idy,maxn;
void dfs2(int u,int f){
    if(flag[u]) maxout[u]=maxn;
    trie.insert(a[u],u);
    maxn=max(maxn,a[u]^a[trie.query(a[u])]);
    int son=0;
    for(auto [v,w]:e[u]){
        if(v==f) continue;
        if(!flag[v]) dfs2(v,u);
        else son=v;
    }
    if(son) dfs2(son,u);
}
void dfs3(int u,bool keep){
    for(auto [v,w]:e[u]){
        if(v==fa[u]||v==son[u]) continue;
        dfs3(v,0);
    }
    if(son[u]) dfs3(son[u],1),maxin[u]=maxin[son[u]];
    for(auto [v,w]:e[u]){
        if(v==fa[u]||v==son[u]) continue;
        for(int i=dfn[v];i<dfn[v]+siz[v];i++){
            trie.insert(a[idfn[i]],idfn[i]);
            maxin[u]=max(maxin[u],a[idfn[i]]^a[trie.query(a[idfn[i]])]);
        }
    }
    trie.insert(a[u],u);
    maxin[u]=max(maxin[u],a[u]^a[trie.query(a[u])]);
    if(!keep) for(int i=dfn[u];i<dfn[u]+siz[u];i++) trie.del(a[idfn[i]]);
}
int ans;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,u,v,w;i<n;i++){
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    dfs1(1,0);
    for(int i=1;i<=n;i++){
        trie.insert(a[i],i);
        int x=trie.query(a[i]);
        if((a[x]^a[i])>maxn){
            maxn=a[x]^a[i];
            idx=i,idy=x;
        }
    }
    for(int i=1;i<=n;i++) maxout[i]=maxn;
    trie.clear();
    while(idx) flag[idx]=1,maxout[idx]=0,idx=fa[idx];
    maxn=0;
    dfs2(1,0);
    trie.clear();
    memset(flag,0,sizeof(bool)*(n+10));
    while(idy) flag[idy]=1,maxout[idy]=0,idy=fa[idy];
    maxn=0;
    dfs2(1,0);
    trie.clear();
    dfs3(1,0);
    for(int i=2;i<=n;i++) ans=max(ans,maxin[i]+maxout[i]);
    cout<<ans<<'\n';
    return 0;
}

bitset

[JSOI2015] 最小表示

一个边 u,vu,v 能被删去当且仅当存在 uu 到 xx 和 xx 到 vv 的路径。那么在正反图上都求一遍可达性就可以判断。
一般认为 DAG 可达性问题复杂度最优 O(nmw)O\left(\dfrac{nm}{w}\right)（理论上矩阵乘法可以做到 O(nω)O(n^{\omega})，但是因常数和实现难度问题难以在实际中应用）。

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
#include<iostream>
#include<bitset>
#include<vector>
#include<queue>
using namespace std;
constexpr int N=3e4+10,M=1e5+10;
int n,m,indeg1[N],indeg2[N],u[M],v[M],ans;
bitset<N> f[N],g[N];
vector<int> e1[N],e2[N];
queue<int> q;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i];
        e1[v[i]].push_back(u[i]);
        ++indeg1[u[i]];
        e2[u[i]].push_back(v[i]);
        ++indeg2[v[i]];
    }
    for(int i=1;i<=n;i++) if(!indeg1[i]) q.push(i);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:e1[u]){
            f[v]|=f[u];
            f[v].set(u);
            if(!--indeg1[v]) q.push(v);
        }
    }
    for(int i=1;i<=n;i++) if(!indeg2[i]) q.push(i);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:e2[u]){
            g[v]|=g[u];
            g[v].set(u);
            if(!--indeg2[v]) q.push(v);
        }
    }
    for(int i=1;i<=m;i++)
        if((f[u[i]]&g[v[i]]).any()) ++ans;
    cout<<ans<<'\n';
    return 0;
}

重构树

[IOI 2018] werewolf 狼人

建两棵重构树，求叶子节点的交集，转化为二维数点问题。

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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
constexpr int N=2e5+10,M=4e5+10;
int n,m,q;
struct edge{int u,v;}a[M];
inline bool cmp1(const edge &x,const edge &y){
    return max(x.u,x.v)<max(y.u,y.v);
}
inline bool cmp2(const edge &x,const edge &y){
    return min(x.u,x.v)>min(y.u,y.v);
}
int boss[N<<1],tot1,tot2;
int find(int x){return boss[x]==x?x:boss[x]=find(boss[x]);}
int fa1[19][N<<1],fa2[19][N<<1];
int val1[N<<1],val2[N<<1];
vector<int> e1[N<<1],e2[N<<1];
int dfn1[N<<1],dfn2[N<<1],dfncnt,siz1[N<<1],siz2[N<<1],idfn2[N<<1];
void dfs1(int u){
    dfn1[u]=++dfncnt;
    siz1[u]=1;
    for(int v:e1[u]){
        dfs1(v);
        siz1[u]+=siz1[v];
    }
}
void dfs2(int u){
    dfn2[u]=++dfncnt;
    idfn2[dfncnt]=u;
    siz2[u]=1;
    for(int v:e2[u]){
        dfs2(v);
        siz2[u]+=siz2[v];
    }
}
int tot;
struct ask{
    int x,l,r,id,k;
    inline bool operator<(const ask &a)const{return x<a.x;}
}b[N<<1];
#define lowbit(x) (x&-x)
int tree[N<<1],cnt[N];
void modify(int x){
    for(;x<=tot1;x+=lowbit(x)) ++tree[x];
}
int query(int x){
    int res=0;
    for(;x;x^=lowbit(x)) res+=tree[x];
    return res;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v;
        ++a[i].u,++a[i].v;
    }
    sort(a+1,a+1+m,cmp1);
    tot1=n;
    for(int i=1;i<=n*2;i++) boss[i]=i;
    for(int i=1;i<=n;i++) val1[i]=i;
    for(int i=1;i<=m;i++){
        int x=find(a[i].u),y=find(a[i].v);
        if(x==y) continue;
        boss[x]=boss[y]=++tot1;
        e1[tot1].push_back(x),e1[tot1].push_back(y);
        val1[tot1]=max(a[i].u,a[i].v);
        fa1[0][x]=fa1[0][y]=fa1[0][tot1]=tot1;
    }
    dfncnt=0;
    dfs1(tot1);
    for(int i=1;i<=__lg(tot1);i++)
        for(int j=1;j<=tot1;j++)
            fa1[i][j]=fa1[i-1][fa1[i-1][j]];
    sort(a+1,a+1+m,cmp2);
    tot2=n;
    for(int i=1;i<=n*2;i++) boss[i]=i;
    for(int i=1;i<=n;i++) val2[i]=i;
    for(int i=1;i<=m;i++){
        int x=find(a[i].u),y=find(a[i].v);
        if(x==y) continue;
        boss[x]=boss[y]=++tot2;
        e2[tot2].push_back(x),e2[tot2].push_back(y);
        val2[tot2]=min(a[i].u,a[i].v);
        fa2[0][x]=fa2[0][y]=fa2[0][tot2]=tot2;
    }
    dfncnt=0;
    dfs2(tot2);
    for(int i=1;i<=__lg(tot2);i++)
        for(int j=1;j<=tot2;j++)
            fa2[i][j]=fa2[i-1][fa2[i-1][j]];
    for(int i=1,s,t,l,r;i<=q;i++){
        cin>>s>>t>>l>>r;
        ++s,++t,++l,++r;
        for(int j=__lg(tot1);j>=0;j--)
            if(val1[fa1[j][t]]<=r) t=fa1[j][t];
        for(int j=__lg(tot2);j>=0;j--)
            if(val2[fa2[j][s]]>=l) s=fa2[j][s];
        if(dfn2[s]>1) b[++tot]={dfn2[s]-1,dfn1[t],dfn1[t]+siz1[t]-1,i,-1};
        b[++tot]={dfn2[s]+siz2[s]-1,dfn1[t],dfn1[t]+siz1[t]-1,i,1};
    }
    sort(b+1,b+1+tot);
    for(int i=1,j=1;i<=tot2;i++){
        if(idfn2[i]<=n) modify(dfn1[idfn2[i]]);
        while(j<=tot&&b[j].x<=i){
            cnt[b[j].id]+=b[j].k*(query(b[j].r)-query(b[j].l-1));
            ++j;
        }
    }
    for(int i=1;i<=q;i++) cout<<(cnt[i]?"1\n":"0\n");
    return 0;
}
OI
#数据结构
数据结构听课笔记
https://headless-piston.github.io/2025/11/17/数据结构听课笔记/
作者
headless-piston
发布于
2025年11月17日
许可协议