记录编号 |
357605 |
评测结果 |
AAAAAAAAAA |
题目名称 |
蝗灾 |
最终得分 |
100 |
用户昵称 |
哒哒哒哒哒! |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
2.574 s |
提交时间 |
2016-12-11 17:10:43 |
内存使用 |
27.07 MiB |
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
const int maxn=501000;
struct qu{int op,x,y,x2,y2,c;}q[maxn];
int n,m,c[maxn];
ll ans[maxn];
struct quer{
int op,x,y,c,p;
bool operator < (const quer &a)const{
if(x==a.x&&y==a.y) return op<a.op;
if(x!=a.x)return x<a.x;
return y<a.y;
}
}qq[maxn];
void insert(int x,int y){if(x==0)return;for(int i=x;i<=n;i+=i&-i)c[i]+=y;}
int query(int x){int s=0;for(int i=x;i;i-=i&-i)s+=c[i];return s;}
void solve(int l,int r){
if(l==r) return;
int mid=(l+r)/2,cnt=0;
solve(l,mid);
for(int i=l;i<=mid;i++)
if(q[i].op==1) qq[++cnt].op=1,qq[cnt].x=q[i].x,qq[cnt].y=q[i].y,qq[cnt].c=q[i].c;
for(int i=mid+1;i<=r;i++)
if(q[i].op==2){
qq[++cnt].op=2,qq[cnt].x=q[i].x-1,qq[cnt].y=q[i].y-1,qq[cnt].c=1,qq[cnt].p=i;
qq[++cnt].op=2,qq[cnt].x=q[i].x2,qq[cnt].y=q[i].y2,qq[cnt].c=1,qq[cnt].p=i;
qq[++cnt].op=2,qq[cnt].x=q[i].x-1,qq[cnt].y=q[i].y2,qq[cnt].c=-1,qq[cnt].p=i;
qq[++cnt].op=2,qq[cnt].x=q[i].x2,qq[cnt].y=q[i].y-1,qq[cnt].c=-1;qq[cnt].p=i;
}
sort(qq+1,qq+cnt+1);
for(int i=1;i<=cnt;i++){
if(qq[i].op==1) insert(qq[i].y,qq[i].c);
else ans[qq[i].p]+=qq[i].c*1ll*query(qq[i].y);
}
for(int i=1;i<=cnt;i++)
if(qq[i].op==1) insert(qq[i].y,-qq[i].c);
solve(mid+1,r);
}
int main(){
freopen("locust.in","r",stdin);freopen("locust.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=m;i++){
q[i].op=read();
if(q[i].op==1) q[i].x=read(),q[i].y=read(),q[i].c=read();
else q[i].x=read(),q[i].y=read(),q[i].x2=read(),q[i].y2=read();
}
solve(1,m);
for(int i=1;i<=m;i++)if(q[i].op==2)printf("%lld\n",ans[i]);
fclose(stdin);fclose(stdout);
return 0;
}