首页 > 代码库 > 四维偏序

四维偏序

2024-08-28 12:53:01   222人阅读

我是萌萌的传送门

终于(算是)学会CDQ套CDQ了= =看来我对分治的理解还是不太深，要不然怎么会只会用CDQ压掉一维却不会压掉更高维呢……

题目就是个最简单的四维偏序，为了简化问题把四维都搞成了1~n的排列(废话，出题人可是我自己= =)，还把四维LIS换成了四维正序对(该是有多懒……)

四维偏序的话其实压力还是有点大的，首先O(nlog3n)的算法跟暴力差距真的不是特别大，不过经实测除了树套树套树速度和暴力差不多之外剩下的两种做法都是比较快的(经测试n=50000的数据暴力要跑大概6s+，好吧年代久远我忘了具体时间了)，所以时限开到2.5s，保证CDQ树套树和CDQ再CDQ都能稳过了。

言归正传。

CDQ树套树的做法很好想，就是对位置分治，这样就可以用扫描线把x压掉，只剩下y和z两维了。由于x已经用离线的扫描线压掉了，必须在线维护y和z，因此可以直接树套树(我写的是树状数组套替罪羊树，由于是随机数据替罪羊树还是很快的)。

技术分享 
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define siz(x) ((x)?((x)->size):(0))
  5 #define lowbit(x) ((x)&(-(x)))
  6 using namespace std;
  7 const int maxn=50010;
  8 const double A=0.65;
  9 struct node{//Scapegoat Tree
 10     int data,size;
 11     node *lc,*rc,*prt;
 12     node(int d=0):data(d),size(1),lc(NULL),rc(NULL),prt(NULL){}
 13     inline void refresh(){size=siz(lc)+siz(rc)+1;}
 14 }*root[maxn];
 15 struct B{
 16     int id,a,b,c;
 17     bool operator<(const B &a)const{return this->a<a.a;}
 18 }a[maxn],b[maxn];
 19 void CDQ(int,int);
 20 void add(int,int);
 21 void del(int,int);
 22 int query(int,int);
 23 void insert(int);
 24 void erase(int);
 25 int rank(int);
 26 node *insert(node*);
 27 node *find(int);
 28 node *erase(node*);
 29 node *findmax(node*);
 30 void rebuild(node*);
 31 void zorder(node*);
 32 void removetree(node*);
 33 node *rebuild(int,int);
 34 int n,T,cnt,data[maxn];
 35 long long ans=0ll;
 36 int main(){
 37 #define MINE
 38 #ifdef MINE
 39     freopen("partial_order.in","r",stdin);
 40     freopen("partial_order.out","w",stdout);
 41 #endif
 42     scanf("%d",&n);
 43     for(int i=1;i<=n;i++)a[i].id=i;
 44     for(int i=1;i<=n;i++)scanf("%d",&a[i].a);
 45     for(int i=1;i<=n;i++)scanf("%d",&a[i].b);
 46     for(int i=1;i<=n;i++)scanf("%d",&a[i].c);
 47     CDQ(1,n);
 48     printf("%lld",ans);
 49 #ifndef MINE
 50     printf("\n-------------------------DONE-------------------------\n");
 51     for(;;);
 52 #endif
 53     return 0;
 54 }
 55 void CDQ(int l,int r){
 56     if(l>=r)return;
 57     int mid=(l+r)>>1;
 58     CDQ(l,mid);
 59     CDQ(mid+1,r);
 60     int i=l,j=mid+1,k=l;
 61     while(i<=mid&&j<=r){
 62         if(a[i]<a[j])b[k++]=a[i++];
 63         else b[k++]=a[j++];
 64     }
 65     while(i<=mid)b[k++]=a[i++];
 66     while(j<=r)b[k++]=a[j++];
 67     for(int i=l;i<=r;i++){
 68         a[i]=b[i];
 69         if(a[i].id<=mid)add(a[i].b,a[i].c);
 70         else ans+=query(a[i].b,a[i].c);
 71     }
 72     for(int i=l;i<=r;i++)if(a[i].id<=mid)del(a[i].b,a[i].c);
 73 }
 74 void add(int x,int d){
 75     while(x<=n){
 76         T=x;
 77         insert(d);
 78         x+=lowbit(x);
 79     }
 80 }
 81 void del(int x,int d){
 82     while(x<=n){
 83         T=x;
 84         erase(d);
 85         x+=lowbit(x);
 86     }
 87 }
 88 int query(int x,int d){
 89     int ans=0;
 90     while(x){
 91         T=x;
 92         ans+=rank(d);
 93         x-=lowbit(x);
 94     }
 95     return ans;
 96 }
 97 void insert(int x){
 98     node *rt=insert(new node(x));
 99     if(rt)rebuild(rt);
100 }
101 void erase(int x){
102     node *rt=erase(find(x));
103     if(rt)rebuild(rt);
104 }
105 int rank(int x){
106     node *rt=root[T];
107     int ans=0;
108     while(rt){
109         if(x<=rt->data)rt=rt->lc;
110         else{
111             ans+=siz(rt->lc)+1;
112             rt=rt->rc;
113         }
114     }
115     return ans;
116 }
117 node *insert(node *x){
118     if(!root[T]){
119         root[T]=x;
120         return NULL;
121     }
122     node *rt=root[T];
123     for(;;){
124         if(x->data<rt->data){
125             if(rt->lc)rt=rt->lc;
126             else{
127                 rt->lc=x;
128                 break;
129             }
130         }
131         else{
132             if(rt->rc)rt=rt->rc;
133             else{
134                 rt->rc=x;
135                 break;
136             }
137         }
138     }
139     x->prt=rt;
140     x=NULL;
141     for(;rt;rt=rt->prt){
142         rt->refresh();
143         if(max(siz(rt->lc),siz(rt->rc))>A*rt->size)x=rt;
144     }
145     return x;
146 }
147 node *find(int x){
148     node *rt=root[T];
149     while(rt){
150         if(x==rt->data)return rt;
151         else if(x<rt->data)rt=rt->lc;
152         else rt=rt->rc;
153     }
154     return NULL;
155 }
156 node *erase(node *x){
157     if(x->lc&&x->rc){
158         node *y=findmax(x->lc);
159         x->data=http://www.mamicode.com/y->data;
160         return erase(y);
161     }
162     if(!x->lc&&!x->rc){
163         if(x->prt){
164             if(x==x->prt->lc)x->prt->lc=NULL;
165             else x->prt->rc=NULL;
166         }
167         else root[T]=NULL;
168     }
169     else if(x->lc&&!x->rc){
170         x->lc->prt=x->prt;
171         if(x->prt){
172             if(x==x->prt->lc)x->prt->lc=x->lc;
173             else x->prt->rc=x->lc;
174         }
175         else root[T]=x->lc;
176     }
177     else if(!x->lc&&x->rc){
178         x->rc->prt=x->prt;
179         if(x->prt){
180             if(x==x->prt->lc)x->prt->lc=x->rc;
181             else x->prt->rc=x->rc;
182         }
183         else root[T]=x->rc;
184     }
185     node *rt=x->prt;
186     delete x;
187     x=NULL;
188     for(;rt;rt=rt->prt){
189         rt->refresh();
190         if(max(siz(rt->lc),siz(rt->rc))>A*rt->size)x=rt;
191     }
192     return x;
193 }
194 node *findmax(node *x){
195     while(x->rc)x=x->rc;
196     return x;
197 }
198 void rebuild(node *rt){
199     cnt=0;
200     zorder(rt);
201     node *x=rebuild(1,cnt);
202     x->prt=rt->prt;
203     if(rt->prt){
204         if(rt==rt->prt->lc)rt->prt->lc=x;
205         else rt->prt->rc=x;
206     }
207     else root[T]=x;
208     removetree(rt);
209 }
210 void removetree(node *x){
211     if(!x)return;
212     removetree(x->lc);
213     removetree(x->rc);
214     delete x;
215 }
216 void zorder(node *x){
217     if(!x)return;
218     zorder(x->lc);
219     data[++cnt]=x->data;
220     zorder(x->rc);
221 }
222 node *rebuild(int l,int r){
223     if(l>r)return NULL;
224     int mid=(l+r)>>1;
225     node *x=new node(data[mid]);
226     x->lc=rebuild(l,mid-1);
227     if(x->lc)x->lc->prt=x;
228     x->rc=rebuild(mid+1,r);
229     if(x->rc)x->rc->prt=x;
230     x->refresh();
231     return x;
232 }
View Code

这里还有一份用pb_ds写的代码，你们要学会偷懒哈哈哈。

技术分享 
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<ext/pb_ds/assoc_container.hpp>
 5 #include<ext/pb_ds/tree_policy.hpp>
 6 #define lowbit(x) ((x)&(-(x)))
 7 using namespace std;
 8 using namespace __gnu_pbds;
 9 const int maxn=50010;
10 void CDQ(int,int);
11 void add(int,int);
12 void query(int,int);
13 void clear(int);
14 tree<int,null_mapped_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>T[maxn];
15 int n,x[maxn],y[maxn],z[maxn],a[maxn],b[maxn],ans=0;
16 bool cmp(int i,int j){return x[i]<x[j];}
17 int main(){
18 #define MINE
19 #ifdef MINE
20     freopen("partial_order.in","r",stdin);
21     freopen("partial_order.out","w",stdout);
22 #endif
23     scanf("%d",&n);
24     for(int i=1;i<=n;i++)scanf("%d",&x[i]);
25     for(int i=1;i<=n;i++)scanf("%d",&y[i]);
26     for(int i=1;i<=n;i++)scanf("%d",&z[i]);
27     CDQ(1,n);
28     printf("%d\n",ans);
29 #ifndef MINE
30     printf("\n-------------------------DONE-------------------------\n");
31     for(;;);
32 #endif
33     return 0;
34 }
35 void CDQ(int l,int r){
36     if(l>=r)return;
37     for(int i=l;i<=r;i++)a[i]=i;
38     sort(a+l,a+r+1,cmp);
39     int mid=(l+r)>>1;
40     for(int i=l;i<=r;i++){
41         if(a[i]<=mid)add(y[a[i]],z[a[i]]);
42         else query(y[a[i]],z[a[i]]);
43     }
44     for(int i=l;i<=r;i++)if(a[i]<=mid)clear(y[a[i]]);
45     CDQ(l,mid);
46     CDQ(mid+1,r);
47 }
48 void add(int x,int d){
49     while(x<=n){
50         T[x].insert(d);
51         x+=lowbit(x);
52     }
53 }
54 void query(int x,int d){
55     while(x){
56         ans+=T[x].order_of_key(d);
57         x-=lowbit(x);
58     }
59 }
60 void clear(int x){
61     while(x<=n&&!T[x].empty()){
62         T[x].clear();
63         x+=lowbit(x);
64     }
65 }
View Code

然而树套树的常数很大，极限数据要跑大概1.1s~1.2s(本地和COGS都是这样)，并且树套树并不好写(当然你可以用树状数组套线段树来减少代码量)，所以可以再用一次分治压掉一维，剩下最后一维就可以直接树状数组搞掉了。

考虑每次外层的分治，我们都是计算左半部分与右半部分之间的正序对数目，而对x排序之后x已经有序了，剩下无序的y和z可以用树套树维护。既然位置是初始有序的，而x被我们排序后也有序了，我们就可以再对x分治，这样里层的分治就变成了统计位置和x都在左半的元素与位置和x都在右半的元素之间的正序对数量(x在同一半的情况会被里层分治递归解决)。这样处理之后就只剩下y和z了，用扫描线把y压掉，直接用树状数组维护z即可。

为了实现方便，把位置在前一半的元素标记为ins(插入)。a是原序列，b是把x排序之后里层分治用的序列。

技术分享 
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=50010;
 6 struct A{
 7     int x,y,z;
 8     bool ins;
 9 }a[maxn],b[maxn];
10 void CDQ1(int,int);
11 void CDQ2(int,int);
12 void add(int,int);
13 int query(int);
14 bool cmpx(const A &x,const A &y){return x.x<y.x;}
15 bool cmpy(const A &x,const A &y){return x.y<y.y;}
16 int n,ans=0,c[maxn]={0};
17 int main(){
18     freopen("partial_order.in","r",stdin);
19     freopen("partial_order.out","w",stdout);
20     scanf("%d",&n);
21     for(int i=1;i<=n;i++)scanf("%d",&a[i].x);
22     for(int i=1;i<=n;i++)scanf("%d",&a[i].y);
23     for(int i=1;i<=n;i++)scanf("%d",&a[i].z);
24     CDQ1(1,n);
25     printf("%d\n",ans);
26     return 0;
27 }
28 void CDQ1(int l,int r){
29     if(l>=r)return;
30     int mid=(l+r)>>1;
31     CDQ1(l,mid);CDQ1(mid+1,r);
32     for(int i=l;i<=mid;i++)a[i].ins=true;
33     for(int i=mid+1;i<=r;i++)a[i].ins=false;
34     sort(a+l,a+r+1,cmpx);//sort x
35     copy(a+l,a+r+1,b+l);
36     CDQ2(l,r);
37 }
38 void CDQ2(int l,int r){
39     if(l>=r)return;
40     int mid=(l+r)>>1;
41     CDQ2(l,mid);CDQ2(mid+1,r);
42     sort(b+l,b+mid+1,cmpy);
43     sort(b+mid+1,b+r+1,cmpy);
44     int i=l,j=mid+1;
45     while(i<=mid&&j<=r){
46         if(b[i].y<b[j].y){
47             if(b[i].ins)add(b[i].z,1);
48             i++;
49         }
50         else{
51             if(!b[j].ins)ans+=query(b[j].z-1);
52             j++;
53         }
54     }
55     while(i<=mid){
56         if(b[i].ins)add(b[i].z,1);
57         i++;
58     }
59     while(j<=r){
60         if(!b[j].ins)ans+=query(b[j].z-1);
61         j++;
62     }
63     for(i=l;i<=mid;i++)if(b[i].ins)add(b[i].z,-1);
64 }
65 void add(int x,int d){
66     while(x<=n){
67         c[x]+=d;
68         x+=x&-x;
69     }
70 }
71 int query(int x){
72     int ans=0;
73     while(x){
74         ans+=c[x];
75         x&=x-1;
76     }
77     return ans;
78 }
View Code

还可以进一步优化，两层分治的排序都用归并排序，这样可以减小常数(对复杂度并没有影响)。t是里层的归并排序用的序列。

技术分享 
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=50010;
 6 struct A{
 7     int x,y,z;
 8     bool ins;
 9 }a[maxn],b[maxn],t[maxn];
10 void CDQ1(int,int);
11 void CDQ2(int,int);
12 void add(int,int);
13 int query(int);
14 int n,ans=0,c[maxn]={0};
15 int main(){
16     freopen("partial_order.in","r",stdin);
17     freopen("partial_order.out","w",stdout);
18     scanf("%d",&n);
19     for(int i=1;i<=n;i++)scanf("%d",&a[i].x);
20     for(int i=1;i<=n;i++)scanf("%d",&a[i].y);
21     for(int i=1;i<=n;i++)scanf("%d",&a[i].z);
22     CDQ1(1,n);
23     printf("%d\n",ans);
24     return 0;
25 }
26 void CDQ1(int l,int r){
27     if(l>=r)return;
28     int mid=(l+r)>>1;
29     CDQ1(l,mid);CDQ1(mid+1,r);
30     int i=l,j=mid+1,k=l;
31     while(i<=mid&&j<=r){
32         if(a[i].x<a[j].x){
33             a[i].ins=true;
34             b[k++]=a[i++];
35         }
36         else{
37             a[j].ins=false;
38             b[k++]=a[j++];
39         }
40     }
41     while(i<=mid){
42         a[i].ins=true;
43         b[k++]=a[i++];
44     }
45     while(j<=r){
46         a[j].ins=false;
47         b[k++]=a[j++];
48     }
49     copy(b+l,b+r+1,a+l);
50     CDQ2(l,r);
51 }
52 void CDQ2(int l,int r){
53     if(l>=r)return;
54     int mid=(l+r)>>1;
55     CDQ2(l,mid);CDQ2(mid+1,r);
56     int i=l,j=mid+1,k=l;
57     while(i<=mid&&j<=r){
58         if(b[i].y<b[j].y){
59             if(b[i].ins)add(b[i].z,1);
60             t[k++]=b[i++];
61         }
62         else{
63             if(!b[j].ins)ans+=query(b[j].z-1);
64             t[k++]=b[j++];
65         }
66     }
67     while(i<=mid){
68         if(b[i].ins)add(b[i].z,1);
69         t[k++]=b[i++];
70     }
71     while(j<=r){
72         if(!b[j].ins)ans+=query(b[j].z-1);
73         t[k++]=b[j++];
74     }
75     for(i=l;i<=mid;i++)if(b[i].ins)add(b[i].z,-1);
76     copy(t+l,t+r+1,b+l);
77 }
78 void add(int x,int d){
79     while(x<=n){
80         c[x]+=d;
81         x+=x&-x;
82     }
83 }
84 int query(int x){
85     int ans=0;
86     while(x){
87         ans+=c[x];
88         x&=x-1;
89     }
90     return ans;
91 }
View Code

这里是三种写法的对比(pb_ds就别贴了……)，不得不说CDQ的威力真是太强大了……

树套树：

技术分享

CDQ(没有用归并排序优化)：

技术分享

CDQ(归并排序)：

技术分享

这个故事还告诉我们一个道理，写CDQ一定要用归并卡常……

 

话说我博客真是乱乱乱……我需要整理整理……

四维偏序


联系
我们