• 13967708449
  • 1322284500@qq.com

[Cqoi2010]内部白点

[Cqoi2010]内部白点

题意:

你有一个平面,然后你有一些黑点,然后内部白点(上下左右都有黑点的点)会被黑点染黑,询问最后有多少黑点……

分析:

我们发现所有被染黑的白点都是一开始上下左右都有黑点的点,然后我们把问题转换成了,上下左右都有黑点的点有多少个…..这个怎么求呢…..
当然我们先去哈希一下,得到了新的图,然后我们发现两个点在同一行,他们之间的点有可能被染黑,只要这些点上下也有黑点就好了,然后我们发现上下关系的黑点的贡献是一段,那么我们维护一个树状数组,从下往上枚举所有横线,然后维护竖线,当我们扫到下端点的时候,加入,扫到上端点时删除…..

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=2e5+10;
const LL mod=998244353;
const LL inf=0x3f3f3f3f;
const double eps=1e-12;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,totx,toty,ans,last;
struct Node{int x,y;}node[N];
bool cmp1(Node a,Node b){return a.x==b.x?a.y<b.y:a.x<b.x;}
bool cmp2(Node a,Node b){return a.y==b.y?a.x<b.x:a.y<b.y;}
P Ve[N];
vector<int> be[N],en[N],vec[N];
namespace BIT
{
    int xx[N*4];
    int lowbit(int now){return now&-now;}
    void change(int now,int v){for(;now<=n;now+=lowbit(now)) xx[now]+=v;}
    int query(int now,int ret=0){for(;now;now-=lowbit(now)) ret+=xx[now];return ret;}
}
using namespace BIT;
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(node[i].x),read(node[i].y);
    sort(node+1,node+n+1,cmp2);last=-inf;
    for(int i=1;i<=n;i++)
    {
        if(last==node[i].y) node[i].y=node[i-1].y;
        else last=node[i].y,node[i].y=++toty;
    }
    sort(node+1,node+n+1,cmp1);last=-inf;
    for(int i=1;i<=n;i++) 
    {
        if(last==node[i].x) node[i].x=node[i-1].x;
        else last=node[i].x,node[i].x=++totx;
        vec[node[i].y].push_back(node[i].x);
        Ve[node[i].x].first = (Ve[node[i].x].first==0?node[i].y:min(node[i].y,Ve[node[i].x].first));
        Ve[node[i].x].second = (Ve[node[i].x].second==0?node[i].y:max(node[i].y,Ve[node[i].x].second));
    }
    for(int i=1;i<=totx;i++) 
        if(Ve[i].second-1>Ve[i].first)
            be[Ve[i].first].push_back(i),en[Ve[i].second-1].push_back(i);
    for(int i=1;i<=toty;i++)
    {
        int siz=vec[i].size();for(int j=1;j<siz;j++)
            ans += query(vec[i][j]-1) - query(vec[i][j-1]);
        siz=be[i].size();for(int j=0;j<siz;j++) change(be[i][j],1);
        siz=en[i].size();for(int j=0;j<siz;j++) change(en[i][j],-1);
    }
    printf("%d\n",ans+n);
    return 0;
}
feluamn

[Cqoi2010]内部白点》上有2条评论

LMOliver发布于2:41 下午 - 11月 9, 2018

明天就要NOIP了

好慌啊

留下您的信息