题意:
有一个n*n棋盘,一开始上面有n个棋子,且每一行和每一列都恰好只有一个棋子
给出m个操作
所有棋子向上/下/左/右移动k格
查询第i个棋子的位置
查询现在有多少对棋子在同一个格子
对于查询第i个棋子的位置:
将二维棋盘的行列分离,单独计算
以计算列为例
每一列压缩为一行
棋子一旦到达左右边界上,将永远处于同一列
所有棋子左移,可以看成是棋盘的左边界右移
所有棋子右移,可以看成是棋盘的右边界左移
用l,r表示移动后的左右边界在第几列,即所有棋子都在长为r-l+1的区间里
用一个变量δ表示出与实际在第几列的偏移量
即[l+δ,r+δ]才是棋子实际在的区间
偏移量的修改要根据棋子是否会到边界上分开计算
查询的时候
如果棋子的初始位置在l左边,说明棋子在左边界上
如果棋子的初始位置在r右边,说明棋子在右边界上
否则,棋子在区间里面
计算行同理
对于查询有多少个棋子在同一个格子:
还是用棋子移动看作是棋盘边界移动
这样棋子到同一个格子里只会发生在移动边界后的棋盘的四个角上
如果棋子的初始位置既在左边界的左边,又在上边界的上边,那它就在左上角
类推出其他三个角
然后特判一行、一列、一个格子的情况
#include<cstdio> #define N 300001 int n; int a[N],b[N]; long long C[N]; int lu,ld,ru,rd; bool vis[N]; void cal(int ); struct node { int l,r,d; int pos[N],id[N]; void initial() { l=1; r=n; d=0; } void initial2() { cal(id[1]); cal(id[n]); } void add(int p,int i) { pos[i]=p; id[p]=i; } void movel(int k) { while(l<r && l+d-k<1) cal(id[++l]); if(l+d-k>=1) d-=k; else d=1-l; } void mover(int k) { while(l<r && r+d+k>n) cal(id[--r]); if(r+d+k<=n) d+=k; else d=n-r; } int getpos(int x) { if(x<=l) return l+d; else if(x>=r) return r+d; else return x+d; } }lr,ud; void cal(int x) { if(vis[x]) return; if(lr.pos[x]<=lr.l && ud.pos[x]<=ud.l) { vis[x]=true; lu++; } else if(lr.pos[x]<=lr.l && ud.pos[x]>=ud.r) { vis[x]=true; ld++; } else if(lr.pos[x]>=lr.r && ud.pos[x]<=ud.l) { vis[x]=true; ru++; } else if(lr.pos[x]>=lr.r && ud.pos[x]>=ud.r) { vis[x]=true; rd++; } } long long solve() { if(lr.l==lr.r && ud.l==ud.r) return C[lu+ld+ru+rd]; if(lr.l==lr.r) return C[lu+ru]+C[ld+rd]; if(ud.l==ud.r) return C[lu+ld]+C[ru+rd]; return C[lu]+C[ru]+C[ld]+C[rd]; } int main() { int T,m,x,y; char s[3]; for(int i=1;i<N;++i) C[i]=1ll*(i-1)*i/2; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); lr.initial(); ud.initial(); lu=ld=ru=rd=0; for(int i=1;i<=n;++i) vis[i]=0; for(int i=1;i<=n;++i) { scanf("%d%d",&a[i],&b[i]); lr.add(b[i],i); ud.add(a[i],i); } lr.initial2(); ud.initial2(); while(m--) { scanf("%s",s); if(s[0]=='!') printf("%lld ",solve()); else { scanf("%d",&x); if(s[0]=='L') lr.movel(x); else if(s[0]=='R') lr.mover(x); else if(s[0]=='U') ud.movel(x); else if(s[0]=='D') ud.mover(x); else printf("%d %d ",ud.getpos(a[x]),lr.getpos(b[x])); } } } }