【upc】2020年秋季组队训练赛第十五场 Black and White | 扫描线 + 线段树

问题 B: Black and White

时间限制: 1 Sec  内存限制: 128 MB
提交 状态

题目描述

Consider a square map with N × N cells. We indicate the coordinate of a cell by (i, j), where 1 ≤ 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([xlow , xhigh], [ylow , yhigh]), which flips the color of each cell in the rectangle [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) shows the initial map. Next, we call flip([2, 4], [1, 3]) and obtain Figure (b). Then, we call flip([1, 5], [3, 5]) and obtain Figure (c). This map contains 18 black cells.

输入

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

输出

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

样例输入 Copy

1   
5 2  
2 4 1 3
1 5 3 5

样例输出 Copy

18

题目大意：

每次翻转一个矩形内的灯的状态，最后询问矩形内有多少灯亮着

题目思路：

扫描线，扫描当前一行内有多少灯是亮着的

用线段树维护区间0变1 ， 1变0即可

因为无论是增加覆盖次数，或者减少覆盖次数 都会使得奇偶性发生改变

所以用线段树维护1的数量即可

Code:

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef  long long ll;
typedef unsigned long long ull;
const ll INF= 1e18;
const int maxn = 1e5;
const int mod= 998244353;
inline bool read(ll &num)
{char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
vector<pair<int,int>>v[maxn];
ll sum[maxn];
int lazy[maxn];
void push(int k){sum[k] = sum[k<<1] + sum[k<<1|1];
}
void build(int k,int l,int r){sum[k] = lazy[k] = 0;if(l == r) return ;int mid = (l+r)/2;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void down(int k,int l,int r){int mid = (l+r)/2;if(lazy[k]){lazy[k<<1] ^=1;lazy[k<<1|1] ^= 1;sum[k<<1] = (mid-l+1)-sum[k<<1];sum[k<<1|1] = (r-mid) - sum[k<<1|1];lazy[k] = 0;}
}
void Modify(int k,int l,int r,int x,int y){if(x<=l && y>=r){sum[k] = r-l+1 - sum[k];lazy[k] ^= 1;return;}down(k,l,r);int mid = (l+r)/2;if(x<=mid) Modify(k<<1,l,mid,x,y);if(y>mid) Modify(k<<1|1,mid+1,r,x,y);push(k);
}
int main(){int T;scanf("%d",&T);while(T--){read(n);read(m);for(int i=0;i<=10000;i++) v[i].clear();for(int i=1;i<=m;i++){int ax,ay,bx,by;scanf("%d%d%d%d",&ax,&bx,&ay,&by);v[ax].push_back({ay,by});v[bx+1].push_back({ay,by});}ll ans = 0;build(1,1,10000);for(int i=1;i<=10000;i++){for(auto x:v[i]) Modify(1,1,n,x.first,x.second);ans += sum[1];}printf("%lld\n",ans);}return 0;
}
/***
1
4 2
1 3 1 3
2 4 2 4
***/