洛谷P3300 城市规划

题意：给你一个6 * n的网格题，单点修改，询问区间联通块数。n <= 10w

解：看起来就很显然的一道题......线段树每个点用一个ufs维护连通性。完了。

我为了方便思考把图转成横着的了。

写起来真是毒瘤......

重点在于：1.建立叶节点。2.合并两个子节点。3.把新的并查集的中间两列压掉。

第一步，这个就直接枚举，merge就完事了。

第二步，把两个2列的子并查集copy到当前节点的4列的并查集上。注意右边那个并查集，fa全部要加2m，因为下标加了2m。

然后枚举中间两列merge。这样也做完了。

第三步，我们只要保留两边的两列即可。注意到有可能有两边元素的代表元在中间，我们使用左偏树技巧，切换代表元到它自己，注意vis也要变。

然后把两边的vis和facopy一份出来，用以查询代表元。

然后把前两列init，然后枚举每个元素，跟它的代表元merge。注意这一步会对连通块总数tot造成改变，最后复原即可。

最后把前两列的vis和lk从copy的那里拿来用即可。

注意，vis(当前联通块是否有建筑物)要继承代表元的，lk(能否与两边连通)直接从对应下标继承，这两个不一样！

具体实现看代码吧......

 #include <bits/stdc++.h>

 #define ck(x) ((x) == '+' || (x) == '|')

 const int N = ;

 template <typename T> inline void read(T &x) {

     x = ;

     char c = getchar();

     while(c < '' || c > '') {

         c = getchar();

     }

     while(c >= '' && c <= '') {

         x = x *  + c - ;

         c = getchar();

     }

     return;

 }

 int n, m, gt[], GT, exfa[], exvis[], exlk[], newvis[], newlk[];

 int exfind(int x) {

     return (x == exfa[x]) ? x : exfa[x] = exfind(exfa[x]);

 }

 inline int trans(int x) {

     return x < m ? x : x - (m << );

 }

 struct Node {

     int fa[], tot;

     std::bitset<> lk, vis;

     int find(int x) {

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

     }

     inline void Merge(int x, int y) {

         x = find(x);

         y = find(y);

         if(x == y) return;

         fa[y] = x;

         tot -= (vis[x] && vis[y]);

         if(vis[y]) vis.set(x);

         return;

     }

     Node() {}

     Node(char *a) {

         tot = ;

         for(register int i(); i < m; ++i) {

             fa[i + m] = fa[i] = i;

             if(a[i] == 'O') {

                 vis.set(i);

                 vis.set(i + m);

                 lk.set(i);

                 lk.set(i + m);

                 ++tot;

             }

             else if(a[i] == '.') {

                 vis.reset(i);

                 vis.reset(i + m);

                 lk.reset(i);

                 lk.reset(i + m);

             }

             else if(a[i] == '-' || a[i] == '+') {

                 vis.reset(i);

                 vis.reset(i + m);

                 lk.set(i);

                 lk.set(i + m);

             }

         }

         for(register int i(); i < m; ++i) {

             if(ck(a[i - ]) && ck(a[i])) {

                 Merge(i - , i);

             }

             else if((ck(a[i - ]) && a[i] == 'O') || (ck(a[i]) && a[i - ] == 'O')) {

                 Merge(i - , i);

             }

             else if(a[i] == 'O' && a[i - ] == 'O') {

                 Merge(i - , i);

             }

         }

     }

     inline void update() {

         for(register int i(); i < m; ++i) {

             int t(find(i));

             fa[i] = fa[t] = i;

             vis[i] = vis[t];

             t = find(i + m * );

             fa[i + m * ] = fa[t] = i + m * ;

             vis[i + m * ] = vis[t];

         }

         memcpy(exfa, fa, sizeof(fa));

         for(register int i(); i < m; ++i) {

             exvis[i] = vis[i];

             exvis[i + m * ] = vis[i + m * ];

             exlk[i] = lk[i];

             exlk[i + m * ] = lk[i + m * ];

         }

         int temp = tot;

         for(register int i(); i < m; ++i) {

             fa[i] = i;

             fa[i + m] = i + m;

         }

         for(register int i(); i < m; ++i) {

             Merge(i, trans(exfind(i)));

             Merge(i + m, trans(exfind(i + m * )));

         }

         for(register int i(); i < m; ++i) {

             vis[i] = exvis[exfind(i)];

             vis[i + m] = exvis[exfind(i + m * )];

             lk[i] = exlk[i];

             lk[i + m] = exlk[i + m * ];

         }

         tot = temp;

         return;

     }

     inline Node merge(const Node &w) const {

         Node ans;

         /// copy

         for(register int i(); i < m; ++i) {

             ans.fa[i] = fa[i];

             ans.lk[i] = lk[i];

             ans.vis[i] = vis[i];

             ans.fa[i + m] = fa[i + m];

             ans.lk[i + m] = lk[i + m];

             ans.vis[i + m] = vis[i + m];

             ans.fa[i + m * ] = w.fa[i] + m * ;

             ans.lk[i + m * ] = w.lk[i];

             ans.vis[i + m * ] = w.vis[i];

             ans.fa[i + m * ] = w.fa[i + m] + m * ;

             ans.lk[i + m * ] = w.lk[i + m];

             ans.vis[i + m * ] = w.vis[i + m];

         }

         ans.tot = tot + w.tot;

         /// merge

         for(register int i(); i < m; ++i) {

             if(ans.lk[i + m] && ans.lk[i + m * ]) { /// -> <-

                 ans.Merge(i + m, i + m * 2);

             }

         }

         ans.update();

         return ans;

     }

 }node[N << ];

 char str[N][];

 void build(int l, int r, int o) {

     if(l == r) {

         node[o] = Node(str[r]);

         return;

     }

     int mid = (l + r) >> ;

     build(l, mid, o << );

     build(mid + , r, o <<  | );

     node[o] = node[o << ].merge(node[o <<  | ]);

     return;

 }

 void change(int p, int l, int r, int o) {

     if(l == r) {

         node[o] = Node(str[r]);

         return;

     }

     int mid = (l + r) >> ;

     if(p <= mid) {

         change(p, l, mid, o << );

     }

     else {

         change(p, mid + , r, o <<  | );

     }

     node[o] = node[o << ].merge(node[o <<  | ]);

     return;

 }

 Node ask(int L, int R, int l, int r, int o) {

     if(L <= l && r <= R) {

         return node[o];

     }

     int mid = (l + r) >> ;

     if(R <= mid) {

         return ask(L, R, l, mid, o << );

     }

     if(mid < L) {

         return ask(L, R, mid + , r, o <<  | );

     }

     Node temp(ask(L, R, l, mid, o << ));

     temp = temp.merge(ask(L, R, mid + , r, o <<  | ));

     return temp;

 }

 int main() {

     read(n); read(m);

     for(int i = ; i <= n; i++) {

         scanf("%s", str[i]);

         for(int j = ; j < m; j++) {

             if(str[i][j] == '-') {

                 str[i][j] = '|';

             }

             else if(str[i][j] == '|') {

                 str[i][j] = '-';

             }

         }

     }

     build(, n, );

     int q, x, y;

     char ss[];

     read(q);

     for(int i = ; i <= q; i++) {

         scanf("%s", ss); read(x); read(y);

         if(ss[] == 'C') { /// change

             scanf("%s", ss);

             if(ss[] == '-') {

                 ss[] = '|';

             }

             else if(ss[] == '|') {

                 ss[] = '-';

             }

             str[x][y - ] = ss[];

             change(x, , n, );

         }

         else { /// Query

             Node temp = ask(x, y, , n, );

             printf("%d\n", temp.tot);

         }

     }

     return ;

 }

AC代码

这代码常数奇大...

巴特西

洛谷P3300 城市规划

最新文章

热门文章