学习C++从娃娃抓起！记录下AtCoder（日本算法竞技网站）备赛学习过程中的题目，记录每一个瞬间。
附上汇总贴：AtCoder 备赛刷题 | 汇总
【Problem Statement】
There are N N N stones placed on a 2 2 2-dimensional plane. The i i i-th stone is located at coordinates ( X i , Y i ) (X_i,Y_i) (Xi,Yi). All stones are located at lattice points in the first quadrant (including the axes).
有 N N N 块石头放置在一个 2 2 2 维的平面上。第 i i i 块石头位于坐标 ( X i , Y i ) (X_i,Y_i) (Xi,Yi) 处。所有石头都位于第一象限（包括轴线）的格点处。
Count the number of lattice points ( x , y ) (x,y) (x,y) where no stone is placed and it is impossible to reach ( − 1 , − 1 ) (−1,−1) (−1,−1) from ( x , y ) (x,y) (x,y) by repeatedly moving up, down, left, or right by 1 1 1 without passing through coordinates where a stone is placed.
计算没有放置石头的格子点 ( x , y ) (x,y) (x,y) 的数量，并且通过反复向上、向下、向左或向右移动 1 1 1 而不通过放置石头的坐标，不可能从 ( x , y ) (x,y) (x,y) 到达 ( − 1 , − 1 ) (-1,-1) (−1,−1)。
More precisely, count the number of lattice points ( x , y ) (x,y) (x,y) where no stone is placed, and there does not exist a finite sequence of integer pairs ( x 0 , y 0 ) , … , ( x k , y k ) (x_0,y_0),…,(x_k,y_k) (x0,y0),…,(xk,yk) that satisfies all of the following four conditions:
更准确地说，计算没有放置石头的格点 ( x , y ) (x,y) (x,y) 的数量，并且不存在满足以下四个条件的整数对 ( x 0 , y 0 ) , … , ( x k , y k ) (x_0,y_0),…,(x_k,y_k) (x0,y0),…,(xk,yk) 的有限序列：
- ( x 0 , y 0 ) = ( x , y ) (x_0,y_0)=(x,y) (x0,y0)=(x,y).
- ( x k , y k ) = ( − 1 , − 1 ) (x_k,y_k)=(−1,−1) (xk,yk)=(−1,−1).
- ∣ x i − x i + 1 ∣ + ∣ y i − y i + 1 ∣ = 1 |x_i−x_i+1|+|y_i−y_i+1|=1 ∣xi−xi+1∣+∣yi−yi+1∣=1 for all 0 ≤ i < k 0≤i<k 0≤i<k.
- There is no stone at ( x i , y i ) (x_i,y_i) (xi,yi) for all 0 ≤ i ≤ k 0≤i≤k 0≤i≤k.
【Constraints】
- 0 ≤ N ≤ 2 × 1 0 5 0≤N≤2×10^5 0≤N≤2×105
- 0 ≤ X i , Y i ≤ 2 × 1 0 5 0≤X_i,Y_i≤2×10^5 0≤Xi,Yi≤2×105
- The pairs ( X i , Y i ) (X_i,Y_i) (Xi,Yi) are distinct.
- All input values are integers.
【Input】
The input is given from Standard Input in the following format:
N
X_1 Y_1
.
.
.
X_N Y_N
【Output】
Print the number of lattice points that satisfy the conditions.
【Sample Input 1】
5
1 0
0 1
2 3
1 2
2 1
【Sample Output 1】
1
It is impossible to reach ( − 1 , − 1 ) (−1,−1) (−1,−1) from ( 1 , 1 ) (1,1) (1,1).
【Sample Input 2】
0
【Sample Output 2】
0
【Sample Input 3】
22
0 1
0 2
0 3
1 0
1 4
2 0
2 2
2 4
3 0
3 1
3 2
3 4
5 1
5 2
5 3
6 0
6 4
7 0
7 4
8 1
8 2
8 3
【Sample Output 3】
6
There are six such points: ( 6 , 1 ) , ( 6 , 2 ) , ( 6 , 3 ) , ( 7 , 1 ) , ( 7 , 2 ) , ( 7 , 3 ) (6,1),(6,2),(6,3),(7,1),(7,2),(7,3) (6,1),(6,2),(6,3),(7,1),(7,2),(7,3).
【代码详解】
《AtCoder Go Territory》 #并查集# #双指针two-pointer#
#include <bits/stdc++.h>
using namespace std;
const int N = 200200, M=N<<3;
typedef pair<int, int> PII;
PII p[N];
vector<pair<int, int> > l[N];
int n, sz[M];
int h[M], e[M], ne[M], idx;
bool vis[M];
queue<int> q;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main()
{
cin >> n;
int MX=0, MY=0;
int x, y;
memset(h, -1, sizeof(h));
for (int i=1; i<=n; i++)
{
cin >> x >> y;
x = x+1, y = y+1;
p[i] = make_pair(x, y);
MX = max(MX, x);
MY = max(MY, y);
}
MX++; MY++;
sort(p+1, p+n+1);
for (int i=0, L=0; i<=MX; i++)
{
int R = L;
while (R+1<=N && p[R+1].first==i) ++R;
int Low = 0;
for (int j=L+1; j<=R; j++)
{
if (Low<p[j].second) l[i].push_back(make_pair(Low, p[j].second-1));
Low = p[j].second+1;
}
l[i].push_back(make_pair(Low, MY));
L = R;
}
int tot = 1;
for (int i=0; i<MX; i++)
{
int len = l[i].size();
int nxtlen = l[i+1].size();
for (int j=0,pos=0; j<len; j++)
{
int now = tot+j;
int L=l[i][j].first, R=l[i][j].second;
sz[now] = R-L+1;
while (pos<nxtlen && l[i+1][pos].second<L) ++pos;
while (pos<nxtlen && l[i+1][pos].second<=R)
{
int nxt = tot + len + pos;
add(now, nxt);
add(nxt, now);
++pos;
}
if (pos<nxtlen && l[i+1][pos].first<=R)
{
int nxt = tot+len+pos;
add(now, nxt);
add(nxt, now);
}
}
tot +=len;
}
q.push(1);
vis[1] = true;
while (!q.empty())
{
int u = q.front(); q.pop();
for (int i=h[u]; i!=-1; i=ne[i])
{
int j = e[i];
// cout << j << " " << vis[j] << endl;
if (vis[j]) continue;
vis[j] = true;
q.push(j);
}
}
long long ans = 0;
for (int i=1; i<=tot; i++)
if (!vis[i]) ans += sz[i];
cout << ans;
return 0;
}
【运行结果】
5
1 0
0 1
2 3
1 2
2 1
1