首页 > 代码库 > BZOJ 2683 简单题 ——CDQ分治
BZOJ 2683 简单题 ——CDQ分治
简单题
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) #define maxn 2000005 int sum[maxn]; void add(int x,int f) { // printf("Add %d on %d\n",f,x); for (;x<maxn;x+=x&(-x)) sum[x]+=f; } int gs(int x) { // printf("gs %d ",x); int ret=0; for (;x;x-=x&(-x)) ret+=sum[x]; // printf("= %d\n",ret); return ret; } struct query{ int opt; int x,y,a; int id; void print() { printf("%d %d %d %d %d\n",opt,x,y,a,id); } }a[maxn]; int opt,top=0,x,y,xx,yy,tot,ans[maxn]; bool cmp(query A,query B) {return A.x<B.x;} void CDQ(int l,int r) { if (l==r) return; int mid=l+r>>1; CDQ(l,mid); CDQ(mid+1,r); // printf("CDQ %d %d\n",l,r); // F(i,l,r) a[i].print(); int pl=l; F(i,mid+1,r) if (a[i].opt==2){ // printf("now is %d %d\n",a[i].x,a[i].y); // a[pl].print(); while (a[i].x>=a[pl].x&&pl<=mid) { if (a[pl].opt==1) { add(a[pl].y,a[pl].a); // printf("Add %d on %d\n",a[pl].a,a[pl].y); } pl++; } ans[a[i].id]+=a[i].a*gs(a[i].y); // printf("%d += %d\n",a[i].id,a[i].a*gs(a[i].y)); } F(i,l,pl-1) if (a[i].opt==1) add(a[i].y,-a[i].a); sort(a+l,a+r+1,cmp); // printf("Over\n"); } int main() { scanf("%*d"); while (scanf("%d",&opt)!=EOF&&opt!=3) { switch (opt) { case 1: ++top;scanf("%d%d%d",&a[top].x,&a[top].y,&a[top].a);a[top].opt=1;break; case 2: ++tot; scanf("%d%d%d%d",&x,&y,&xx,&yy); ++top;a[top].id=tot;a[top].x=xx; a[top].y=yy; a[top].a=1; a[top].opt=2; ++top;a[top].id=tot;a[top].x=x-1;a[top].y=y-1; a[top].a=1; a[top].opt=2; ++top;a[top].id=tot;a[top].x=xx; a[top].y=y-1; a[top].a=-1;a[top].opt=2; ++top;a[top].id=tot;a[top].x=x-1; a[top].y=yy; a[top].a=-1;a[top].opt=2; break; } } CDQ(1,top); F(i,1,tot) printf("%d\n",ans[i]); }
BZOJ 2683 简单题 ——CDQ分治
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。