隐藏
「bzoj1935」「SHOI2007」园丁的烦恼 - 树状数组二维偏序 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bzoj1935」「SHOI2007」园丁的烦恼 - 树状数组二维偏序

题目大意

多次询问一个矩阵中点的个数。


题目分析

这便是一个普通的二维偏序问题。
我们在Mokia处提到过本题解法且升级成了待修改版。
在这里我们再对二维偏序的处理方式进行详细说明。

还是这个图:

还是这句话:全部减掉比$x1$小的且在$y$范围内点的权值,全部加上比$x2$小且在$y$范围内点的权值。(前缀和)
然而这道题并不含修改操作,所以可以把点和询问混在一起按照$x$排序,当$x$与$y$同时有序时即可做前缀和。
排完序后$x$维已经做到了有序,故用树状数组维护$y$维即可。
记住要对$y$维离散化。


代码

本题使用cdq分治会TLE两个点。

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=500005;
struct BIT {
LL n,c[maxn*3];
#define Lowbit(x) (x&(-x))
void init(LL n) {
this->n=n;
memset(c,0,sizeof(c));
}
void add(LL x,LL v) {
for(int i=x; i<=n; i+=Lowbit(i))c[i]+=v;
}
LL sum(LL x) {
LL ans=0;
for(int i=x; i; i-=Lowbit(i))ans+=c[i];
return ans;
}
} bit;
LL n,k,a[maxn*5],b[maxn*5],sum[maxn],cnt;
void Discretization(int n) {
memcpy(b,a,sizeof(b));
sort(a+1,a+n+1);
int cnt=unique(a+1,a+n+1)-a-1;
for(int i=1; i<=n; i++)b[i]=lower_bound(a+1,a+cnt+1,b[i])-a;
}
struct Point {
LL x,y,v,id,bj;
bool operator < (const Point& b) const {
return x<b.x||(x==b.x&&y<b.y)||(x==b.x&&y==b.y&&id<b.id);
}
} p[maxn*5];
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++) {
p[i].x=Get_Int();
a[i]=p[i].y=Get_Int();
p[i].v=1;
}
cnt=n;
for(int i=1; i<=k; i++) {
LL xx=Get_Int(),yy=Get_Int(),x2=Get_Int(),y2=Get_Int();
p[++cnt]={xx-1,yy-1,0,i,1},a[cnt]=yy-1;
p[++cnt]={xx-1,y2,0,i,-1},a[cnt]=y2;
p[++cnt]={x2,yy-1,0,i,-1},a[cnt]=yy-1;
p[++cnt]={x2,y2,0,i,1},a[cnt]=y2;
}
Discretization(cnt);
for(int i=1; i<=cnt; i++)p[i].y=b[i];
sort(p+1,p+cnt+1);
bit.init(cnt);
for(int i=1; i<=cnt; i++) {
if(p[i].v)bit.add(p[i].y,p[i].v); //原有点
else sum[p[i].id]+=bit.sum(p[i].y)*p[i].bj; //新加点
}
for(int i=1; i<=k; i++)printf("%lld\n",sum[i]);
return 0;
}

姥爷们赏瓶冰阔落吧~