| 记录编号 |
314827 |
评测结果 |
RRRRRRRRRR |
| 题目名称 |
[IOI 2001] 移动电话 |
最终得分 |
0 |
| 用户昵称 |
 AntiLeaf |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
2.535 s |
| 提交时间 |
2016-10-04 08:14:32 |
内存使用 |
224.40 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
typedef int point[2];
void madd(point,point,int,int);
void qsum(point,point,int,int);
void pushdown(point,point,int,int);
long long a[maxn*maxn<<4],lazy[maxn*maxn<<4];
int n,m;
long long d,ans;
point x,s,t,L,R;
int main(){
#define MINE
#ifdef MINE
freopen("notmobile.in","r",stdin);
freopen("notmobile.out","w",stdout);
#endif
memset(a,0,sizeof(a));
memset(lazy,0,sizeof(lazy));
scanf("%d%d",&n,&m);
L[0]=L[1]=1;
R[0]=R[1]=n;
while(m--){
scanf("%lld%d%d%d%d",&d,&s[0],&s[1],&t[0],&t[1]);
if(d==1ll){
scanf("%lld",&d);
madd(L,R,1,0);
}
else{
ans=0ll;
qsum(L,R,1,0);
printf("%lld\n",ans);
}
}
#ifndef MINE
printf("\n-------------------------DONE-------------------------\n");
for(;;);
#endif
return 0;
}
void madd(point l,point r,int rt,int k){
//printf("(%d,%d)-(%d,%d) k=%d\n",l[0],l[1],r[0],r[1],k);
//printf("rt=%d a[rt]=%lld lazy[rt]=%lld\n",rt,a[rt],lazy[rt]);
if(s[0]<=l[0]&&t[0]>=r[0]&&s[1]<=l[1]&&t[1]>=r[1]){
lazy[rt]+=d;
a[rt]+=lazy[rt]*(long long)(r[0]-l[0]+1)*(long long)(r[1]-l[1]+1);
return;
}
if(l[0]==r[0])k=1;
else if(l[1]==r[1])k=0;
pushdown(l,r,rt,k);
if(k==0){
//printf("lc:(%d,%d)-(%d,%d)\n",l[0],l[1],(l[0]+r[0])>>1,r[1]);
//printf("rc:(%d,%d)-(%d,%d)\n",((l[0]+r[0])>>1)+1,l[1],r[0],r[1]);
}
else{
//printf("lc:(%d,%d)-(%d,%d)\n",l[0],l[1],r[0],(l[1]+r[1])>>1);
//printf("rc:(%d,%d)-(%d,%d)\n",l[0],((l[1]+r[1])>>1)+1,r[0],r[1]);
}
//printf("\n");
point mid;
if(s[k]<=((l[k]+r[k])>>1)){
mid[k]=(l[k]+r[k])>>1;
mid[k^1]=r[k^1];
madd(l,mid,rt<<1,k^1);
}
if(t[k]>((l[k]+r[k])>>1)){
mid[k]=((l[k]+r[k])>>1)+1;
mid[k^1]=l[k^1];
madd(mid,r,rt<<1|1,k^1);
}
a[rt]=a[rt<<1]+a[rt<<1|1];
//printf("back to (%d,%d)-(%d,%d) k=%d\n",l[0],l[1],r[0],r[1],k);
//printf("rt=%d a[rt]=%lld lazy[rt]=%lld\n",rt,a[rt],lazy[rt]);
//printf("\n");
}
void qsum(point l,point r,int rt,int k){
//printf("(%d,%d)-(%d,%d) k=%d\n",l[0],l[1],r[0],r[1],k);
//printf("rt=%d a[rt]=%lld lazy[rt]=%lld\n",rt,a[rt],lazy[rt]);
if(s[0]<=l[0]&&t[0]>=r[0]&&s[1]<=l[1]&&t[1]>=r[1]){
ans+=a[rt];
return;
}
if(l[0]==r[0])k=1;
else if(l[1]==r[1])k=0;
pushdown(l,r,rt,k);
point mid;
if(k==0){
//printf("lc:(%d,%d)-(%d,%d)\n",l[0],l[1],(l[0]+r[0])>>1,r[1]);
//printf("rc:(%d,%d)-(%d,%d)\n",((l[0]+r[0])>>1)+1,l[1],r[0],r[1]);
}
else{
//printf("lc:(%d,%d)-(%d,%d)\n",l[0],l[1],r[0],(l[1]+r[1])>>1);
//printf("rc:(%d,%d)-(%d,%d)\n",l[0],((l[1]+r[1])>>1)+1,r[0],r[1]);
}
//printf("\n");//getchar();
if(s[k]<=((l[k]+r[k])>>1)){
mid[k]=(l[k]+r[k])>>1;
mid[k^1]=r[k^1];
qsum(l,mid,rt<<1,k^1);
}
if(t[k]>((l[k]+r[k])>>1)){
mid[k]=((l[k]+r[k])>>1)+1;
mid[k^1]=l[k^1];
qsum(mid,r,rt<<1|1,k^1);
}
//printf("back to (%d,%d)-(%d,%d) k=%d\n",l[0],l[1],r[0],r[1],k);
//printf("rt=%d a[rt]=%lld lazy[rt]=%lld\n",rt,a[rt],lazy[rt]);
//printf("\n");
}
void pushdown(point l,point r,int rt,int k){
if(!lazy[rt])return;
//printf("pushdown(%d)\n",rt);
int lc=rt<<1,rc=rt<<1|1;
point mid;
mid[k]=(l[k]+r[k])>>1;
mid[k^1]=r[k^1];
a[lc]+=lazy[rt]*(mid[k]-l[k]+1)*(mid[k^1]-l[k^1]+1);
lazy[lc]+=lazy[rt];
mid[k]=((l[k]+r[k])>>1)+1;
mid[k^1]=l[k^1];
a[rc]+=lazy[rt]*(r[k]-mid[k]+1)*(r[k^1]-mid[k^1]+1);
lazy[rc]+=lazy[rt];
lazy[rt]=0ll;
}
/*
5 8
1 1 1 2 2 1
2 2 2 3 3
1 1 5 2 5 3
2 1 1 5 2
2 2 3 4 5
1 1 1 1 1 7
1 4 5 5 5 4
2 2 2 4 5
Answer:
1
4
3
8
*/
/*
我们尝试使用类似K-D树的方式劈区间，
把当前区间轮流横劈和竖劈，
这样就可以完美地解决二维问题啦。
*/