首页 > 代码库 > 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]内部白点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。