首页 > 代码库 > BZOJ 1818 内部白点
BZOJ 1818 内部白点
扫描线。
cmp不要乱打。。。。。最后一个一定不要if直接return。
感谢http://hzwer.com/1836.html
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100500 using namespace std; int n,hash[maxn],top=0,t[maxn],cnt=0; struct pnt { int x,y; }p[maxn]; struct query { int y,l,r,x,type; }q[maxn*10]; bool cmp1(pnt x,pnt y) { if (x.y!=y.y) return x.y<y.y; return x.x<y.x; } bool cmp2(pnt x,pnt y) { if (x.x!=y.x) return x.x<y.x; return x.y<y.y; } bool cmp3(query x,query y) { if (x.y!=y.y) return x.y<y.y; return x.type<y.type; } int find(int x) { return lower_bound(hash+1,hash+top+1,x)-hash; } void addq(int x,int y,int type) { if (type==0) { cnt++; q[cnt].y=p[x].y;q[cnt].type=type;q[cnt].x=0; q[cnt].l=find(p[x].x);q[cnt].r=find(p[y].x); } else { cnt++; q[cnt].y=p[x].y;q[cnt].type=type; q[cnt].x=find(p[x].x);q[cnt].l=q[cnt].r=0; } } void build_line() { sort(p+1,p+n+1,cmp1); for (int i=2;i<=n;i++) { if (p[i-1].y==p[i].y) addq(i-1,i,0); } sort(p+1,p+n+1,cmp2); for (int i=2;i<=n;i++) { if (p[i-1].x==p[i].x) { addq(i-1,0,1); addq(i,0,-1); } } sort(q+1,q+cnt+1,cmp3); } int lowbit(int x) { return (x&(-x)); } void modify(int x,int val) { for (int i=x;i<=top;i+=lowbit(i)) t[i]+=val; } int ask(int x) { int ret=0; for (int i=x;i>=1;i-=lowbit(i)) ret+=t[i]; return ret; } void get_ans() { int ans=0; for (int i=1;i<=cnt;i++) { if (q[i].type==-1) modify(q[i].x,-1); else if (q[i].type==1) modify(q[i].x,1); else ans+=ask(q[i].r-1)-ask(q[i].l); } printf("%d\n",ans+n); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d%d",&p[i].x,&p[i].y); hash[++top]=p[i].x; } sort(hash+1,hash+top+1);top=unique(hash+1,hash+top+1)-hash-1; build_line(); get_ans(); return 0; }
BZOJ 1818 内部白点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。