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

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

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

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

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

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

并查集写法

#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

如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！