题解 P7963 【[NOIP2021] 棋局】

题目大意：给定 $n\times m$ 的棋盘，棋盘上有 $4$ 种类型的边，分别代表不可通行、只能走一步、只能一直沿一个方向往前走和可以任意走。棋子有两种颜色和等级，棋子间可以吃子，规定只能吃颜色不同且等级不高于自己的棋子，且吃完子后不能继续向前走。同时规定每次走子时经过的边类型必须相同。初始棋盘是空的，有 $q$ 次操作，每次往棋盘上放一个棋子，问这个棋子能走到多少个格子。 题解：先在不考虑吃子的情况下看一个棋子能走到哪些空格子。此时可以把之前已经放上的棋子当作障碍，那么对于第一类边，只需要考虑上下左右 $4$ 个格子；对于第二类边，只需要考虑沿着上下左右 $4$ 个方向延伸出去的一条线段；对于第三类边，只需要考虑第三类边形成的连通块。 我们发现放一个棋子相当于删掉图中的一个点，删点维护图的连通性这件事太蛋疼了，于是我们不妨把问题反过来：假设一开始所有的棋子都是在棋盘上的，我们要每次删去一个棋子，删之前问它能走到多少个格子。 显然加点维护连通性是相对容易的，在不需要维护特殊信息的情况下只需要并查集就能搞定；即使需要维护集合，我们也有启发式合并、线段树合并等一堆合并集合的数据结构和算法。这为我们进一步分析题目提供了很好的技术支持。 首先，对于一类边，只有有限个点的情况总是好处理的：在别的情况都处理完之后，只需要暴力查询一下这几个点是否能被以其他方式走到即可。用并查集自然就可以做到。 对于二类边，我们可以在每个点上维护它向 $4$ 个方向最远能沿着二类边走到哪。这件事也可以用并查集来维护，就是连续一段横向或纵向的二类边串起来的点分别用并查集维护起来，并查集中再顺手维护一个集合的编号最小/最大的点总是容易的。 对于三类边，我们好像也可以直接拿并查集维护所有点在三类边下的连通性，维护每个连通块的大小即可。 做完了吗？没有，最麻烦之处在于：如果一个点通过二类边和三类边都能走到，怎么去重？ 此时要注意到一个性质：我们可以让二类边串起来的一排点的编号是连续的。如果我们把点按照横坐标第一关键字、纵坐标第二关键字排序的话，那么横向的二类边连通块对应编号连续的集合；反之，如果纵坐标第一关键字、横坐标第二关键字，编号连续的就是纵向的二类边连通块了。 所以，如果我们能在一个三类边连通块里查询编号位于某个区间内的点的数量，就可以实现去重了。 回过头来，我们发现简单地用并查集维护三类边的连通块似乎是行不通的，因为去重操作意味着我们还需要实打实地把每个连通块中的点记录下来。这就要用到我们先前提到的集合合并了：我们对每个三类边连通块开两个集合，分别存储其中的点按照两种编号方式的编号。合并连通块时，将两个集合对应合并，查询时在集合中区间查询即可。这里推荐使用线段树合并，因为复杂度为 $1$ 个 $\log$ 且线段树天生支持区间查询。 最后还要处理吃子的情况。我们发现能通过一、二类边吃到的子每个方向上最多一个，因此也留到最后暴力处理即可；而通过三类边能吃到的子可能很多，在当前这个三类边连通块里，如果某个点又向外连了一条三类边而且恰好遇到了一个棋子，它就要被纳入考虑。 具体而言，我们要在每个三类边连通块上同时绑定与其直接通过三类边相邻的棋子集合，当然肯定要分黑白两色维护；合并连通块时，需要把两个集合分别合并，同时注意一个棋子可能同时在两个三类边连通块的集合中，因此还要去重（这里推荐先离散化使得每个棋子的等级均不同，以便于去重）。查询时，只需查询与当前棋子颜色相反的集合中，等级不超过它自身的棋子有多少个即可，这相当于一个前缀查询操作。显然这也是线段树合并就能解决的任务。对于一、二类边的特判，只需将涉及到的棋子在线段树中查询一下是否存在即可。 总结：倒序操作+合并连通块+维护集合，支持合并、区间查询+线段树合并，总复杂度 $O((nm+q) \log (nm+q))$ 。 最后码长大约6KB多的样子，能在场上写出来调过的人请深受我一拜orz。实际上，如果不去写正解的话，至少前 $32$ 分是可以直接模拟+bfs简单通过的，中间“没有三类边”的部分可以如上述题解所述用并查集维护二类边连通块，最后 $n,m\leq 1000,q\leq 2000$ 的部分只需要用并查集维护三类边连通块的大小，而一、二类边以及可能的吃子均不超过 $O(n+m+q)$ 级别，可以枚举+暴力判断，复杂度 $O(nm+q(n+m+q))$（不过据我所知场上真正写了这档的人好像很少的样子qwq）。如上至少 $56$ 分是可以不用写大数据结构即可实现的。~~有人说T4部分分是乱给的，他可不是乱给的啊~~ ```cpp #include<bits/stdc++.h> #define gc getchar() #define pc putchar #define li long long #define md int mid = (l + r) >> 1 #define ln ls[q],l,mid #define rn rs[q],mid + 1,r using namespace std; inline void file(char *s){ char c[50]; sprintf(c,"%s.in",s); freopen(c,"r",stdin); sprintf(c,"%s.out",s); freopen(c,"w",stdout); } int t,n,m,q; int e[4][200010],ans[100010],qz[200010]; struct node{ int col,lv,x,y,id; }a[100010],aa[100010]; inline bool operator < (node x,node y){ return x.lv == y.lv ? x.id < y.id : x.lv < y.lv; } char ch[200010]; #define pos(x,y) (((x) - 1) * m + (y)) #define pos2(x,y) (((y) - 1) * n + (x)) #define tox(x) (((x) - 1) / m + 1) #define toy(x) (((x) - 1) % m + 1) void mgg(int,int); struct bcj{ int f[200010],sz[200010],mx[200010],mn[200010]; inline int getf(int x){ return f[x] == x ? x : f[x] = getf(f[x]); } inline void mg(int u,int v,bool fg = 0){ u = getf(u),v = getf(v); if(u == v) return; if(sz[u] > sz[v]) swap(u,v); sz[v] += sz[u];f[u] = v; mx[v] = max(mx[v],mx[u]); mn[v] = min(mn[v],mn[u]); if(fg) mgg(u,v); } inline void init(int p){ for(int i = 1;i <= p;++i) f[i] = mx[i] = mn[i] = i,sz[i] = 1; } inline int chksz(int x){return sz[getf(x)];} inline int chkmx(int x){return mx[getf(x)];} inline int chkmn(int x){return mn[getf(x)];} }bc[3]; struct xds{ int rt[200010],ls[8000010],rs[8000010],sz[8000010],cnt; inline void init(){ memset(rt,0,sizeof(rt)); for(int i = 1;i <= cnt;++i) ls[i] = rs[i] = sz[i] = 0; cnt = 0; } int ins(int q,int l,int r,int x,int v = 1){ if(!q) q = ++cnt; if(l == r){ if(v == -1) return 0; if(!sz[q]) ++sz[q]; return q; } md; if(mid >= x) ls[q] = ins(ln,x,v); else rs[q] = ins(rn,x,v); sz[q] = sz[ls[q]] + sz[rs[q]]; return sz[q] ? q : 0; } int mg(int p,int q,int l,int r,int op = -1){ if(!p || !sz[p]) return q; if(!q || !sz[q]) return p; if(l == r){ sz[q] = min(1,sz[q] + sz[p]); return q; } md; ls[q] = mg(ls[p],ln,op); rs[q] = mg(rs[p],rn,op); sz[q] = sz[ls[q]] + sz[rs[q]]; return q; } int qy(int q,int l,int r,int x){ if(!q || !x) return 0; if(l == r) return sz[q]; md; if(mid >= x) return qy(ln,x); return sz[ls[q]] + qy(rn,x); } int qy2(int q,int l,int r,int x){ if(!q || !x) return 0; if(l == r) return sz[q]; md; if(mid >= x) return qy2(ln,x); return qy2(rn,x); } int cx(int q,int l,int r){ return qy(rt[q],1,n * m,r) - qy(rt[q],1,n * m,l - 1); } }xd[4]; void mgg(int u,int v){ xd[0].rt[v] = xd[0].mg(xd[0].rt[u],xd[0].rt[v],1,q); xd[1].rt[v] = xd[1].mg(xd[1].rt[u],xd[1].rt[v],1,q); xd[2].rt[v] = xd[2].mg(xd[2].rt[u],xd[2].rt[v],1,n * m); xd[3].rt[v] = xd[3].mg(xd[3].rt[u],xd[3].rt[v],1,n * m); } inline void init(){ memset(e,0,sizeof(e)); memset(qz,0,sizeof(qz)); memset(ans,0,sizeof(ans)); for(int i = 0;i < 3;++i) bc[i].init(n * m); for(int i = 0;i < 4;++i) xd[i].init(); } int dx[4] = {-1,0,1,0},dy[4] = {0,-1,0,1}; inline bool caneat(int x,int y){ if(!y || y >= x) return 0; node ax = a[x],ay = a[y]; return ax.col != ay.col && ax.lv >= ay.lv; } int main(){ //file("chess"); int i,j,k,id,tx,ty,nxt; scanf("%d",&t); while(t--){ scanf("%d%d%d",&n,&m,&q); init(); for(i = 1;i <= n;++i){ scanf("%s",ch + 1); for(j = 1;j < m;++j){ e[1][pos(i,j + 1)] = e[3][pos(i,j)] = ch[j] - '0'; } } for(i = 1;i < n;++i){ scanf("%s",ch + 1); for(j = 1;j <= m;++j){ e[0][pos(i + 1,j)] = e[2][pos(i,j)] = ch[j] - '0'; } } for(i = 1;i <= q;++i){ scanf("%d%d%d%d",&a[i].col,&a[i].lv,&a[i].x,&a[i].y); a[i].id = i; } sort(a + 1,a + q + 1); for(i = 1;i <= q;++i) a[i].lv = i; for(i = 1;i <= q;++i) aa[a[i].id] = a[i]; for(i = 1;i <= q;++i) a[i] = aa[i]; for(i = 1;i <= q;++i) qz[pos(a[i].x,a[i].y)] = i; for(i = 1;i <= n;++i){ for(j = 1;j <= m;++j){ id = pos(i,j); for(k = 0;k < 4;++k) if(e[k][id] > 1){ tx = i + dx[k];ty = j + dy[k];nxt = pos(tx,ty); if(!qz[id] && !qz[nxt]) bc[e[k][id] == 3 ? 0 : k % 2 + 1].mg(id,nxt); } } } for(i = 1;i <= n;++i){ for(j = 1;j <= m;++j){ id = pos(i,j);int iid = bc[0].getf(id); xd[2].rt[iid] = xd[2].ins(xd[2].rt[iid],1,n * m,pos2(i,j)); xd[3].rt[iid] = xd[3].ins(xd[3].rt[iid],1,n * m,id); for(k = 0;k < 4;++k) if(e[k][id] == 3){ tx = i + dx[k];ty = j + dy[k];nxt = pos(tx,ty); if(qz[nxt]){ int tmp = a[qz[nxt]].col; xd[tmp].rt[iid] = xd[tmp].ins(xd[tmp].rt[iid],1,q,a[qz[nxt]].lv); } } } } for(i = q;i;--i){ id = pos(a[i].x,a[i].y); int tmp = a[i].col,px = a[i].x,py = a[i].y; //opt=3 for(j = 0;j < 4;++j) if(e[j][id] == 3){ tx = px + dx[j];ty = py + dy[j];nxt = pos(tx,ty); nxt = bc[0].getf(nxt); xd[tmp].rt[nxt] = xd[tmp].ins(xd[tmp].rt[nxt],1,q,a[i].lv,-1); } for(j = 0;j < 4;++j) if(e[j][id] == 3){ tx = px + dx[j];ty = py + dy[j];nxt = pos(tx,ty); if(qz[nxt] && qz[nxt] < i) continue; bc[0].mg(id,nxt,1); } int iid = bc[0].getf(id); ans[i] = bc[0].chksz(id) + xd[!tmp].qy(xd[!tmp].rt[iid],1,q,a[i].lv); //opt=2 for(j = 0;j < 4;++j) if(e[j][id] == 2){ tx = px + dx[j];ty = py + dy[j];nxt = pos(tx,ty); if(qz[nxt] && qz[nxt] < i) continue; bc[j % 2 + 1].mg(id,nxt); } int mx1 = bc[1].chkmx(id),mx2 = bc[2].chkmx(id); int mn1 = bc[1].chkmn(id),mn2 = bc[2].chkmn(id); ans[i] += mx2 - mn2 + 1 + (mx1 - mn1) / m + 1; //all int dmx = pos2(tox(mx1),toy(mx1)),dmn = pos2(tox(mn1),toy(mn1)); ans[i] -= xd[2].cx(iid,dmn,dmx) + xd[3].cx(iid,mn2,mx2); if(e[0][mn1] == 2 && caneat(i,qz[mn1 - m])){ if(!xd[!tmp].qy2(xd[!tmp].rt[iid],1,q,a[qz[mn1 - m]].lv)) ++ans[i]; } if(e[1][mn2] == 2 && caneat(i,qz[mn2 - 1])){ if(!xd[!tmp].qy2(xd[!tmp].rt[iid],1,q,a[qz[mn2 - 1]].lv)) ++ans[i]; } if(e[2][mx1] == 2 && caneat(i,qz[mx1 + m])){ if(!xd[!tmp].qy2(xd[!tmp].rt[iid],1,q,a[qz[mx1 + m]].lv)) ++ans[i]; } if(e[3][mx2] == 2 && caneat(i,qz[mx2 + 1])){ if(!xd[!tmp].qy2(xd[!tmp].rt[iid],1,q,a[qz[mx2 + 1]].lv)) ++ans[i]; } //opt=1 for(j = 0;j < 4;++j) if(e[j][id] == 1){ tx = px + dx[j];ty = py + dy[j];nxt = pos(tx,ty); if(qz[nxt] && qz[nxt] < i){ if(caneat(i,qz[nxt]) && !xd[!tmp].qy2(xd[!tmp].rt[iid],1,q,a[qz[nxt]].lv)) ++ans[i]; } else if(bc[0].getf(id) != bc[0].getf(nxt)) ++ans[i]; } --ans[i]; } for(i = 1;i <= q;++i){ printf("%d\n",ans[i]); } } return 0; } ```