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

# 【JZOJ7262】模拟NOI！

4小时前 3次浏览

## 【JZOJ7262】模拟NOI！

### by AmanoKumiko

#### Sample Input

``````100000 1
1 1 100000 100000
``````

#### Sample Output

``````2000000000
``````

#### Data Constraint

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

#### 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;
}
``````