「BZOJ1935」[SHOI2007] Tree 园丁的烦恼
Description
很久很久以前,在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者,在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里,若有所思,他问一个园丁道: “最近我在思索一个问题,如果我们把花坛摆成六个六角形,那么……” “那么本质上它是一个深度优先搜索,陛下”,园丁深深地向国王鞠了一躬。 “嗯……我听说有一种怪物叫九头蛇,它非常贪吃苹果树……” “是的,显然这是一道经典的动态规划题,早在N元4002年我们就已经发现了其中的奥秘了,陛下”。 “该死的,你究竟是什么来头?” “陛下息怒,干我们的这行经常莫名其妙地被问到和OI有关的题目,我也是为了预防万一啊!” 王者的尊严受到了伤害,这是不可容忍的。看来一般的难题是难不倒这位园丁的,国王最后打算用车轮战来消耗他的实力: “年轻人,在我的花园里的每一棵树可以用一个整数坐标来表示,一会儿,我的骑士们会来轮番询问你某一个矩阵内有多少树,如果你不能立即答对,你就准备走人吧!”说完,国王气呼呼地先走了。 这下轮到园丁傻眼了,他没有准备过这样的问题。所幸的是,作为“全国园丁保护联盟”的会长——你,可以成为他的最后一根救命稻草。
Input
第一行有两个整数n,m(0≤n≤500000,1≤m≤500000)。n代表皇家花园的树木的总数,m代表骑士们询问的次数。 文件接下来的n行,每行都有两个整数xi,yi,代表第i棵树的坐标(0≤xi,yi≤10000000)。 文件的最后m行,每行都有四个整数aj,bj,cj,dj,表示第j次询问,其中所问的矩形以(aj,bj)为左下坐标,以(cj,dj)为右上坐标。
Output
共输出m行,每行一个整数,即回答国王以(aj,bj)和(cj,dj)为界的矩形里有多少棵树。
Sample Input
3 1
0 0
0 1
1 0
0 0 1 1
0 0
0 1
1 0
0 0 1 1
Sample Output
3
题解
妈蛋一道水题看了半天
离线处理询问
x坐标排序,y坐标上离散化以后树状数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,tot,que; int disc[1500005]; int x[500005],y[500005]; int a[500005],b[500005],c[500005],d[500005]; int t[1500005]; int ans[500005][5]; struct data{int x,y,id,f;}q[2500005]; inline int lowbit(int x){return x&(-x);} inline bool operator<(data a,data b) { return a.x<b.x||(a.x==b.x&&a.f<b.f); } inline void add(int x,int y) { for(int i=x;i<=tot;i+=lowbit(i)) t[i]+=y; } inline int query(int x) { int sum=0; for(int i=x;i;i-=lowbit(i)) sum+=t[i]; return sum; } int find(int x) { int l=1,r=tot; while(l<=r) { int mid=(l+r)>>1; if(disc[mid]==x)return mid; else if(disc[mid]<x)l=mid+1; else r=mid-1; } } void solve() { sort(q+1,q+que+1); for(int i=1;i<=que;i++) { if(!q[i].f)add(q[i].y,1); else { int t=query(q[i].y); ans[q[i].id][q[i].f]=t; } } } int main() { n=read();m=read(); for(int i=1;i<=n;i++) { x[i]=read(),y[i]=read(); disc[++tot]=y[i]; } for(int i=1;i<=m;i++) { a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read(); disc[++tot]=b[i];disc[++tot]=d[i]; } sort(disc,disc+tot+1); for(int i=1;i<=n;i++) { y[i]=find(y[i]); q[++que].x=x[i];q[que].y=y[i]; } for(int i=1;i<=m;i++) { b[i]=find(b[i]);d[i]=find(d[i]); q[++que].x=c[i];q[que].y=d[i];q[que].id=i;q[que].f=1; q[++que].x=a[i]-1;q[que].y=d[i];q[que].id=i;q[que].f=2; q[++que].x=c[i];q[que].y=b[i]-1;q[que].id=i;q[que].f=3; q[++que].x=a[i]-1;q[que].y=b[i]-1;q[que].id=i;q[que].f=4; } solve(); for(int i=1;i<=m;i++) { int t=ans[i][1]+ans[i][4]-ans[i][2]-ans[i][3]; printf("%d\n",t); } return 0; } |
求教这题能不能用二维树状数组做。。
n到500000……