首页 > 代码库 > 【BZOJ1935/4822】[Shoi2007]Tree 园丁的烦恼/[Cqoi2017]老C的任务 树状数组
【BZOJ1935/4822】[Shoi2007]Tree 园丁的烦恼/[Cqoi2017]老C的任务 树状数组
题意：两道题差不多，都是给你一堆平面上的点，每个点有权值，然后m次询问求某一矩形区域内的点权和
题解：先离散化，然后将询问拆成左右两条线段，然后将点和这些线段一起按x坐标排序，在y轴上维护树状数组。然后询问的答案就是两条线段上点权和之差
BZOJ1935:
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int s[1000010];struct QUERY{ int qx,ql,qr,org,k;}q[1000010];struct tree{ int px,py;}p[500010];int n,m,nm;int ans[500010];int rd(){ int ret=0; char gc=getchar(); while(gc<‘0‘||gc>‘9‘) gc=getchar(); while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar(); return ret;}bool cmp1(tree a,tree b){ return a.px<b.px;}bool cmp2(QUERY a,QUERY b){ return a.qx<b.qx;}void updata(int x){ for(int i=x;i<=nm;i+=i&-i) s[i]++;}int query(int x){ int i,ret=0; for(i=x;i;i-=i&-i) ret+=s[i]; return ret;}int main(){ n=rd(),m=rd(); int i,j; for(i=1;i<=n;i++) p[i].px=rd(),p[i].py=rd()+1; for(i=1;i<=m;i++) q[i*2-1].qx=rd()-1,q[i*2-1].ql=q[i*2].ql=rd(),q[i*2].qx=rd(),q[i*2-1].qr=q[i*2].qr=rd()+1, q[i*2-1].org=q[i*2].org=i,q[i*2-1].k=-1,q[i*2].k=1,nm=max(nm,q[i*2].qr); sort(p+1,p+n+1,cmp1); sort(q+1,q+2*m+1,cmp2); for(i=j=1;i<=2*m;i++) { for(;j<=n&&p[j].px<=q[i].qx;j++) updata(p[j].py); ans[q[i].org]+=q[i].k*(query(q[i].qr)-query(q[i].ql)); } for(i=1;i<=m;i++) printf("%d\n",ans[i]); return 0;}BZOJ4822
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef long long ll;struct QUERY{ int qx,ql,qr,org,k;}q[200010];struct tree{ int px,py; ll pow;}p[100010];int n,m,nm;ll ans[100010],s[400010];struct node{ int num,org,k;}v[500010];int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<‘0‘||gc>‘9‘){if(gc==‘-‘)f=-f; gc=getchar();} while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar(); return ret*f;}bool cmp(node a,node b){ return a.num<b.num;}bool cmp1(tree a,tree b){ return a.px<b.px;}bool cmp2(QUERY a,QUERY b){ return a.qx<b.qx;}void updata(int x,ll val){ for(int i=x;i<=nm;i+=i&-i) s[i]+=val;}ll query(int x){ int i; ll ret=0; for(i=x;i;i-=i&-i) ret+=s[i]; return ret;}int main(){ n=rd(),m=rd(); int i,j; for(i=1;i<=n;i++) p[i].px=rd(),v[i].num=rd(),p[i].pow=rd(),v[i].org=i,v[i].k=1; for(i=1;i<=m;i++) q[i*2-1].qx=rd()-1,v[i*2-1+n].num=rd()-1,q[i*2].qx=rd(),v[i*2+n].num=rd(), q[i*2-1].org=q[i*2].org=i,q[i*2-1].k=-1,q[i*2].k=1,v[i*2-1+n].org=v[i*2+n].org=i, v[i*2-1+n].k=2,v[i*2+n].k=3; sort(v+1,v+n+2*m+1,cmp); for(i=1;i<=n+2*m;i++) { if(v[i].num>v[i-1].num||i==1) nm++; if(v[i].k==1) p[v[i].org].py=nm; if(v[i].k==2) q[2*v[i].org-1].ql=q[2*v[i].org].ql=nm; if(v[i].k==3) q[2*v[i].org-1].qr=q[2*v[i].org].qr=nm; } sort(p+1,p+n+1,cmp1); sort(q+1,q+2*m+1,cmp2); for(i=j=1;i<=2*m;i++) { for(;j<=n&&p[j].px<=q[i].qx;j++) updata(p[j].py,p[j].pow); ans[q[i].org]+=(ll)q[i].k*(query(q[i].qr)-query(q[i].ql)); } for(i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0;}【BZOJ1935/4822】[Shoi2007]Tree 园丁的烦恼/[Cqoi2017]老C的任务 树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。