首页 > 代码库 > BZOJ 1935 园丁的烦恼

BZOJ 1935 园丁的烦恼

离线,BIT。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 500500using namespace std;int n,m,a,b,c,d,t[maxn*30],ans[maxn*2],hash[maxn*30],cnt=0,mov=0;struct query{    int x,y,pos,val,opt;}q[maxn*7];bool cmp(query a,query 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 add(int x,int val){    for (int i=x;i<=cnt;i+=lowbit(i))        t[i]+=val;}int ask(int x){    int ret=0;    for (int i=x;i>=1;i-=lowbit(i))        ret+=t[i];    return ret;}int main(){        scanf("%d%d",&n,&m);    for (int i=1;i<=n;i++)    {        scanf("%d%d",&a,&b);a++;b++;        q[++mov].x=a;q[i].y=b;q[i].pos=i;q[i].val=1;q[i].opt=0;        hash[++cnt]=b;    }    for (int i=1;i<=m;i++)    {        scanf("%d%d%d%d",&a,&b,&c,&d);a++;b++;c++;d++;        hash[++cnt]=b;hash[++cnt]=d;hash[++cnt]=b-1;hash[++cnt]=d-1;        q[++mov].x=c;q[mov].y=d;q[mov].pos=i;q[mov].val=1;q[mov].opt=1;        q[++mov].x=a-1;q[mov].y=d;q[mov].pos=i;q[mov].val=-1;q[mov].opt=1;        q[++mov].x=c;q[mov].y=b-1;q[mov].pos=i;q[mov].val=-1;q[mov].opt=1;        q[++mov].x=a-1;q[mov].y=b-1;q[mov].pos=i;q[mov].val=1;q[mov].opt=1;    }    sort(hash+1,hash+cnt+1);cnt=unique(hash+1,hash+cnt+1)-hash-1;    for (int i=1;i<=mov;i++) q[i].y=lower_bound(hash+1,hash+cnt+1,q[i].y)-hash;    sort(q+1,q+mov+1,cmp);    for (int i=1;i<=mov;i++)    {        if (!q[i].opt) add(q[i].y,q[i].val);        else ans[q[i].pos]+=q[i].val*ask(q[i].y);    }    for (int i=1;i<=m;i++)        printf("%d\n",ans[i]);    return 0;}

 

BZOJ 1935 园丁的烦恼