• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【JZOJ7262】模拟NOI!

开发技术 开发技术 4小时前 3次浏览

【JZOJ7262】模拟NOI!

by AmanoKumiko

Desc++ription

给出一个(n*n)的方阵,有(q)个操作,每次操作对于一个子矩阵,从左到右,从下到上编号(从0开始),对于编号为5的倍数的格子染黑,求操作完后的黑格子数

Input

第一行两个整数(n,q)

接下来(q)行每行四个数(x1,y1,x2,y2)表示子矩阵

Output

一行一个整数,表示答案

Sample Input

100000 1
1 1 100000 100000

Sample Output

2000000000

Data Constraint

(1le n,q le 2*10^5)

Solution

对于格子((x,y)),易得格子((x+5,y),(x,y+5))的颜色与其相同

又因为(x,y)对于(5)取模的结果各只有5种,所以对(x,y)分类,一共(25)

再把((x,y))((x+5,y),(x,y+5))之间的“空隙”去掉

那么就是(25)个矩形面积计算,因为各个计算独立,所以直接(25)次扫描线

Code

#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define Fd(i,a,b) for(register int i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define N 100010
#define ls x<<1
#define rs (x<<1)|1

long long ans;
int n,q,X1,Y1,X2,Y2,tot[5][5];
struct node{int stx,enx,y,flag;}a[5][5][N*2];
struct tree{
	int sum[N*4],tag[N*4];
	void modify(int x,int len){sum[x]=tag[x]>0?len:sum[ls]+sum[rs];}
	void change(int x,int l,int r,int ll,int rr,int val){
		if(r<ll||l>rr)return;
		if(l>=ll&&r<=rr){tag[x]+=val;modify(x,r-l+1);return;}
		int mid=l+r>>1;
		change(ls,l,mid,ll,rr,val);change(rs,mid+1,r,ll,rr,val);
		modify(x,r-l+1);
	}
	void clear(){mem(sum,0);mem(tag,0);}
}t;

bool cmp(node x,node y){return x.y<y.y;}

int tr(int x){return x/5+(x%5>0);}

int main(){
	scanf("%d%d",&n,&q);
	F(i,1,q){
		scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
		int lx,ly,rx,ry,len=X2-X1+1;
		F(j,0,4){
			ly=Y1+j;if(ly>Y2)continue;
			F(k,0,4)if(!((k+j*len)%5)){lx=k+X1;break;}if(lx>X2)continue;
			rx=(X2-lx)/5*5+lx;ry=(Y2-ly)/5*5+ly;
			a[lx%5][ly%5][++tot[lx%5][ly%5]]=(node){tr(lx),tr(rx),tr(ly)-1,1};
			a[lx%5][ly%5][++tot[lx%5][ly%5]]=(node){tr(lx),tr(rx),tr(ry),-1};
		}
	}
	F(i,0,4) F(j,0,4){
		t.clear();sort(a[i][j]+1,a[i][j]+tot[i][j]+1,cmp);
		t.change(1,0,n+1,a[i][j][1].stx,a[i][j][1].enx,a[i][j][1].flag);
		F(k,2,tot[i][j]){
			ans+=1ll*t.sum[1]*(a[i][j][k].y-a[i][j][k-1].y);
			t.change(1,0,n+1,a[i][j][k].stx,a[i][j][k].enx,a[i][j][k].flag);
		}
	}
	printf("%lld",ans);
	return 0;
}

程序员灯塔
转载请注明原文链接:【JZOJ7262】模拟NOI!
喜欢 (0)