「CF1140F」Extending Set of Points

发表于 更新于 分类于

题目链接：https://codeforces.com/problemset/problem/1140/F。

线段树分治，早就听过了，第一次写。。

首先有个转化，就是说对于一个在集合里的点$(x,y)$，就把$x$行向$y$列连一条边，那么答案就是每个连通块的行数乘列数之和，证明显然。

那么现在的问题就是，怎么处理边的删除。

注意到每条边的出现在时间上是一段一段的，我们可以对时间进行线段树分治，也就是说，假设有一条边是出现在$(l,r)$的时间，那么我们先把这个区间拆成线段树上的一些区间，然后对于每个区间把边加进去。

然后去$\rm dfs$整棵线段树，对于当前区间，先把边全部加进去，然后继续$\rm dfs$，完了之后再撤回这些操作。

那么就可以用并查集维护联通，顺便维护答案，并查集写按秩合并，可以支持撤销，并且每次都是$O(\log n)$。

所以总复杂度$O(n\log ^2 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
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define data asd09123jdf02i3h

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 6e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
const int N = 3e5;

int n,fa[maxn],sz[maxn][2],nxt[maxn],rk[maxn];
pii a[maxn];
ll res[maxn],ans;
map<pii,vector<int > > t;
vector<pii > w[maxn<<2];

#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)

void add(int p,int l,int r,int x,int y,pii v) {
    if(x<=l&&r<=y) {
        // printf("add :: %d %d %d %d\n",l,r,v.fr,v.sc);
        return w[p].pb(v),void();
    }
    if(x<=mid) add(ls,l,mid,x,y,v);
    if(y>mid) add(rs,mid+1,r,x,y,v);
}

int find(int x) {return fa[x]==x?x:find(fa[x]);}

void dfs(int p,int l,int r) {
    stack<pair<int*,int > > st;
    ll pre=ans;
    for(auto x:w[p]) {
        int u=find(x.fr),v=find(x.sc+N);
        if(u==v) continue;
        // printf("insert :: %d %d\n",u,v);
        if(rk[u]>rk[v]) swap(u,v);
        st.push(mp(fa+u,fa[u]));
        fa[u]=v;
        if(rk[u]==rk[v]) st.push(mp(rk+v,rk[v])),rk[v]++;
        st.push(mp(sz[v],sz[v][0]));
        st.push(mp(sz[v]+1,sz[v][1]));
        ans-=1ll*sz[v][0]*sz[v][1];
        sz[v][0]+=sz[u][0],sz[v][1]+=sz[u][1];
        ans-=1ll*sz[u][0]*sz[u][1];
        ans+=1ll*sz[v][0]*sz[v][1];
    }
    // printf("dfs :: %d %d\n",l,r);
    if(l==r) res[l]=ans;
    else dfs(ls,l,mid),dfs(rs,mid+1,r);
    while(!st.empty()) *st.top().fr=st.top().sc,st.pop();
    ans=pre;
}

int main() {
    read(n);
    for(int i=1;i<=N;i++) fa[i]=i,sz[i][0]=1;
    for(int i=1;i<=N;i++) fa[i+N]=i+N,sz[i+N][1]=1;
    for(int i=1;i<=n;i++) read(a[i].fr),read(a[i].sc),t[a[i]].pb(i);
    for(auto &x:t) {
        if(x.sc.size()&1) x.sc.pb(n+1);
        for(int j=0;j<(int)x.sc.size();j+=2) add(1,1,n,x.sc[j],x.sc[j+1]-1,x.fr);
    }
    dfs(1,1,n);
    for(int i=1;i<=n;i++) printf("%I64d ",res[i]);puts("");
    return 0;
}