1. General topic
On the Go board, if there are chess pieces in the four directions of a certain coordinate, up, down, left, and right, then ans + 1. According to the number of input chess pieces, find the number of ans.
2. Problem-solving ideas
The question mentions that if the program does not end, then -1 is output. This is actually passive water and will not happen at all.
We can loop column by column, and then build a tree array for the column (line segment trees are also acceptable, tree arrays are faster)
The coordinates are relatively large and need to be discretized (discretization is an algorithm that sorts the effective coordinates and places them in the array, and then replaces the original coordinates with the corresponding numbers of the original coordinates and the order of the array elements. You can refer to “Challenge Programming” Chapter 3 – Selection of commonly used techniques, or you can refer to my humble work solution to AOJ0531) The x and y input for each chess piece in this question are valid coordinates, and the other coordinates are invalid, because rows or columns without chess pieces must not allow ans + 1 .
Then sort according to the columns. If the columns are the same, sort according to the rows (pair defaults to rows, first column, second row)
Then record the coordinates of the last chess piece in each row (you can define an array, set the initial value to 1 or 0, cycle through all the chess pieces, and update to the maximum column of each row)
Then, record a bool type tag array at the same time to represent whether there is a chess piece in front of a certain row, as shown below
When looping through each column, collectively add 1 to the elements between the current element and the previous element in the current column (tree array operation) update (the column of the previous element + 1, the column of the current element -1, 1) needs to be judged here. The size of the previous column + 1 and the current column – 1. If it is greater than or equal to the size, do not update it.
When encountering the first chess piece in each row at the same time, mark this row, and then update the position of this row to 0 (updated to 0 because there is no chess piece on the left before this row, if there is no chess piece on the left, then these + 1 situations , even if there are pieces above and below, they should not be recorded in the answer, in order to prevent the position of the red arrow in the picture below from being recorded incorrectly), so that next time you encounter this line of chess pieces, it can represent the part between the two. The location can be added to the answer.
Then when updating to the last column of each row (here you can judge whether it is the last column through the array of the largest column of the previously recorded row), if this row has not been marked before, that is, there is no chess piece to the left of the last chess piece in this row, then The coordinates of + 1 in this line do not count. There are subs up and down, and also on the right, but if there are no subs on the left, it will not work, so just continue.
If this row has been marked, then there is a chess piece on the left side of the table, and the last chess piece in the row looped to is on its right, and then the interval boundary when updating the tree array is above and below it, then the tree array finds this row The number needs to be added to ans. My idea is as shown in the figure below. Some numbers on the right side of each column are the tree arrays that are rendered to normal when passing through a certain column (the non-tree summation ones) ), then the red arrow means that you have reached the last column of a certain row and increased ans.
Sorry for the unclear expression!
3. Code
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
Pnum[100010];
ll bit0[131080], bit1[131080], ans;
int x[100010], y[100010], xLen, yLen, n, n_, maxCol[100010];
bool activeRow[100010];
void input()
{
for (int i = 1; i <= n_; i + + )
{
scanf("%d%d", & num[i].first, & num[i].second);
x[i] = num[i].first;
y[i] = num[i].second;
activeRow[i] = false;
maxCol[i] = 1;
}
sort(x + 1, x + (1 + n_));
sort(y + 1, y + (1 + n_));
}
void compress()
{
xLen = 1;
yLen = 1;
for (int i = 2; i <= n_; i + + )
{
if (x[xLen] != x[i])
{
x[ + + xLen] = x[i];
}
if (y[yLen] != y[i])
{
y[ + + yLen] = y[i];
}
}
for (int i = 1; i <= n_; i + + )
{
num[i].first = lower_bound(x + 1, x + (xLen + 1), num[i].first) - x;
num[i].second = lower_bound(y + 1, y + (yLen + 1), num[i].second) - y;
if (maxCol[num[i].second] < num[i].first)
{
maxCol[num[i].second] = num[i].first;
}
}
}
void init()
{
n = 131072;
for (int i = 0; i <= n; i + + )
{
bit0[i] = 0LL;
bit1[i] = 0LL;
}
}
void updateBit0(int r, ll v)
{
if (r <= 0)
{
return;
}
for (int i = r; i <= n; i = i + (i & amp; (-i)))
{
bit0[i] = bit0[i] + v;
}
}
void updateBit1(int r, ll v)
{
if (r <= 0)
{
return;
}
for (int i = r; i <= n; i = i + (i & amp; (-i)))
{
bit1[i] = bit1[i] + v;
}
}
ll queryBit0(int r)
{
ll sum = 0LL;
for (int i = r; i > 0; i = i - (i & amp; (-i)))
{
sum = sum + bit0[i];
}
return sum;
}
ll queryBit1(int r)
{
ll sum = 0LL;
for (int i = r; i > 0; i = i - (i & amp; (-i)))
{
sum = sum + bit1[i];
}
return sum;
}
void update(int l, int r, ll v)
{
updateBit0(l, (-1LL) * v * ((ll)(l - 1)));
updateBit0(r + 1, v * ((ll)r));
updateBit1(l, v);
updateBit1(r + 1, (-1LL) * v);
}
ll query(int l, int r)
{
ll allAmt = queryBit0(r);
ll allAdd = queryBit1(r) * ((ll)r);
ll leftAmt = queryBit0(l - 1);
ll leftAdd = queryBit1(l - 1) * ((ll)(l - 1));
return (allAmt + allAdd - leftAmt - leftAdd);
}
void solve()
{
sort(num + 1, num + (1 + n_));
ans = 0LL;
for (int i = 1; i <= n_; i + + )
{
if (i > 1 & amp; & amp; num[i - 1].first == num[i].first & amp; & amp; (num[i - 1].second + 1) < num[i] .second)
{
update(num[i - 1].second + 1, num[i].second - 1, 1LL);
}
if (maxCol[num[i].second] == num[i].first & amp; & amp; !activeRow[num[i].second])
{
continue;
}
if (maxCol[num[i].second] == num[i].first & amp; & amp; activeRow[num[i].second])
{
ans = ans + query(num[i].second, num[i].second);
}
if (!activeRow[num[i].second])
{
ll oldVal = query(num[i].second, num[i].second);
update(num[i].second, num[i].second, (-1LL) * oldVal);
activeRow[num[i].second] = true;
}
}
}
int main()
{
while (~scanf("%d", & amp;n_))
{
input();
compress();
init();
solve();
ans = ans + ((ll)n_);
printf("%lld\
", ans);
}
return 0;
}