首页 > 代码库 > poj 3109 Inner Vertices(树状数组）
poj 3109 Inner Vertices(树状数组）
| Time Limit: 5000MS | Memory Limit: 65536K | |
| Total Submissions: 1692 | Accepted: 446 | |
| Case Time Limit: 2000MS | ||
Description
There is an infinite square grid. Some vertices of the grid are black and other vertices are white.
A vertex V is called inner if it is both vertical-inner and horizontal-inner. A vertex V is called horizontal-inner if there are two such black vertices in the same row that V is located between them. A vertex V is called vertical-inner if there are two such black vertices in the same column that V is located between them.
On each step all white inner vertices became black while the other vertices preserve their colors. The process stops when all the inner vertices are black.
Write a program that calculates a number of black vertices after the process stops.
Input
The first line of the input file contains one integer number n (0 ≤ n ≤ 100 000) — number of black vertices at the beginning.
The following n lines contain two integer numbers each — the coordinates of different black vertices. The coordinates do not exceed 109 by their absolute values.
Output
Output the number of black vertices when the process stops. If the process does not stop, output -1.
Sample Input
4 0 2 2 0 -2 0 0 -2
Sample Output
5
Hint
看了一天多的别人的代码：http://blog.csdn.net/z309241990/article/details/38638243，太弱了
预处理标记第i个点是最上面的还是最下面的点，如果是最下面的点且不是最下面的点，就增加一列被染色的点，
如果是最上面的点且不是最下方的点，肯定少一列被染色的点，最后以y坐标为扫描线，看这段区间有几列被染
色。
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=200000+100;
struct node
{
int x;
int y;
}p[maxn];
int a[maxn];
int b[maxn];
int n,cur;
bool vis[maxn],l[maxn],r[maxn];
bool cmp(node u,node v)
{
if(u.y==v.y)
return u.x<v.x;
return u.y<v.y;
}
int low(int k)
{
return k&(-k);
}
void update(int k,int v)
{
while(k<maxn)
{
a[k]+=v;
k+=low(k);
}
}
long long sum(int k)
{
long long ans=0;
while(k>0)
{
ans+=a[k];
k-=low(k);
}
return ans;
}
void init()//预处理
{
memset(a,0,sizeof(a));//初始化树状数组
sort(b,b+cur);
cur=unique(b,b+cur)-b;//排序，离散化
for(int i=0;i<n;i++)
{
p[i].x=lower_bound(b,b+cur,p[i].x)-b+1;
p[i].y=lower_bound(b,b+cur,p[i].y)-b+1;
}
sort(p,p+n,cmp);//按y排序，已y坐标建扫描线
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
if(!vis[p[i].x])//预处理，k位置在下方第一次出现
{
l[i]=1;
vis[p[i].x]=1;
}
else
l[i]=0;
}
memset(vis,0,sizeof(vis));
for(int i=n-1;i>=0;i--)
{
if(!vis[p[i].x])//第k个点的x坐标在上方出现第一次出现
{
r[i]=1;
vis[p[i].x]=1;
}
else
r[i]=0;
}
}
void solve()
{
long long ans=0;
for(int i=0;i<n;)
{
int j=i;
while(j<n-1&&p[j].y==p[j+1].y)//同一条扫描线
j++;
for(int k=i;k<=j;k++)
{
if(!l[k]&&r[k])// 最上面的点，且下面存在被染色的点
{
update(p[k].x,-1);
}
}
if(i!=j)
ans+=(sum(p[j].x-1)-sum(p[i].x));//p[j].x-1到p[i].x间被改变颜色的点
if(i<j)
{
for(int k=i+1;k<j;k++)
if(!l[k]&&!r[k])//原来是黑色的点
ans--;
}
while(i<=j)
{
if(l[i]&&!r[i])//p[i].x是最底下的位置，且上面有元素，p[i].x上的要被染色
update(p[i].x,1);
i++;
}
}
printf("%I64d\n",ans+n);
}
int main()
{
while(~scanf("%d",&n))
{
cur=0;
for(int i=0;i<n;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
b[cur++]=p[i].x;
b[cur++]=p[i].y;
}
init();
solve();
}
return 0;
}
poj 3109 Inner Vertices(树状数组）