首页 > 代码库 > 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