The 2018 ACM-ICPC Asia Jiaozuo Regional Contest C. Supreme Command
题目链接
http://codeforces.com/gym/102028/problem/C
题目大意
给你一个 $n$ 行 $n$ 列的棋盘，保证每行每列都有且仅有一个棋子。有四种操作，向四个方向移动所有棋子，如果无法移动则停留在原地。两种询问，问某个棋子当前的位置，和当前情况下有多少个重叠再一起的棋子对。
题目分析
注意到每一行每一列都只有一个棋子，则会产生一个很有意思的性质：所有的棋子如果出现合并的情况必定存在它的 $x$ 坐标等于所有棋子的最小值或最大值且 $y$ 坐标也是所有棋子的最小值或最大值。那么一共有四种情况。首先考虑如何维护所有棋子的坐标。由于所有棋子的初始行列坐标都是唯一对应的，因此可以快速将所有点按照行列坐标分别排序。分别维护所有点的行列坐标，每次将所有能移动到边界的行列都合并，记录合并到第几个点即可。由于在最小值和最大值中间的每一个值上都会有一个点，因此可以很轻松的维护点的坐标。再考虑维护重叠的点。由于所有的点一定是在四个角处才能合并因此只需要维护四种情况。而当所有点都合并成一个的时候，这四种情况会合并，维护即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 3e5 + 10;
int n, m, t;
pair <int, int> point[maxn];
int c[2][maxn];
int treen[2][maxn];
/*
x y
1 1 1
1 2 2
2 1 3
2 2 4
*/
int getn(int x, int y, int d){
int ret[4][4];
ret[1][1] = 1;
ret[1][2] = 2;
ret[2][1] = 3;
ret[2][2] = 4;
ret[3][1] = 1;
ret[3][2] = 2;
ret[1][3] = 1;
ret[2][3] = 3;
ret[3][3] = 1;
if(d){
return ret[y][x];
}else{
return ret[x][y];
}
}
struct unionset {
int fa[maxn];
long long son[maxn];
int cnt;
int find(int x){
if(fa[x] != x){
fa[x] = find(fa[x]);
}
return fa[x];
}
int join(int x, int y){
int ra = find(x);
int rb = find(y);
if(ra != rb){
fa[ra] = rb;
son[rb] += son[ra];
}
return 0;
}
long long getans(){
int i, j;
long long ret = 0;
for(i=n+1;i<=n+4;i++){
if(find(i) == i and son[i] > 1){
ret += son[i] * (son[i] - 1) / 2;
}
}
return ret;
}
int init(){
int i, j;
for(i=1;i<=n+4;i++){
fa[i] = i;
son[i] = (i <= n ? 1 : 0);
}
return 0;
}
};
unionset s;
struct sttree {
int mx, mn, delta;
int l, r;
int query(int x){
if(x <= l){
return mn;
}else if(x < r){
return delta + x;
}else{
return mx;
}
}
int update(int x, int d){
if(x > 0){
if(mx + x <= n){
delta += x;
mx += x;
mn += x;
}else{
if(mn + x >= n){
l = n;
r = 1;
mx = n;
mn = n;
if(c[d][1] != 3){
if(c[!d][1] != 3){
for(int i=1;i<=n;i++){
c[d][i] = 3;
if(c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)] != 0){
s.join(treen[d][i], n + getn(3, c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)], d));
}
}
}else{
for(int i=1;i<=n;i++){
c[d][i] = 3;
if(c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)] != 0){
s.join(treen[d][i], n + getn(3, c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)], d));
}
}
s.join(n + 1, n + 3), s.join(n + 2, n + 4);
s.join(n + 1, n + 2), s.join(n + 3, n + 4);
}
}
}else{
int p = r - (mx - (n - x));
int u = r;
delta += x;
mn += x;
mx = n;
r = p;
for(int i=p;i<u;i++){
c[d][i] = 2;
if(c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)] != 0){
s.join(treen[d][i], n + getn(2, c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)], d));
}
}
}
}
}else{
if(mn + x >= 1){
delta += x;
mx += x;
mn += x;
}else{
if(mx + x <= 1){
mx = 1;
mn = 1;
l = n;
r = 1;
if(c[d][1] != 3){
if(c[!d][1] != 3){
for(int i=1;i<=n;i++){
c[d][i] = 3;
if(c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)] != 0){
s.join(treen[d][i], n + getn(3, c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)], d));
}
}
}else{
for(int i=1;i<=n;i++){
c[d][i] = 3;
if(c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)] != 0){
s.join(treen[d][i], n + getn(3, c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)], d));
}
}
s.join(n + 1, n + 3), s.join(n + 2, n + 4);
s.join(n + 1, n + 2), s.join(n + 3, n + 4);
}
}
}else{
int p = l + ((1 - x) - mn);
int u = l;
delta += x;
mn = 1;
mx += x;
l = p;
for(int i=u+1;i<=p;i++){
c[d][i] = 1;
if(c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)] != 0){
s.join(treen[d][i], n + getn(1, c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)], d));
}
}
}
}
}
return 0;
}
int init(){
mx = n;
mn = 1;
l = 1;
r = n;
delta = 0;
return 0;
}
};
sttree treex;
sttree treey;
int read(){
int x = 0;
char ch = getchar();
while('0' > ch or ch > '9'){
ch = getchar();
}
while('0' <= ch and ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
int main(){
int i, j;
int x, y;
char op;
int d;
t = read();
while(t--){
n = read();
m = read();
s.init();
for(i=1;i<=n;i++){
x = read();
y = read();
point[i] = make_pair(x, y);
treen[0][x] = treen[1][y] = i;
c[0][i] = c[1][i] = 0;
}
c[0][1] = c[1][1] = 1;
c[0][n] = c[1][n] = 2;
d = 0,i = 1;
if(c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)] != 0){
s.join(treen[d][i], n + getn(c[d][i], c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)], d));
}
d = 0,i = n;
if(c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)] != 0){
s.join(treen[d][i], n + getn(c[d][i], c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)], d));
}
d = 1,i = 1;
if(c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)] != 0){
s.join(treen[d][i], n + getn(c[d][i], c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)], d));
}
d = 1,i = n;
if(c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)] != 0){
s.join(treen[d][i], n + getn(c[d][i], c[!d][(d ? point[treen[d][i]].first : point[treen[d][i]].second)], d));
}
treex.init();
treey.init();
while(m--){
scanf(" %c", &op);
if(op == '!'){
printf("%lld\n", s.getans());
}else{
x = read();
if(op == 'L'){
treey.update(-x, 1);
}else if(op == 'R'){
treey.update(x, 1);
}else if(op == 'U'){
treex.update(-x, 0);
}else if(op == 'D'){
treex.update(x, 0);
}else if(op == '?'){
printf("%d %d\n", treex.query(point[x].first), treey.query(point[x].second));
}
}
}
}
return 0;
}