题意：给你一些坐标，代表篱笆的顶点和或者蔬菜，问你篱笆外面的蔬菜价值几何？
思路：扫描线+线段树或树装数组
鉴于这道题找了四五个小时的bug，还是写出来庆祝一下终于到来的AC；
因为这里坐标太大了，按照惯例离散一下，那我就从下面往上面扫，因为不是多个图形的叠加，没有必要标注上下边，而且很难分辨上下边（当然我开始写的时候是很傻逼想标来着，后来想到计算奇数偶数即可啊），这样的话，就用线段树维护一下区间即可，复杂度nlogn，排出bug，一身轻松~~~
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; const LL INF=0x3f3f3f3f; const int maxn=1e5+20; int n,m,cntx,cntp,c[maxn<<1]; LL x[maxn<<1]; struct point { LL l,r,h;int k,v; point(LL _l=0,LL _r=0,LL _h=0,int _k=0,int _v=0):l(_l),r(_r),h(_h),k(_k),v(_v){} bool operator <(const point &r)const{return h<r.h;} }p[maxn<<1]; void add(LL *xx,LL *yy) { if(yy[0]==yy[1]) p[cntp++]=point(min(xx[0],xx[1]),max(xx[0],xx[1]),yy[0],1,0); } int Lowbit(int x){return x&(-x);} void update(int i,int x) { while(i>0) { c[i]+=x; i-=Lowbit(i); } } int sum(int x,int tol) { int sum=0; while(x<=tol) { sum+=c[x]; x+=Lowbit(x); } return sum; } int main() { //freopen("F_37.in","r",stdin); while(scanf("%d%d",&n,&m)!=EOF) { cntp=0,cntx=1; LL xx[2],yy[2],tx,ty; for(int i=0;i<n;i++) { scanf("%I64d%I64d",&xx[0],&yy[0]); p[cntp++]=point(xx[0],yy[0],yy[0],0,i+1); x[cntx++]=xx[0]; } scanf("%I64d%I64d",&xx[0],&yy[0]); tx=xx[0],ty=yy[0];x[cntx++]=xx[0]; for(int i=1;i<m;i++) { scanf("%I64d%I64d",&xx[1],&yy[1]); x[cntx++]=xx[1];add(xx,yy); xx[0]=xx[1],yy[0]=yy[1]; } xx[1]=tx,yy[1]=ty; add(xx,yy);x[0]=-1e10; sort(x,x+cntx); sort(p,p+cntp); int tol=2; for(int i=2;i<cntx;i++) if(x[i]!=x[i-1]) x[tol++]=x[i]; memset(c,0,(m+n+10)*sizeof(int)); LL ans=0; for(int i=0;i<cntp;i++) { if(p[i].k) { int tl=lower_bound(x,x+tol,p[i].l)-x; int tr=lower_bound(x,x+tol,p[i].r)-x; update(tr-1,1);update(tl-1,-1); } else { int tx=lower_bound(x,x+tol,p[i].l)-x; if(!(sum(tx,tol)&1))ans+=1LL*p[i].v; } } printf("%I64d ",ans); } return 0; }