title: 十六届蓝桥杯-JavaA组T.H奇偶覆盖tags: ACM
abbrlink: 72bd2125
date: 2020-11-17 18:01:26

线段树初步版本，未完善

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. const int N=1e5+5;
  7. struct node
  8. {
  9.     int l,r,h;
  10.     bool operator< (const node& a)const
  11.     {
  12.         return h<a.h;
  13.     }
  14. }e[N*2];
  16. int a[N*2];
  17. int sum[N*2*4],flag[N*2*4];
  19. void cal(int l,int r,int root)
  20. {
  21.     sum[root]=(a[r]-a[l])-sum[root];
  22. }
  24. void pushup(int root)
  25. {
  26.     sum[root]=sum[root<<1]+sum[root<<1|1];
  27. }
  29. void pushdown(int l,int r,int root)
  30. {
  31.     if(!flag[root])
  32.         return ;
  33.     flag[root<<1]^=1;
  34.     flag[root<<1|1]^=1;
  35.     int mid=l+r>>1;
  36.     cal(l,mid,root<<1);
  37.     cal(mid,r,root<<1|1);
  38.     flag[root]=0;
  39. }
  41. void update(int l,int r,int root,int ql,int qr)
  42. {
  43.     if(l>=ql&&r<=qr)
  44.     {
  45.         cal(l,r,root);
  46.         flag[root]^=1;
  47.         return ;
  48.     }
  49.     pushdown(l,r,root);
  50.     int mid=l+r>>1;
  51.     if(mid>ql)
  52.         update(l,mid,root<<1,ql,qr);
  53.     if(mid<qr)
  54.         update(mid,r,root<<1|1,ql,qr);
  55.     pushup(root);
  56. }
  58. int main()
  59. {
  60.     int n;
  61.     scanf("%d",&n);
  62.     int x1,x2,y1,y2,all=0;
  63.     for(int i=1;i<=n;i++)
  64.     {
  65.         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
  66.         e[2*i-1].l=min(x1,x2);
  67.         e[2*i-1].r=max(x1,x2);
  68.         e[2*i-1].h=min(y1,y2);
  69.         e[2*i].l=min(x1,x2);
  70.         e[2*i].r=max(x1,x2);
  71.         e[2*i].h=max(y1,y2);
  72.         a[2*i-1]=x1,a[2*i]=x2;
  73.     }
  74.     sort(a+1,a+1+n*2);
  75.     all=unique(a+1,a+1+n*2)-a-1;
  76.     for(int i=1;i<=2*n;i++)
  77.         e[i].l=lower_bound(a+1,a+1+all,e[i].l)-a,e[i].r=lower_bound(a+1,a+1+all,e[i].r)-a;
  78.     sort(e+1,e+1+2*n);
  79.     ll ans=0;
  80.     for(int i=1;i<=2*n;i++)
  81.     {
  82.         ans+=sum[1]*(e[i].h-e[i-1].h);
  83.         update(1,all,1,e[i].l,e[i].r);
  84.     }
  85.     printf("%lld\n",ans);
  86. }