少买笑傲

#include<bits/stdc++.h>using namespace std;typedef long long ll; int n;int sum[40000];int mark[40000];void nodeupdate(int root,int l,int r,ll num){ mark[root]^=1; sum[root]=(r-l+1)-sum[root];}void pushdown(int root,int r)//传递给两孩子{ if(mark[root]==0)return; int mid=(l+r)/2; nodeupdate(root*2,l,mid,mark[root]); nodeupdate(root*2+1,mid+1,r,mark[root]); mark[root]=0;}void update(int kl,int kr,ll num,int root=1,int l=1,int r=n)//区间[kl,kr]修改{ if(kl<=l&&r<=kr){ nodeupdate(root,num); return; } pushdown(root,r); int mid=(l+r)/2; if(kl<=mid) update(kl,kr,num,root*2,mid); if(kr>mid) update(kl,root*2+1,r); sum[root]=sum[root*2]+sum[root*2+1];} struct node{ int h,a,b,flag;}e[404040];int cnt=0;bool cmp(node a,node b){ if(a.h==b.h)return a.flag>b.flag; return a.h<b.h;}int main(){ int T,m,x1,x2,y1,y2; cin>>T; while(T--) { cin>>n>>m; memset(sum,sizeof(sum)); memset(mark,sizeof(mark)); cnt=0; for(int i=0;i<m;i++) { scanf("%d%d%d%d",&x1,&x2,&y1,&y2); e[cnt++]=node{y1,1}; e[cnt++]=node{y2,-1}; } sort(e,e+cnt,cmp); int ans=0; for(int i=1,j=0;i<=n;i++) { while(j<cnt&&e[j].h<=i&&e[j].flag==1){ update(e[j].a,e[j].b,1); j++; } ans+=sum[1]; while(j<cnt&&e[j].h<=i){ update(e[j].a,1); j++; } } cout<<ans<<endl; }}