CF1140F Extending Set of Points 【按时间分治，并查集】

喜欢ヅ旅行 2021-11-09 11:02 184阅读 0赞

题目链接：[洛谷][Link 1]

首先我们考虑没有撤回操作的情况，就是将每一行和每一列看做一个点（代表行的称为白点，代表列的称为黑点），每个点$(x,y)$看做一条边。

Extend操作实际上就是$x\_1$行与$y\_1,y\_2$列联通，$x\_2$行与$y\_1$列联通时，$x\_2$行也跟$y\_2$列联通。

同一个联通块里的一个黑点和一个白点会产生1的贡献，所以就是连边操作+查询每个联通块的（黑点个数\*白点个数）之和，可以使用并查集维护。

现在考虑撤回操作，其实就相当于每条边在$\[t\_1,t\_2\]$这段时间里“有贡献”，考虑建一个关于时间的线段树，将$\[t\_1,t\_2\]$拆分为log个区间，然后将这条边加入这log个区间对应的边集中，表示在这个区间的范围中这条边“有贡献”。

然后对这个线段树进行dfs，每次dfs到一个区间$\[l,r\]$的时候，将这个区间对应的边集的边加入并查集，退出的时候把影响消除。

其实对于大部分非均摊时间的数据结构都是可以很快撤回的，并查集也是这样。所以不能使用路径压缩，要使用按秩合并。

时间复杂度$O(n\\log^2n)$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 #define Rint register int
     3 #define fi first
     4 #define se second
     5 #define mp make_pair
     6 using namespace std;
     7 typedef long long LL;
     8 typedef pair<int, int> pii;
     9 const int N = 600003;
    10 int q, fa[N], siz[N][2], top;
    11 map<pii, int> ma;
    12 vector<pii> vec[N << 2];
    13 LL ans, ansx[N];
    14 inline int getfa(int x){
    15     return x == fa[x] ? x : getfa(fa[x]);
    16 }
    17 pii que[N];
    18 inline void comb(int x, int y){
    19     x = getfa(x); y = getfa(y);
    20     if(x == y) return;
    21     if(siz[x][0] + siz[x][1] < siz[y][0] + siz[y][1]) swap(x, y);
    22     ans += (LL) siz[x][0] * siz[y][1] + (LL) siz[x][1] * siz[y][0];
    23     siz[x][0] += siz[y][0];
    24     siz[x][1] += siz[y][1];
    25     fa[y] = x;
    26     que[++ top] = mp(x, y);
    27 }
    28 inline void undo(int x, int y){
    29     fa[y] = y;
    30     siz[x][0] -= siz[y][0];
    31     siz[x][1] -= siz[y][1];
    32     ans -= (LL) siz[x][0] * siz[y][1] + (LL) siz[x][1] * siz[y][0];
    33 }
    34 inline void update(int x, int L, int R, int l, int r, pii val){
    35     if(l <= L && R <= r){
    36         vec[x].push_back(val);
    37         return;
    38     }
    39     int mid = L + R >> 1;
    40     if(l <= mid) update(x << 1, L, mid, l, r, val);
    41     if(mid < r) update(x << 1 | 1, mid + 1, R, l, r, val);
    42 }
    43 inline void dfs(int x, int L, int R){
    44     int now = top;
    45     for(pii tmp : vec[x])
    46         comb(tmp.fi, tmp.se);
    47     if(L == R) ansx[L] = ans;
    48     else {
    49         int mid = L + R >> 1;
    50         dfs(x << 1, L, mid); dfs(x << 1 | 1, mid + 1, R);
    51     }
    52     while(top > now){
    53         undo(que[top].fi, que[top].se); -- top;
    54     }
    55 }
    56 int main(){
    57     scanf("%d", &q);
    58     for(Rint i = 1;i <= q;i ++){
    59         int x, y;
    60         scanf("%d%d", &x, &y); y += 3e5;
    61         if(!ma.count(mp(x, y))) ma[mp(x, y)] = i;
    62         else {
    63             update(1, 1, q, ma[mp(x, y)], i - 1, mp(x, y));
    64             ma.erase(mp(x, y));
    65         }
    66     }
    67     for(auto it = ma.begin();it != ma.end();it ++)
    68         update(1, 1, q, it -> se, q, it -> fi);
    69     for(Rint i = 1;i <= 3e5;i ++) fa[i] = i, siz[i][0] = 1;
    70     for(Rint i = 3e5 + 1;i <= 6e5;i ++) fa[i] = i, siz[i][1] = 1;
    71     dfs(1, 1, q);
    72     for(Rint i = 1;i <= q;i ++) printf("%lld\n", ansx[i]);
    73 }

CF1140F

转载于:https://www.cnblogs.com/AThousandMoons/p/11116420.html

[Link 1]: https://www.luogu.org/problemnew/show/CF1140F
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/ed09af41868543b085b9ee61e45436eb.png