首页 > 代码库 > BZOJ 1818: [Cqoi2010]内部白点

BZOJ 1818: [Cqoi2010]内部白点

Description

如果一个点左右上下都有黑点,那么这个点也会变成黑点,问最后有多少个黑点\(n\leqslant 10^5\).

Solution

扫描线.

显然变化后的点并不会产生新点,因为他的产生就需要他上下左右有点。

可以把他们转化成一些横纵的互不相交的直线...然后求交点个数...就是扫描线...

Code

/**************************************************************    Problem: 1818    User: BeiYu    Language: C++    Result: Accepted    Time:1672 ms    Memory:16532 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; const int N = 300050; inline int in(int x=0,char s=getchar(),int v=1) { while(s>‘9‘||s<‘0‘)v=s==‘-‘?-1:v,s=getchar();    while(s>=‘0‘&&s<=‘9‘)x=x*10+s-‘0‘,s=getchar();return x*v; } int n,cp,cl,cy,ans;int yy[N];pair<int,int> pp[N];struct P { int x,y,f; }p[N];struct L { int x,y1,y2; }l[N]; int cmpp(const P &a,const P &b) { return a.x==b.x?a.f>b.f:a.x<b.x; }int cmpl(const L &a,const L &b) { return a.x<b.x; } void Add1(L a) { p[++cp]=(P) { a.y1,a.x,1 },p[++cp]=(P) { a.y2,a.x,-1 }; }void Add2(L a) { l[++cl]=a; }int Qy(int x) { return lower_bound(yy+1,yy+cy+1,x)-yy; } namespace Seg {    int d[N<<2];         #define lc (o<<1)    #define rc (o<<1|1)    #define mid ((l+r)>>1)         void Update(int o) { d[o]=d[lc]+d[rc]; }    void Add(int o,int l,int r,int x,int v) {//      cout<<o<<" "<<l<<" "<<r<<" "<<x<<" "<<v<<endl;        if(l==r) { d[o]+=v;return; }        if(x<=mid) Add(lc,l,mid,x,v);        else Add(rc,mid+1,r,x,v);        Update(o);    }    int Qur(int o,int l,int r,int L,int R) {//      cout<<o<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<endl;        if(L<=l && r<=R) return d[o];        int res=0;        if(L<=mid) res+=Qur(lc,l,mid,L,R);        if(R>mid) res+=Qur(rc,mid+1,r,L,R);        return res;    }}; int main() {    n=in();    for(int i=1;i<=n;i++) {        int x=in(),y=in();        pp[i]=make_pair(x,y);        yy[++cy]=y,yy[++cy]=y-1,yy[++cy]=y+1;    }    sort(yy+1,yy+cy+1);    cy=unique(yy+1,yy+cy+1)-yy-1;    for(int i=1;i<=n;i++) pp[i].second=Qy(pp[i].second);    sort(pp+1,pp+n+1);    for(int i=1,j;i<=n;i=j+1) {        for(j=i;j<=n && pp[i].first==pp[j+1].first;j++);        for(int k=i;k<j;k++) Add2((L) { pp[k].first,pp[k].second+1,pp[k+1].second-1 });    }    for(int i=1;i<=n;i++) swap(pp[i].first,pp[i].second);    sort(pp+1,pp+n+1);    for(int i=1,j;i<=n;i=j+1) {        for(j=i;j<=n && pp[i].first==pp[j+1].first;j++);        for(int k=i;k<j;k++) if(pp[k].second+1<=pp[k+1].second-1)            Add1((L) { pp[k].first,pp[k].second+1,pp[k+1].second-1 });         }    sort(p+1,p+cp+1,cmpp);    sort(l+1,l+cl+1,cmpl);     /*  cout<<cp<<endl;    for(int i=1;i<=cp;i++) cout<<p[i].x<<" "<<p[i].y<<" "<<p[i].f<<endl;     cout<<cl<<endl;    for(int i=1;i<=cl;i++) cout<<l[i].x<<" "<<l[i].y1<<" "<<l[i].y2<<endl;*/         for(int i=1,j,k=1;i<=cl;i=j+1) {        for(;k<=cp&&(p[k].x<l[i].x||(p[k].x==l[i].x&&p[k].f>0));k++) Seg::Add(1,1,cy,p[k].y,p[k].f);        for(j=i;j+1<=cl && l[i].x==l[j+1].x;j++);        for(int t=i;t<=j;t++) ans+=Seg::Qur(1,1,cy,l[t].y1,l[t].y2);        for(;k<=cp && p[k].x==l[i].x;k++) Seg::Add(1,1,cy,p[k].y,p[k].f);    }printf("%d\n",ans+n);    return 0;}

  

BZOJ 1818: [Cqoi2010]内部白点