首页 > 代码库 > BZOJ 1176 MOKIA
BZOJ 1176 MOKIA
cdq分治。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 2000500#define maxq 400050using namespace std;int s,w,type,a,b,c,d,cnt=0,m=0,ans[maxq];struct ques{ int val,opt,x,y,pos,id;}q[maxq],tmp[maxq];int t[maxn];bool cmp(ques a,ques b){ if ((a.x==b.x) && (a.y==b.y)) return a.opt<b.opt; if (a.x==b.x) return a.y<b.y; return a.x<b.x;}int lowbit(int x){ return (x&(-x));}void add1(int x){ scanf("%d%d%d",&a,&b,&c); q[++m].id=m;q[m].pos=0;q[m].val=c;q[m].opt=0; q[m].x=a;q[m].y=b;}void add2(int x){ scanf("%d%d%d%d",&a,&b,&c,&d); cnt++; q[++m].val=1;q[m].opt=1;q[m].x=c;q[m].y=d;q[m].pos=cnt;q[m].id=m; q[++m].val=1;q[m].opt=1;q[m].x=a-1;q[m].y=b-1;q[m].pos=cnt;q[m].id=m; q[++m].val=-1;q[m].opt=1;q[m].x=a-1;q[m].y=d;q[m].pos=cnt;q[m].id=m; q[++m].val=-1;q[m].opt=1;q[m].x=c;q[m].y=b-1;q[m].pos=cnt;q[m].id=m;}void add(int x,int val){ for (int i=x;i<=w;i+=lowbit(i)) t[i]+=val;}int query(int x){ int ret=0; for (int i=x;i>=1;i-=lowbit(i)) ret+=t[i]; return ret;}void cdq(int left,int right){ if (left==right) return; int mid=left+right>>1; int l1=left,l2=mid+1; for (int i=left;i<=right;i++) { if ((q[i].id<=mid) && (!q[i].opt)) add(q[i].y,q[i].val); else if ((q[i].id>mid) && (q[i].opt)) ans[q[i].pos]+=q[i].val*query(q[i].y); } for (int i=left;i<=right;i++) if ((q[i].id<=mid) && (!q[i].opt)) add(q[i].y,-q[i].val); for (int i=left;i<=right;i++) { if (q[i].id<=mid) tmp[l1++]=q[i]; else tmp[l2++]=q[i]; } for (int i=left;i<=right;i++) q[i]=tmp[i]; cdq(left,mid);cdq(mid+1,right);}int main(){ scanf("%d%d",&s,&w); while (scanf("%d",&type)!=EOF) { if (type==3) break; if (type==1) add1(cnt); else add2(cnt); } sort(q+1,q+m+1,cmp); cdq(1,m); for (int i=1;i<=cnt;i++) printf("%d\n",ans[i]); return 0;}
BZOJ 1176 MOKIA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。