2017ICPC hongkang B题Black and White（线段树线扫描）

计蒜客题目：https://nanti.jisuanke.com/t/19926

Considerasquaremapwith N \times NN×N cells. We indicate the coordinate of a cell by(i,j)(i,j),where 1 \le i,j \le N1≤i,j≤N. Each cell has a color either white or black. The color of each cell is initialized to white. The map supports the operation flip([x_{low}, x_{high}], [y_{low}, y_{high]})([xlow​,xhigh​],[ylow​,yhigh]​), which flips the color of each cell in the rectangle [x_{low}, x_{high}] \times [y_{low}, y_{high}][xlow​,xhigh​]×[ylow​,yhigh​]. Given a sequence of flip operations, our problem is to count the number of black cells in the final map. We illustrate this in the following example. Figure (a)(a)shows the initial map. Next, we call flip([2,4],[1,3])([2,4],[1,3]) and obtain Figure (b)(b). Then, we call f lip([1, 5], [3, 5])([1,5],[3,5]) and obtain Figure (c)(c). This map contains 1818 black cells.

Input

The first line contains the number of test cases T (T < 10)T(T<10). Each test case begins with a line containing two integers NN and K (1 < N,K < 10000)K(1<N,K<10000), where NN is the parameter of the map size and KK is the number of flip operations. Each subsequent line corresponds to a flip operation, with four integers: x_{low}x_{high}xlow​xhigh​, y_{low}, y_{high}ylow​,yhigh​.

Output

For each test case, output the answer in aa line.

样例输入

1
5 2
2 4 1 3
1 5 3 5

样例输出

18

题目来源

ACM-ICPC 2017 Asia HongKong

【分析】

以前做过矩形面积并的题目，有点像，只不过这个题只要相交就 异或1，抵消。

线段树模板，只改动了nodeupdate函数

【代码】

#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 l,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,l,r,num);
        return;
    }
    pushdown(root,l,r);
    int mid=(l+r)/2;
    if(kl<=mid)
        update(kl,kr,num,root*2,l,mid);
    if(kr>mid)
        update(kl,kr,num,root*2+1,mid+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,0,sizeof(sum));
        memset(mark,0,sizeof(mark));
        cnt=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
            e[cnt++]=node{y1,x1,x2,1};
            e[cnt++]=node{y2,x1,x2,-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,e[j].b,1);
                j++;
            }
        }
        cout<<ans<<endl;
    }
}