欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  科技

2020秦皇岛CCPC 7-2 Bounding Wall（树状数组+二分，并查集）

程序员文章站 2022-07-02 11:22:12
题意：一个n*m的方格，每个格子可以是’#‘或者’.‘ 。每次操作可以改变一个格子的状态，或者询问经过(x,y)的最大方框面积，且这个方框不能经过’.’ 。思路：思路参考自大佬每次询问一个点(x,y)(x,y)(x,y)，我们只需要考虑以这个点为矩形下边的情况，然后枚举上面那条边。其他的情况只需要将方格旋转90°/180°/270°即可。我们维护每个点最左边/右边/上边的’.'位置。那么每次修改点，只需要单独维护出这个点左边/右边/上边的位置，复杂度O(n+m)O(n+m)O(n+m)。你想想...

题意：
一个n*m的方格，每个格子可以是’#‘或者’.‘ 。每次操作可以改变一个格子的状态，或者询问经过(x,y)的最大方框面积，且这个方框不能经过’.’ 。

思路：
思路参考自大佬
每次询问一个点 ( x , y ) (x,y) (x,y)，我们只需要考虑以这个点为矩形下边的情况，然后枚举上面那条边。其他的情况只需要将方格旋转90°/180°/270°即可。

我们维护每个点最左边/右边/上边的’.'位置。那么每次修改点，只需要单独维护出这个点左边/右边/上边的位置，复杂度 O ( n + m ) O(n+m) O(n+m)。

你想想，我们维护的是边框，所以只有上边和下边得全部是 # ，所以假设我们已经确定下边界的点 ( x , y ) (x,y) (x,y)，和上边界点 ( i , y ) (i,y) (i,y)。此时矩阵边框的高是确定的，我们只需要确定能否找到对应的左右边。

所以我们可以记录下 x   i x~i x i行的哪些列出现过’.’。我们只需要从左边界开始往右找到第一个无’.‘的列，从右边界开始向左找到第一个无’.'的列。这就确定了左右边界了。这个过程可以用并查集或者树状数组+二分可以维护。

并查集写法

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long ll;

const int maxn = 1e3 + 7;

char s_now[maxn][maxn],s[maxn][maxn];
int fa[maxn],mi[maxn],mx[maxn];
int Up[maxn][maxn],L[maxn][maxn],R[maxn][maxn];
int ans[maxn],vis[maxn];
vector<int>vec[maxn];
int n,m,q;

struct Query {
    int id,x,y;
}que_now[maxn],que[maxn];

int findset(int x) {
    if(fa[x] == x) return fa[x];
    return fa[x] = findset(fa[x]);
}

void Union(int x,int y) {
    int rx = findset(x),ry = findset(y);
    if(rx != ry) {
        fa[rx] = ry;
        mi[ry] = min(mi[rx],mi[ry]);
        mx[ry] = max(mx[rx],mx[ry]);
    }
}

void init() {
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            Up[i][j] = s[i][j] == '.' ? i : Up[i - 1][j];
            L[i][j] = s[i][j] == '.' ? j : L[i][j - 1];
        }
        for(int j = m;j >= 1;j--) {
            R[i][j] = s[i][j] == '.' ? j : (j == m ? m + 1 : R[i][j + 1]);
        }
    }
}

void solve() {
    init();
    for(int t = 1;t <= q;t++) {
        int x = que[t].x,y = que[t].y;
        if(que[t].id == 1) {
            s[x][y] = s[x][y] == '.' ? '#' : '.';
            for(int i = 1;i <= m;i++) {
                L[x][i] = s[x][i] == '.' ? i : L[x][i - 1];
            }
            for(int i = m;i >= 1;i--) {
                R[x][i] = s[x][i] == '.' ? i : (i == m ? m + 1 : R[x][i + 1]);
            }
            for(int i = 1;i <= n;i++) {
                Up[i][y] = s[i][y] == '.' ? i : Up[i - 1][y];
            }
        } else {
            if(s[x][y] == '#') {
                int l = L[x][y] + 1,r = R[x][y] - 1;
                ans[t] = max(ans[t],r - l + 1);
                for(int i = 0;i <= max(n + 1,m + 1);i++) {
                    vis[i] = 0,vec[i].clear();
                }
                for(int i = l;i <= r;i++) {
                    vec[Up[x][i]].push_back(i);
                }
                
                for(int i = x - 1;i >= 1;i--) {
                    int cl = L[i][y] + 1,cr = R[i][y] - 1;
                    cl = max(l,cl);
                    cr = min(r,cr);
                    if(y >= cl && y <= cr) {
                        if(vis[cl]) {
                            cl = mx[findset(cl)] + 1;
                        }
                        if(vis[cr]) {
                            cr = mi[findset(cr)] - 1;
                        }
                        if(y >= cl && y <= cr) {
                            ans[t] = max(ans[t],(x - i + 1) * (cr - cl + 1));
                        }
                    }
                    for(int j = 0;j < vec[i].size();j++) {
                        int v = vec[i][j];
                        vis[v] = 1;
                        fa[v] = v;
                        mi[v] = mx[v] = v;
                        if(vis[v - 1]) Union(v - 1,v);
                        if(vis[v + 1]) Union(v,v + 1);
                    }
                }
            }
        }
    }
}

int main() {
    int T;scanf("%d",&T);
    int kase = 0;
    while(T--) {
        scanf("%d%d%d",&n,&m,&q);
        for(int i = 1;i <= n;i++) scanf("%s",s_now[i] + 1);
        for(int i = 1;i <= q;i++) {
            scanf("%d%d%d",&que_now[i].id,&que_now[i].x,&que_now[i].y);
        }
        
        for(int i = 1;i <= q;i++) ans[i] = 0;
        
        //正常情况
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= m;j++) {
                s[i][j] = s_now[i][j];
            }
        }
        for(int i = 1;i <= q;i++) {
            que[i].id = que_now[i].id;
            que[i].x = que_now[i].x;
            que[i].y = que_now[i].y;
        }
        solve();

//        旋转90度
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= m;j++) {
                s[j][n - i + 1] = s_now[i][j];
            }
        }

        for(int i = 1;i <= q;i++) {
            que[i].id = que_now[i].id;
            que[i].x = que_now[i].y;
            que[i].y = n - que_now[i].x + 1;
        }
        swap(n,m);
        solve();
        swap(n,m);

        //旋转180度
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= m;j++) {
                s[n - i + 1][m - j + 1] = s_now[i][j];
            }
        }
        for(int i = 1;i <= q;i++) {
            que[i].id = que_now[i].id;
            que[i].x = n - que_now[i].x + 1;
            que[i].y = m - que_now[i].y + 1;
        }
        solve();

        //旋转270度
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= m;j++) {
                s[m - j + 1][i] = s_now[i][j];
            }
        }
        for(int i = 1;i <= q;i++) {
            que[i].id = que_now[i].id;
            que[i].x = m - que_now[i].y + 1;
            que[i].y = que_now[i].x;
        }
        swap(n,m);
        solve();

        printf("Case #%d:\n",++kase);
        for(int i = 1;i <= q;i++) {
            if(que_now[i].id == 2) {
                printf("%d\n",ans[i]);
            }
        }
    }
    return 0;
}

树状数组+二分写法

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long ll;

const int maxn = 1e3 + 7;

char s_now[maxn][maxn],s[maxn][maxn];
int fa[maxn],mi[maxn],mx[maxn];
int Up[maxn][maxn],L[maxn][maxn],R[maxn][maxn];
int ans[maxn],vis[maxn];
vector<int>vec[maxn];
int n,m,q;

struct Query {
    int id,x,y;
}que_now[maxn],que[maxn];

int c[maxn];

void add(int x,int v) {
    while(x <= m) {
        c[x] += v;
        x += x & -x;
    }
}

int query(int x) {
    int res = 0;
    while(x) {
        res += c[x];
        x -= x & -x;
    }
    return res;
}

void init() {
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            Up[i][j] = s[i][j] == '.' ? i : Up[i - 1][j];
            L[i][j] = s[i][j] == '.' ? j : L[i][j - 1];
        }
        for(int j = m;j >= 1;j--) {
            R[i][j] = s[i][j] == '.' ? j : (j == m ? m + 1 : R[i][j + 1]);
        }
    }
}

int binL(int l,int r) { //最左边位置
    int ans = r + 1;
    int num = query(l);
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(query(mid) <= num) {
            l = mid + 1;
            ans = mid;
        } else {
            r = mid - 1;
        }
    }
    return ans + 1;
}

int binR(int l,int r) { //最右边位置
    int ans = l - 1;
    int num = query(r);
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(query(mid) >= num) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

void solve() {
    init();
    for(int t = 1;t <= q;t++) {
        int x = que[t].x,y = que[t].y;
        if(que[t].id == 1) {
            s[x][y] = s[x][y] == '.' ? '#' : '.';
            for(int i = 1;i <= m;i++) {
                L[x][i] = s[x][i] == '.' ? i : L[x][i - 1];
            }
            for(int i = m;i >= 1;i--) {
                R[x][i] = s[x][i] == '.' ? i : (i == m ? m + 1 : R[x][i + 1]);
            }
            for(int i = 1;i <= n;i++) {
                Up[i][y] = s[i][y] == '.' ? i : Up[i - 1][y];
            }
        } else {
            if(s[x][y] == '#') {
                int l = L[x][y] + 1,r = R[x][y] - 1;
                ans[t] = max(ans[t],r - l + 1);
                for(int i = 0;i <= max(n + 1,m + 1);i++) {
                    vis[i] = 0;
                    vec[i].clear();
                    c[i] = 0;
                }
                for(int i = l;i <= r;i++) {
                    vec[Up[x][i]].push_back(i);
                    add(i,1);
                }
                
                for(int i = x - 1;i >= 1;i--) {
                    int cl = L[i][y] + 1,cr = R[i][y] - 1;
                    cl = max(l,cl);
                    cr = min(r,cr);
                    if(y >= cl && y <= cr) {
                        if(vis[cl] && cl <= cr) {
                            int pos = binL(cl,cr);
                            cl = pos;
                        }
                        if(vis[cr] && cl <= cr) {
                            int pos = binR(cl,cr);
                            cr = pos;
                        }
                        if(y >= cl && y <= cr) {
                            ans[t] = max(ans[t],(x - i + 1) * (cr - cl + 1));
                        }
                    }
                    for(int j = 0;j < vec[i].size();j++) {
                        int v = vec[i][j];
                        vis[v] = 1;
                        add(v,-1);
                    }
                }
            }
        }
    }
}

int main() {
    int T;scanf("%d",&T);
    int kase = 0;
    while(T--) {
        scanf("%d%d%d",&n,&m,&q);
        for(int i = 1;i <= n;i++) scanf("%s",s_now[i] + 1);
        for(int i = 1;i <= q;i++) {
            scanf("%d%d%d",&que_now[i].id,&que_now[i].x,&que_now[i].y);
        }
        
        for(int i = 1;i <= q;i++) ans[i] = 0;
        
        //正常情况
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= m;j++) {
                s[i][j] = s_now[i][j];
            }
        }
        for(int i = 1;i <= q;i++) {
            que[i].id = que_now[i].id;
            que[i].x = que_now[i].x;
            que[i].y = que_now[i].y;
        }
        solve();
        
        //        旋转90度
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= m;j++) {
                s[j][n - i + 1] = s_now[i][j];
            }
        }
        
        for(int i = 1;i <= q;i++) {
            que[i].id = que_now[i].id;
            que[i].x = que_now[i].y;
            que[i].y = n - que_now[i].x + 1;
        }
        swap(n,m);
        solve();
        swap(n,m);
        
        //旋转180度
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= m;j++) {
                s[n - i + 1][m - j + 1] = s_now[i][j];
            }
        }
        for(int i = 1;i <= q;i++) {
            que[i].id = que_now[i].id;
            que[i].x = n - que_now[i].x + 1;
            que[i].y = m - que_now[i].y + 1;
        }
        solve();
        
        //旋转270度
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= m;j++) {
                s[m - j + 1][i] = s_now[i][j];
            }
        }
        for(int i = 1;i <= q;i++) {
            que[i].id = que_now[i].id;
            que[i].x = m - que_now[i].y + 1;
            que[i].y = que_now[i].x;
        }
        swap(n,m);
        solve();
        
        printf("Case #%d:\n",++kase);
        for(int i = 1;i <= q;i++) {
            if(que_now[i].id == 2) {
                printf("%d\n",ans[i]);
            }
        }
    }
    return 0;
}

本文地址：https://blog.csdn.net/tomjobs/article/details/109239884

相关标签： # 树状数组 # 并查集

上一篇： Mybatis实体类属性与数据库不一致解决方案

下一篇： SpringCloud Alibaba Seata (收藏版)

推荐阅读