icontofig | 发布于 2020-02-22 21:22:30 | 阅读量 441 | 并查集
发布于 2020-02-22 21:22:30 | 并查集

题目大意

一开始有一个所有数全都为0的n*m的矩阵。

一共有q次操作,每次操作读入x,y,c,将坐标为(x,y)处的值改为c。

问每一次操作后连通块的个数是多少。

如果两个相邻的格子数字相同,我们认为这两个格子属于同一个连通块。

询问中的c的值保证单调不减。

题解

询问连通块个数的题目一般来说肯定需要用并查集。

但是有一个问题是普通的并查集并不支持删除操作。

因为改变值,实际上相当于是先删除一个值再添加另一个值。所以必定会涉及到删除操作。

此题也不能用可持久化并查集,因为操作并不是“回溯”,而是单纯的删除。

并查集询问连通块个数的时候一般都是静态询问,但是这个题明显是一个动态维护,难度更高。

首先解决动态维护的问题吧。

我们可以去整一个add数组,里面记录当前操作后连通块个数相较于之前发生了什么样的变化。

后面就是如何计算这个add数组的问题了,先考虑删除问题。

删除是并查集无法完成的操作,但是添加可以,我们可以把删除看作是反向添加,用一个反向添加的并查集来表示删除的元素构成的连通块个数,用对应时间点的添加的连通块个数减去删除的连通块个数即为这个时间点操作后的答案。

具体在实施的时候,不能单纯对矩阵的方格建立并查集。我们需要对于不同的数字情况下分别对方格建立并查集,这样来操作,否则删除的时候会出现问题。

当添加一个元素的时候,扫描其周围四个点与其颜色相同的点的个数num,并查集个数改变量为1-num。

此题思路看代码可能会更加清晰,因为确实跟平常的并查集题目并不相像。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
const int maxc = 2e6+5;
int n,m,q;
int f[maxn*maxn];
int find(int x){
    if(f[x] != x)f[x] = find(f[x]);
    return f[x];
}
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
typedef pair<int,int> PI;
vector<PI>add[maxc],del[maxc];
int a[maxn][maxn],dif[maxc];
void calc(const vector<PI> &p,int flag){
    for(int i = 0;i < n;++i)
        for(int j = 0;j < m;++j)
            a[i][j] = 0;
    for(int i = 0;i < n*m;++i)
        f[i] = i;
    for(auto it : p){
        int cur = 1;
        int x = it.first / m;
        int y = it.first % m;
        a[x][y] = 1;
        for(int i = 0;i < 4;++i){
            int nx = x + dx[i],ny = y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny <= m && a[nx][ny] == 1){
                int id = nx * m + ny;
                int fx = find(it.first),fy = find(id);
                if(fx == fy){
                    continue;
                }
                else{
                    f[fy] = fx;
                    cur -= 1;
                }
            }
        }
        dif[it.second] += cur * flag;
    }
    return;
}
int ans = 0;
int x,y,c;
int tot = 0;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1;i <= q;++i){
        cin >> x >> y >> c;
        --x;--y;
        if(a[x][y] == c)continue;
        add[c].push_back(make_pair(x*m+y,i));
        del[a[x][y]].push_back(make_pair(x*m+y,i));
        a[x][y] = c;
        tot = c;
    }
    for(int i = 0;i < n;++i)
        for(int j = 0;j < m;++j)
            del[a[i][j]].push_back(make_pair(i*m+j,q+1));
    for(int i = 0;i <= tot;++i)
        reverse(del[i].begin(),del[i].end());
    for(int i = 0;i <= tot;++i)
        calc(add[i],1);
    for(int i = 0;i <= tot;++i)
        calc(del[i],-1);
    ans = 1;
    for(int i = 1;i <= q;++i){
        ans += dif[i];
        cout << ans << "\n";
    }
    return 0;
}



内容更新于: 2020-02-22 21:22:36
链接地址: http://blog.leanote.com/post/icontofig/CodeForces-1

上一篇: CodeForces 1313.C2 Skyscrapers(hard version) nlogn线段树做法

下一篇: Codeforces 547E Mike and Friends AC自动机Fail树上DFS序建可持久化线段树

441 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航