首页 > 代码库 > 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 园丁的烦恼
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。