时间分治

Posted on | In

cdq分治，也叫时间分治，核心概念就是对于若干个操作和查询，维护每次操作在哪个时间段中有效。

https://ac.nowcoder.com/acm/contest/888/E?&headNav=acm

这道题中的size就是时间，我们维护某个size区间上点的连通状况（用并查集维护），进行查询时进入某个点则连上这个点上的边，退出它时把并查集再复原。

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;
#define lson rt<<1
#define rson rt<<1|1
const int maxn=1e5+2;
int n,m;
int fa[maxn],h[maxn];
int fnd(int x){
    while(fa[x]!=x)
        x=fa[x];
    return x;
}
struct history{
    int x,y,preh;
};
vector<history> hs[maxn<<3];
int unite(int u,int v,int o){
    //在线段树的o点连上了uv边
    u=fnd(u);
    v=fnd(v);
    if(u==v)
        return 0;
    if(h[u]>h[v])
        swap(u,v);
    hs[o].push_back({u,v,h[v]});
    fa[u]=v;
    h[v]=max(h[u]+1,h[v]);
    return v;
}

void undo(int o){   //撤销线段树o点上的连边
    for(int i=0,x,y,preh;i<hs[o].size();i++){
        x=hs[o][i].x,y=hs[o][i].y,preh=hs[o][i].preh;
        fa[x]=x;h[y]=preh;
    }
    hs[o].clear();
}

struct node{
    int l,r;    //l..r分别代表以这个值开头的小区间，所以后面update时对于lr大区间添加的是l..r-1，这里存的r比实际区间右端点小1
    vector<int> es;
}tree[maxn<<3];

void build(int rt,int l,int r){ //build的意义是为每个节点设置管辖范围lr
    tree[rt].es.clear();
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
}

void update(int L,int R,int rt,int u,int v){
    if(L<=tree[rt].l&&R>=tree[rt].r){
        tree[rt].es.push_back(u);
        tree[rt].es.push_back(v);
        return ;
    }
    int mid=(tree[rt].l+tree[rt].r)>>1;
    if(L<=mid){
        update(L,R,lson,u,v);
    }
    if(R>mid){
        update(L,R,rson,u,v);
    }
}

int ans,val[maxn<<1];

void dfs(int rt){
    for(int i=0;i<tree[rt].es.size();i+=2){
        unite(tree[rt].es[i],tree[rt].es[i+1],rt);
    }
    /*
    if(tree[rt].l==tree[rt].r){
        ans+=(fnd(1)==fnd(n)?val[tree[rt].l+1]-val[tree[rt].l]:0);
    }else{
        dfs(lson);
        dfs(rson);
    }
    */
    //和上面两种写法均可，本题这种快一些
    if(fnd(1)==fnd(n)){ //优先判通，上面的是只在叶节点判断
        ans+=val[tree[rt].r+1]-val[tree[rt].l]; //这个点的贡献是r-l个小区间的长度和，离散化中应该经常用这种技巧来算区间贡献，
        //这里这么来是因为线段树兄弟节点的lr不可等（刚好大1）所以要求l和r的意义要等价，如果就填lr则前r-l个点代表区间左端点，后面的r是多余的，所以我们干脆让每个值代表它作为左端点的那个区间
    }else if(tree[rt].l!=tree[rt].r){
        dfs(lson);
        dfs(rson);
    }
    undo(rt);
}

int u[maxn],v[maxn],l[maxn],r[maxn];
int main(){
    cin>>n>>m;
    int tot=0;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>l[i]>>r[i];
    }
    for(int i=1;i<=m;i++){
        val[++tot]=l[i];
        val[++tot]=++r[i];
    }
    sort(val+1,val+tot+1);
    tot=unique(val+1,val+1+tot)-val-1;
    for(int i=1;i<=m;i++){
        l[i]=lower_bound(val+1,val+1+tot,l[i])-val;
        r[i]=lower_bound(val+1,val+1+tot,r[i])-val;
    }
    build(1,1,tot);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++){
        update(l[i],r[i]-1,1,u[i],v[i]);    //意思是uv这条边在l到r-1（每段区间以左端点来代表）的小区间内都有效，
    }
    dfs(1);
    cout<<ans<<endl;
}