2020-10-04线段树扫描线
http://icpc.upc.edu.cn/problem.php?cid=2590&pid=1
题目描述¶
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 ©. 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.
样例输入¶
样例输出¶
线段树+扫描线#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
int h,a,b,num;
};
int mark[100500]={0};
int sum[100500]={0};
node edge[100500]={0};
bool cmp(node a,node b)
{
if(a.h==b.h)
return a.num>b.num;
else
return a.h<b.h;
}
int nodeupdate(int root,int l,int r,ll num)
{
mark[root]^=1;
sum[root]=r-l+1-sum[root];
}
int pushdown(int root,int l,int r)
{
if(mark[root]==0)
return 0;
int mid=(l+r)/2;
nodeupdate(2*root,l,mid,mark[root]);
nodeupdate(2*root+1,mid+1,r,mark[root]);
mark[root]=0;
}
int update(int root,int l,int r,int L,int R,ll num)
{
if(l>=L&&r<=R)
{
nodeupdate(root,l,r,num);
return 0;
}
pushdown(root,l,r);
int mid=(l+r)/2;
if(mid>=L)
update(root*2,l,mid,L,R,num);
if(mid<R)
update(root*2+1,mid+1,r,L,R,num);
sum[root]=sum[2*root]+sum[2*root+1];
}
int main()
{
int t,cnt;
scanf("%d",&t);
while(t--)
{
memset(sum,0,sizeof(sum));
memset(mark,0,sizeof(mark));
int n,m,ans=0;
cnt=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
edge[cnt++]=node{y1,x1,x2,1};
edge[cnt++]=node{y2,x1,x2,-1};
}
sort(edge,edge+cnt,cmp);
for(int i=1,j=0;i<=n;i++)
{
while(j<cnt&&edge[j].h<=i&&edge[j].num==1)
{
update(1,1,n,edge[j].a,edge[j].b,1);
j++;
}
ans+=sum[1];
while(j<cnt&&edge[j].h<=i)
{
update(1,1,n,edge[j].a,edge[j].b,1);
j++;
}
}
cout<<ans<<endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
int h,a,b,num;
};
int mark[100500]={0};
int sum[100500]={0};
node edge[100500]={0};
bool cmp(node a,node b)
{
if(a.h==b.h)
return a.num>b.num;
else
return a.h<b.h;
}
int pushup(int root,int l,int r,ll num)
{
mark[root]^=num;
if(mark[root])
sum[root]=r-l+1;
else if(l==r)
sum[root]=0;
else
sum[root]=sum[2*root]+sum[2*root+1];
}
int pushdown(int root,int l,int r)
{
if(mark[root]==0)
return 0;
int mid=(l+r)/2;
pushup(2*root,l,mid,mark[root]);
pushup(2*root+1,mid+1,r,mark[root]);
mark[root]=0;
}
int update(int root,int l,int r,int L,int R,ll num)
{
if(l>=L&&r<=R)
{
pushup(root,l,r,num);
return 0;
}
pushdown(root,l,r);
int mid=(l+r)/2;
if(mid>=L)
update(root*2,l,mid,L,R,num);
if(mid<R)
update(root*2+1,mid+1,r,L,R,num);
sum[root]=sum[2*root]+sum[2*root+1];
}
int main()
{
int t,cnt;
scanf("%d",&t);
while(t--)
{
memset(sum,0,sizeof(sum));
memset(mark,0,sizeof(mark));
int n,m,ans=0;
cnt=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
edge[cnt++]=node{y1,x1,x2,1};
edge[cnt++]=node{y2,x1,x2,-1};
}
sort(edge,edge+cnt,cmp);
for(int i=1,j=0;i<=n;i++)
{
while(j<cnt&&edge[j].h<=i&&edge[j].num==1)
{
update(1,1,n,edge[j].a,edge[j].b,1);
j++;
}
ans+=sum[1];
while(j<cnt&&edge[j].h<=i)
{
update(1,1,n,edge[j].a,edge[j].b,1);
j++;
}
}
cout<<ans<<endl;
}
return 0;
}