BZOJ1176: [Balkan2007]Mokia CDQ分治

最近很不对啊=w= 写程序全是bug啊

ans数组开小了竟然一直不知道,小数据没问题大数据拍不过,交上去RE

蛋疼半天

这个主要把每次询问拆成3个询问。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<iostream>
#define dout printf
using namespace std; const int Maxw=+,Maxm=+,Maxq=+;
typedef long long ll;
int S,W,tot,C[Maxw],ans[Maxm+Maxq*]; void Add(int x,const int&d){
for(;<x&&x<=W;x+=x&-x)C[x]+=d;
}
int Query(int x){
int ret=;
for(;<x&&x<=W;x-=x&-x)ret+=C[x];
return ret;
} const int Hmod=1e5+;
struct node{
bool tp;//0 for modify and 1 for query
int x,y,ans,id;
node(int x,int y,int tp,int ans,int id):tp(tp),x(x),y(y),ans(ans),id(id){}
node(){ans=;}
}da[Maxq*+Maxm],q[Maxq*+Maxm]; struct prob{
int s1,s2,s3,s4,t;
void init(int x1,int y1,int x2,int y2){
++tot,da[s1=tot]=node(x2,y2,,,tot);
if(x1==||y1==)s2=;
else ++tot,da[s2=tot]=node(x1-,y1-,,,tot);
if(x1==)s3=;
else ++tot,da[s3=tot]=node(x1-,y2,,,tot);
if(y1==)s4=;
else ++tot,da[s4=tot]=node(x2,y1-,,,tot);
t=(x2-x1+)*(y2-y1+);
}
int calc(){
return ans[s1]+ans[s2]-(ans[s3]+ans[s4])+t*S;
}
}pr[Maxq];int totpr=; inline bool cmp(const node&a,const node&b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
void init(){
scanf("%d%d",&S,&W);
for(int x1,y1,x2,y2,d,opt;~scanf("%d",&opt)&&opt!=;){
if(opt==)scanf("%d%d%d",&x1,&y1,&d),++tot,da[tot]=node(x1,y1,,d,tot);
else scanf("%d%d%d%d",&x1,&y1,&x2,&y2),pr[++totpr].init(x1,y1,x2,y2);
}
} void CDQ(int l,int r){
if(l==r)return;
int mid=(l+r)>>;
CDQ(l,mid);
CDQ(mid+,r);
int i=l;
for(int j=mid+;j<=r;j++){
for(;i<=mid&&da[i].x<=da[j].x;i++)if(!da[i].tp)Add(da[i].y,da[i].ans);
if(da[j].tp)da[j].ans+=Query(da[j].y);
}
for(i--;i>=l;i--)if(!da[i].tp)Add(da[i].y,-da[i].ans);
merge(da+l,da+mid+,da+mid+,da+r+,q,cmp);
memcpy(da+l,q,sizeof(da[])*(r-l+));
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout); init();
CDQ(,tot);
for(int i=;i<=tot;i++)ans[da[i].id]=da[i].ans;
for(int i=;i<=totpr;i++)printf("%d\n",pr[i].calc()); return ;
}
上一篇:pace.js和NProgress.js两个加载进度插件的一点小总结


下一篇:windows下脚本配置IP地址