【二维偏序】【树状数组】【权值分块】【分块】poj2352 Stars

经典问题：二维偏序。给定平面中的n个点，求每个点左下方的点的个数。

因为所有点已经以y为第一关键字，x为第二关键字排好序，所以我们按读入顺序处理，仅仅需要计算x坐标小于<=某个点的点有多少个就行。

这就是所说的：n维偏序，一维排序，二维树状数组，三维分治 Or 树状数组套平衡树……

<法一>树状数组。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 using namespace std;
 5 struct POINT
 6 {
 7     int x,y;
 8 };
 9 int n,d[3200001],ji[1500001],m;
10 POINT star[1500001];
11 bool cmp(const POINT &a,const POINT &b)
12 {
13     if(a.x<b.x)
14       return true;
15     else if(a.x>b.x)
16       return false;
17     else if(a.y<b.y)
18       return true;
19     return false;
20 }
21 int lowbit(int x)
22 {
23     return x&(-x);
24 }
25 void update(int x,int delta)
26 {
27     for(;x<=m;x+=lowbit(x))
28       d[x]+=delta;
29 }
30 int getsum(int x)
31 {
32     int res=0;
33     for(;x>0;x-=lowbit(x))
34       res+=d[x];
35     return res;
36 }
37 int main()
38 {
39     scanf("%d",&n);
40     for(int i=1;i<=n;i++)
41       {
42           scanf("%d%d",&star[i].x,&star[i].y);
43           star[i].y++;
44           m=max(m,star[i].y);
45       }
46     for(int i=1;i<=n;i++)
47       {
48           update(star[i].y,1);
49           ji[getsum(star[i].y)-1]++;
50       }
51     for(int i=0;i<n;i++)
52       printf("%d
",ji[i]);
53     return 0;
54 }

<法二>权值分块。我会说比树状数组还快将近一倍？

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,x[15001],y[15001],LIMIT,r[200],l[200],num[33000],sumv[200],sz,sum,rank[33000],b[33000];
 6 void makeblock()
 7 {
 8     sz=(int)sqrt((double)LIMIT); if(!sz) sz=1; r[0]=-1;
 9     for(sum=1;sum*sz<LIMIT;sum++)
10       {
11           l[sum]=r[sum-1]+1;
12           r[sum]=sum*sz;
13           for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
14       }
15     l[sum]=r[sum-1]+1;
16     r[sum]=LIMIT;
17     for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
18 }
19 int query(const int &V)
20 {
21     int cnt=0;
22     for(int i=1;i<num[V];i++) cnt+=sumv[i];
23     for(int i=l[num[V]];i<=V;i++) cnt+=b[i];
24     ++b[V]; ++sumv[num[V]];
25     return cnt;
26 }
27 int main()
28 {
29     scanf("%d",&n);
30     for(int i=1;i<=n;i++)
31       {
32           scanf("%d%d",&x[i],&y[i]);
33           LIMIT=max(LIMIT,x[i]);
34       } makeblock();
35     for(int i=1;i<=n;i++) ++rank[query(x[i])];
36     for(int i=0;i<n;i++) printf("%d
",rank[i]);
37     return 0;
38 }

<法三>再介绍一种方便扩展到三维的方法。我们不用按x或者y单调插入。

我们发现，二维偏序实际上是二维树状数组的经典操作。

但是二维BIT的空间复杂度无法接受。

但是我们发现，将一维离散化之后，使其按权值单调，树状数组套平衡树可以轻松查询 x、y同时小于等于一个点的点的个数。空间复杂度O(n*log(n)) 时间复杂度O(n*log^2(n))。

然后我们又发现，这同样也是分块的经典操作。空间复杂度O(n) 时间复杂度O(n*sqrt(n*log(n)))。注意分块的时候，我们为了保证块的形态，要先按一维sort，然后每sqrt(n*log(n))个点分成一块，不能按权值分块。

分块姿势①

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<vector>
 4 #include<cmath>
 5 using namespace std;
 6 vector<int>b[200];
 7 struct Point{int x,y,num;}p[33000];
 8 vector<Point>a[200];
 9 int n,R,L,sum,l[200],r[200],sz,rank[33000];
10 void makeblock()
11 {
12     sz=(int)sqrt((double)n*(log((double)n)/log(2.0))); if(!sz) sz=1;
13     for(sum=1;sum*sz<n;sum++)
14       {
15           int R=sum*sz;
16           for(int i=(sum-1)*sz+1;i<=R;i++) p[i].num=sum;
17       }
18     for(int i=(sum-1)*sz+1;i<=n;i++) p[i].num=sum;
19 }
20 void update(const Point &U)
21 {
22     b[U.num].insert(upper_bound(b[U.num].begin(),b[U.num].end(),U.x),U.x);
23     a[U.num].push_back(U);
24 }
25 int query(const Point &U)
26 {
27     int cnt=0;
28     for(int i=1;i<U.num;++i) cnt+=upper_bound(b[i].begin(),b[i].end(),U.x)-b[i].begin();
29     for(vector<Point>::iterator it=a[U.num].begin();it!=a[U.num].end();++it)
30       if((*it).x<=U.x&&(*it).y<=U.y) ++cnt;
31     return cnt;
32 }
33 int main()
34 {
35     scanf("%d",&n);
36     for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
37     makeblock();
38     for(int i=1;i<=n;i++) update(p[i]);
39     for(int i=1;i<=n;i++) ++rank[query(p[i])-1];
40     for(int i=0;i<n;i++) printf("%d
",rank[i]);
41     return 0;
42 }

分块姿势②

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<vector>
 4 #include<cmath>
 5 using namespace std;
 6 vector<int>b[200];
 7 struct Point{int x,y,num;}p[33000];
 8 vector<Point>a[200];
 9 int n,R,L,l[200],r[200],rank[33000];
10 void makeblock()
11 {
12     int sum,sz=(int)sqrt((double)n*(log((double)n)/log(2.0))); if(!sz) sz=1;
13     for(sum=1;sum*sz<n;sum++)
14       {
15           int R=sum*sz;
16           for(int i=(sum-1)*sz+1;i<=R;i++)
17           {
18               p[i].num=sum;
19               b[sum].push_back(p[i].x);
20               a[sum].push_back(p[i]);
21           }
22         sort(b[sum].begin(),b[sum].end());
23       }
24     for(int i=(sum-1)*sz+1;i<=n;i++)
25       {
26           p[i].num=sum;
27         b[sum].push_back(p[i].x);
28         a[sum].push_back(p[i]);
29       }
30     sort(b[sum].begin(),b[sum].end());
31 }
32 int query(const Point &U)
33 {
34     int cnt=0;
35     for(int i=1;i<U.num;++i) cnt+=upper_bound(b[i].begin(),b[i].end(),U.x)-b[i].begin();
36     for(vector<Point>::iterator it=a[U.num].begin();it!=a[U.num].end();++it)
37       if((*it).x<=U.x&&(*it).y<=U.y) ++cnt;
38     return cnt;
39 }
40 int main()
41 {
42     scanf("%d",&n);
43     for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
44     makeblock();
45     for(int i=1;i<=n;i++) ++rank[query(p[i])-1];
46     for(int i=0;i<n;i++) printf("%d
",rank[i]);
47     return 0;
48 }