解题思路 比赛的时候写了扫描线，但TLE了，原因是只要用异或维护奇偶就可以了，我们扫描每一行，更新线段树的奇偶，然后维护区间是奇数的长度即可。如果这次修改的话，那么现在奇数的长度就是原来偶数的长度。然后答案加上tree[1]即可。 AC代码
#include <iostream> #include <stdio.h> #include <cstring> #include <algorithm> #include <vector> #define lc k<<1 #define rc k<<1|1 using namespace std; const int N=1e4+5; int T,n,k; struct node { int lx,rx; }; vector<node>v[N]; int lazy[N<<2],tree[N<<2]; void push_up(int k) { tree[k]=tree[lc]+tree[rc]; } void build(int l,int r,int k) { lazy[k]=tree[k]=0; if(l==r) return ; int mid=(l+r)>>1; build(l,mid,lc); build(mid+1,r,rc); } void push_down(int l,int r,int k) { if(lazy[k]) { lazy[k]=0; int mid=(l+r)>>1; tree[lc]=mid-l+1-tree[lc]; tree[rc]=r-mid-tree[rc]; lazy[lc]^=1; lazy[rc]^=1; } } void update(int l,int r,int k,int ll,int rr) { if(ll<=l&&rr>=r) { tree[k]=r-l+1-tree[k]; lazy[k]^=1; return ; } push_down(l,r,k); int mid=(l+r)>>1; if(ll<=mid) update(l,mid,lc,ll,rr); if(rr>mid) update(mid+1,r,rc,ll,rr); push_up(k); } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) v[i].clear(); while(k--) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); v[c].push_back({a,b}); v[d+1].push_back({a,b}); } build(1,n,1); int ans=0; for(int i=1;i<=n;++i) { for(int j=0;j<v[i].size();++j) { int lx=v[i][j].lx; int rx=v[i][j].rx; update(1,n,1,lx,rx); } ans+=tree[1]; } printf("%d\n",ans); } return 0; }