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）为界的矩形里有多少棵树。
题目分析
这就是一个经典的二维数点问题。
于是这里提供两种做法：
1.树状数组离散化
2.cdq分治
这里是BIT做法：
#include<bits/stdc++.h>
const int maxn = ; struct node
{
int x,y,lb,fr;
bool operator < (node a) const
{
return x==a.x?lb<a.lb:x<a.x;
}
}f[*maxn];
int n,m,cnt,tot;
int sum[maxn],ans[maxn][];
int a[maxn],b[maxn],c[maxn],d[maxn],x[maxn],y[maxn],p[*maxn]; int lowbit(int x){return x&-x;}
void add(int x){for (; x<=cnt; x+=lowbit(x)) sum[x]++;}
int query(int x)
{
int ret = ;
for (; x; x-=lowbit(x))
ret += sum[x];
return ret;
}
int read()
{
char ch = getchar();
int num = ;
for (; !isdigit(ch); ch = getchar());
for (; isdigit(ch); ch = getchar())
num = (num<<)+(num<<)+ch-;
return num;
}
int main()
{
n = read(), m = read();
for (int i=; i<=n; i++)
x[i] = read()+, y[i] = read()+, p[++cnt] = y[i];
for (int i=; i<=m; i++)
a[i] = read()+, b[i] = read()+, c[i] = read()+, d[i] = read()+,
p[++cnt] = b[i], p[++cnt] = d[i];
std::sort(p+, p+cnt+);
cnt = std::unique(p+, p+cnt+)-p-;
for (int i=; i<=n; i++)
y[i] = std::lower_bound(p+, p+cnt+, y[i])-p,
f[++tot].x = x[i], f[tot].y = y[i];
for (int i=; i<=m; i++)
{
b[i] = std::lower_bound(p+, p+cnt+, b[i])-p;
d[i] = std::lower_bound(p+, p+cnt+, d[i])-p;
f[++tot].x = a[i]-, f[tot].y = b[i]-, f[tot].lb = ,f[tot].fr = i;
f[++tot].x = a[i]-, f[tot].y = d[i], f[tot].lb = ,f[tot].fr = i;
f[++tot].x = c[i], f[tot].y = b[i]-, f[tot].lb = ,f[tot].fr = i;
f[++tot].x = c[i], f[tot].y = d[i], f[tot].lb = ,f[tot].fr = i;
}
std::sort(f+, f++tot);
for (int i=; i<=tot; i++)
if (f[i].lb) ans[f[i].fr][f[i].lb] = query(f[i].y);
else add(f[i].y);
for (int i=; i<=m; i++)
printf("%d\n",ans[i][]+ans[i][]-ans[i][]-ans[i][]);
return ;
}
这里是cdq做法：
#include<bits/stdc++.h>
const int maxn = ;
const int maxk = ; struct point
{
int x,y,lb,mt;
point() {}
point(int a, int b, int c, int d):x(a),y(b),lb(c),mt(d) {}
bool operator < (point a) const
{
return x==a.x?abs(mt) < abs(a.mt):x < a.x;
}
}f[maxn*],s[maxn*];
int n,m,cnt,dfn,maxy;
int sum[maxk],tim[maxk],ans[maxn]; int lowbit(int x){return x&-x;}
void add(int x)
{
for (; x <= maxy; x += lowbit(x))
{
if (tim[x] != dfn) tim[x] = dfn, sum[x] = ;
sum[x]++;
}
}
int query(int x)
{
int ret = ;
for (; x; x -= lowbit(x))
if (tim[x] == dfn)
ret += sum[x];
return ret;
}
int read()
{
char ch = getchar();
int num = ;
for (; !isdigit(ch); ch = getchar());
for (; isdigit(ch); ch = getchar())
num = (num<<)+(num<<)+ch-;
return num;
}
void cdq(int l, int r)
{
if (l >= r) return;
int mid = (l+r)>>, L = l, R = mid+, now = l;
cdq(l, mid);
cdq(mid+, r);
dfn++;
while (L <= mid && R <= r)
if (f[L] < f[R]){
if (!f[L].mt) add(f[L].y);
s[now++] = f[L++];
}else{
if (f[R].mt) ans[f[R].lb] += f[R].mt*query(f[R].y);
s[now++] = f[R++];
}
while (L <= mid) s[now++] = f[L++];
while (R <= r)
{
if (f[R].mt) ans[f[R].lb] += f[R].mt*query(f[R].y);
s[now++] = f[R++];
}
for (int i=l; i<=r; i++) f[i] = s[i];
}
int main()
{
n = read(), m = read();
for (int i=; i<=n; i++)
f[++cnt].x = read()+, f[cnt].y = read()+, maxy = std::max(maxy, f[cnt].y);
for (int i=; i<=m; i++)
{
int a = read()+, b = read()+, c = read()+, d = read()+;
f[++cnt] = point(a-, b-, i, );
f[++cnt] = point(c, d, i, );
f[++cnt] = point(a-, d, i, -);
f[++cnt] = point(c, b-, i, -);
maxy = std::max(maxy, std::max(b, d));
}
cdq(, cnt);
for (int i=; i<=m; i++)
printf("%d\n",ans[i]);
return ;
}
另有关cdq的问题详见「初涉cdq」专题
END