CDQ分治2

CDQ套CDQ：四維偏序問題

題目來源：COGS 2479 偏序

#define LEFT 0 #define RIGHT 1struct Node{int a,b,c,d,bg;}; Node q[_],tmp1[_],tmp2[_]; int aa,bb,cc,dd,n; long long Ans;void cdq2(RG int L,RG int R){if(L == R)return;RG int mid = (L+R)>>1; cdq2(L,mid); cdq2(mid+1,R);RG int oo = L , l = L , r = mid + 1;while(l <= mid && r <= R){if(tmp1[l].c < tmp1[r].c){if(tmp1[l].bg == LEFT)BIT:: Update(tmp1[l].d);tmp2[oo++] = tmp1[l++];}else {if(tmp1[r].bg == RIGHT)Ans += BIT::Query(tmp1[r].d);tmp2[oo++] = tmp1[r++];}}while(l <= mid)tmp2[oo++] = tmp1[l++];while(r <= R){if(tmp1[r].bg == RIGHT)Ans += BIT::Query(tmp1[r].d) ;tmp2[oo++] = tmp1[r++];}for(RG int i = L; i <= R; i ++){if(tmp2[i].bg == LEFT)BIT::Clear(tmp2[i].d);tmp1[i] = tmp2[i];}return; }void cdq1(int L,int R){if(L == R)return;RG int mid = (L+R)>>1; cdq1(L,mid); cdq1(mid+1,R);RG int oo = L , l = L ,r = mid + 1;while(l <= mid && r <= R){if(q[l].b < q[r].b)q[l].bg = LEFT ,tmp1[oo++] = q[l++] ;else q[r].bg = RIGHT , tmp1[oo++] = q[r++] ;}while(l <= mid)q[l].bg = LEFT , tmp1[oo++] = q[l++];while(r <= R)q[r].bg = RIGHT , tmp1[oo++] = q[r++];for(RG int i = L; i <= R; i ++)q[i] = tmp1[i];cdq2(L,R); }int main(){freopen("partial_order.in","r",stdin);freopen("partial_order.out","w",stdout);n = gi();for(RG int i = 1; i <= n; i ++)q[i].a = i; for(RG int i = 1; i <= n; i ++)q[i].b = gi(); for(RG int i = 1; i <= n; i ++)q[i].c = gi(); for(RG int i = 1; i <= n; i ++)q[i].d = gi(); Ans = 0; cdq1(1,n);cout<<Ans; return 0; }

CDQ套CDQ套CDQ：五維偏序問題

題目來源：COGS 2580 偏序 \(II\)

#define LEFT 0 #define RIGHT 1struct Node{int d1,d2,d3,d4,d5,bg[2];}; Node q[_] , tmp1[_] , tmp2[_] , tmp3[_]; int n; long long ans;IL bool Check(RG int id,RG int opt) {return tmp2[id].bg[0]==opt && tmp2[id].bg[1]==opt;}void cdq3(RG int L,RG int R){ //cdq分治解決三維偏序問題 if(L == R)return;RG int mid = (L+R)>>1; cdq3(L,mid); cdq3(mid+1,R);RG int l = L , r = mid+1 , oo = L-1;while(l <= mid && r <= R){if(tmp2[l].d4 < tmp2[r].d4){if(Check(l,LEFT))BIT::Update(tmp2[l].d5);tmp3[++oo] = tmp2[l++];}else{if(Check(r,RIGHT))ans += BIT::Query(tmp2[r].d5);tmp3[++oo] = tmp2[r++];}}while(l <= mid)tmp3[++oo] = tmp2[l++];while(r <= R){if(Check(r,RIGHT))ans += BIT::Query(tmp2[r].d5);tmp3[++oo] = tmp2[r++];}for(RG int i = L; i <= R; i ++){if(Check(i,LEFT))BIT::Clear(tmp2[i].d5);tmp2[i] = tmp3[i];}return;}void cdq2(RG int L,RG int R){ //消去第三維的影響 if(L == R)return;RG int mid = (L+R)>>1; cdq2(L,mid); cdq2(mid+1,R);RG int l = L , r = mid+1 , oo = L-1;while(l <= mid && r <= R){if(tmp1[l].d3 < tmp1[r].d3)tmp1[l].bg[1] = LEFT , tmp2[++oo] = tmp1[l++];elsetmp1[r].bg[1] = RIGHT , tmp2[++oo] = tmp1[r++];}while(l <= mid)tmp1[l].bg[1] = LEFT , tmp2[++oo] = tmp1[l++];while(r <= R)tmp1[r].bg[1] = RIGHT , tmp2[++oo] = tmp1[r++];for(RG int i = L; i <= R; i ++)tmp1[i] = tmp2[i];cdq3(L,R); }void cdq1(RG int L,RG int R){ //消去第二維的影響 if(L == R)return;RG int mid = (L+R)>>1; cdq1(L,mid); cdq1(mid+1,R);RG int l = L , r = mid+1 , oo = L-1;while(l <= mid && r <= R){if(q[l].d2 < q[r].d2)q[l].bg[0] = LEFT , tmp1[++oo] = q[l++];else q[r].bg[0] = RIGHT , tmp1[++oo] = q[r++];} while(l<=mid)q[l].bg[0] = LEFT , tmp1[++oo] = q[l++];while(r<=R)q[r].bg[0] = RIGHT , tmp1[++oo] = q[r++];for(RG int i = L; i <= R; i ++)q[i] = tmp1[i]; cdq2(L,R); }int main(){freopen("partial_order_two.in","r",stdin);freopen("partial_order_two.out","w",stdout);n = gi();for(RG int i = 1; i <= n; i ++)q[i].d1 = i;for(RG int i = 1; i <= n; i ++)q[i].d2 = gi();for(RG int i = 1; i <= n; i ++)q[i].d3 = gi();for(RG int i = 1; i <= n; i ++)q[i].d4 = gi();for(RG int i = 1; i <= n; i ++)q[i].d5 = gi();//sort_a 消去第一維的影響 ans = 0; cdq1(1,n);cout << ans; return 0; }

轉載于:https://www.cnblogs.com/Guess2/p/8370972.html

總結

以上是生活随笔為你收集整理的CDQ分治嵌套模板:多维偏序问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。