题目链接：https://www.luogu.org/problem/P1884
题目大意：给你n个矩阵，让你求矩阵面积的并
解题报告：线段树扫描线裸题，需要用到左闭右开的性质。
AC代码：
将多组输入改为单组
1 #include<bits/stdc++.h> 2 #define numm ch-48 3 #define pd putchar(' ') 4 #define pn putchar(' ') 5 #define debug(args...) cout<<#args<<"->"<<args<<endl 6 #define bug cout<<"************" 7 using namespace std; 8 template <typename T> 9 void read(T &res) { 10 bool flag=false;char ch; 11 while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true); 12 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm); 13 flag&&(res=-res); 14 } 15 template <typename T> 16 void write(T x) { 17 if(x<0) putchar('-'),x=-x; 18 if(x>9) write(x/10); 19 putchar(x%10+'0'); 20 } 21 typedef long long ll; 22 const int maxn=210; 23 const int inf=0x3f3f3f3f; 24 const ll maxx=1e9; 25 ll dis[maxn]; 26 struct node { 27 ll l,r,y; 28 int d; 29 node(){} 30 node(ll a,ll b,ll c,int d): l(a),r(b),y(c),d(d){} 31 bool operator <(const node &a) { 32 return y<a.y; 33 } 34 }e[maxn]; 35 struct ST { 36 ll s; 37 int tag; 38 }st[maxn<<2]; 39 #define ls (k<<1) 40 #define rs (k<<1|1) 41 void pushup(int k,int l,int r) { 42 if(st[k].tag) st[k].s=dis[r+1]-dis[l];///[,),区间左闭右开 43 else if(l==r) st[k].s=0; 44 else st[k].s=st[ls].s+st[rs].s; 45 return ; 46 } 47 void update(int l,int r,int ql,int qr,int c,int k) { 48 if(ql<=l&&r<=qr) { 49 st[k].tag+=c; 50 pushup(k,l,r); 51 return ; 52 } 53 int mid=(l+r)>>1; 54 if(mid>=ql) update(l,mid,ql,qr,c,ls); 55 if(mid<qr) update(mid+1,r,ql,qr,c,rs); 56 pushup(k,l,r); 57 return ; 58 } 59 void build(int k,int l,int r) { 60 st[k].s=0; 61 st[k].tag=0; 62 if(l>=r) 63 return ; 64 int mid=(l+r)>>1; 65 build(ls,l,mid); 66 build(rs,mid+1,r); 67 return ; 68 } 69 int main() 70 { 71 int n,cnt=0; 72 while(scanf("%d",&n)!=EOF) { 73 cnt=0; 74 for(int i=1;i<=n;i++) { 75 ll x1,x2,y1,y2; 76 read(x1),read(y1),read(x2),read(y2); 77 dis[++cnt]=x1;e[cnt]=node(x1,x2,y1,1); 78 dis[++cnt]=x2;e[cnt]=node(x1,x2,y2,-1); 79 } 80 sort(dis+1,dis+1+cnt); 81 sort(e+1,e+1+cnt); 82 int tot=unique(dis+1,dis+1+cnt)-dis-1; 83 build(1,1,tot); 84 ll ans=0; 85 for(int i=1;i<cnt;i++) { 86 int l=lower_bound(dis+1,dis+1+tot,e[i].l)-dis; 87 int r=lower_bound(dis+1,dis+1+tot,e[i].r)-dis-1; 88 if(l<=r) update(1,tot,l,r,e[i].d,1); 89 ans+=st[1].s*(e[i+1].y-e[i].y); 90 } 91 write(ans);pn; 92 } 93 return 0; 94 }