cdq+bitset处理高维偏序

高维偏序

CDQ分治

假设处理的区间为 $[l,r]$ ，CDQ分治的过程：

1. 如果 $l\ge r$ ，返回。
2. 设区间中点为 $mid$ ，递归处理 $[l,mid]$ 和 $[mid+1,r]$。
3. 利用单调性处理横跨 $mid$ 的点对，不横跨 $mid$ 的点对将在递归中被解决。

bitset

定义 bitset<maxn>a[i][j] 代表第 $i$ 个数在第 $j$ 个属性上与其他元素的大小关系。

如果 $a[i][j][k]=1$ ，代表第 $i$ 个数在第 $j$ 个属性上大于等于第 $k$ 个数，即 $v[i][j]\ge v[k][j]$ 。

怎么去求解呢，只需要对每个属性进行排序，从小到大遍历，每次在 $bitset$ 这个位置上 $set$ 个 $1$，然后每次让对应的 $a[id][j]=tmp$ 即可。

那么第 $i$ 个数在第 $j$ 个属性上大于等于其他数的个数即为 $a[i][j].count()$ 。

所有属性都大于等于的个数，那么就是按位与之后的 $count$ 。

P3810 【模板】三维偏序（陌上花开）

cdq思路：

只需要解决如何求横跨 $mid$ 的点对，先按 $a$ 属性排序，那么 $[l,mid].a<[mid+1,r].a$，

然后我们再对 $[l,mid],[mid+1,r]$ 按 $b$ 属性分别排序（保证了 $a$ 属性的顺序），然后 $c$ 属性的话按照双指针+树状数组即可统计。

需要注意的是，会有三个属性相同的情况需要特殊处理。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
//#include<random>
//#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define node array<int,5>
#define pii pair<int,int>
#define lowbit(x) x&-x
array<int,200020>c;
struct Tree{void add(int i,int x){for(;i<=200000;i+=lowbit(i))c[i]+=x;}int sum(int i){int ans=0;for(;i;i-=lowbit(i))ans+=c[i];return ans;}
}T;
vector<node>a;
int ans[200020];
int cnt[200020];
void cdq(int l,int r){if(l>=r)return ;int mid=l+r>>1;cdq(l,mid);cdq(mid+1,r);sort(a.begin()+l,a.begin()+mid+1,[](node x,node y){if(x[2]!=y[2])return x[2]<y[2];return x[3]<y[3];});sort(a.begin()+mid+1,a.begin()+r+1,[](node x,node y){if(x[2]!=y[2])return x[2]<y[2];return x[3]<y[3];});int L=l;for(int i=mid+1;i<=r;i++){while(L<=mid&&a[L][2]<=a[i][2])T.add(a[L][3],a[L][4]),L++;ans[a[i][0]]+=T.sum(a[i][3]);}for(int i=l;i<L;i++){T.add(a[i][3],-a[i][4]);}
}
void solve(){int n,k;cin>>n>>k;int tn=n;a=vector<node>(n+1);for(int i=1;i<=n;i++){cin>>a[i][1]>>a[i][2]>>a[i][3];a[i][4]=1;// a[i][0]=i;}sort(a.begin()+1,a.end(),[](node x,node y){if(x[1]!=y[1])return x[1]<y[1];if(x[2]!=y[2])return x[2]<y[2];return x[3]<y[3];});vector<node>b;b.push_back({0,0,0,0,0});for(int i=2;i<=n;i++){if(a[i][1]==a[i-1][1]&&a[i][2]==a[i-1][2]&&a[i][3]==a[i-1][3]){a[i][4]+=a[i-1][4];}else {b.push_back(a[i-1]);}}b.push_back(a[n]);a=b;n=a.size()-1;for(int i=1;i<=n;i++){a[i][0]=i;ans[i]+=a[i][4]-1;}cdq(1,n);for(int i=1;i<=n;++i){cnt[ans[a[i][0]]]+=a[i][4];}for(int i=0;i<tn;i++)cout<<cnt[i]<<'\n';
}   
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t=1;// cin>>t;while(t--)solve();return 0;
}

bitset思路：

需要用到分块，以时间换空间。需要处理同一个属性相同的数。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>
//#include<random>
//#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
bitset<100020>a[8010];
int s[5][100020];
int p[5][100020];
void solve(){int n,K;cin>>n>>K;for(int i=1;i<=n;i++){for(int j=1;j<=3;j++){cin>>s[j][i];}}for(int i=1;i<=n;i++)for(int j=1;j<=3;j++)p[j][i]=i;for(int j=1;j<=3;j++){sort(p[j]+1,p[j]+1+n,[&](int x,int y){return s[j][x]<s[j][y];});}vector<int>ans(n+1,0),cnt(n+1,0);for(int q=1;q<=n;q+=8000){int P=q-1,len=min(8000,n-q+1);for(int i=1;i<=len;i++)a[i].set();for(int j=1;j<=3;j++){bitset<100020>b;b.reset();for(int i=1;i<=n;i++){int k=i;for(k=i;k<=n&&s[j][p[j][i]]==s[j][p[j][k]];k++){b.set(p[j][k]);}for(k=i;k<=n&&s[j][p[j][i]]==s[j][p[j][k]];k++){if(p[j][k]>P&&p[j][k]<=P+len)a[p[j][k]-P]&=b;}i=k-1;}}for(int i=1;i<=len;i++)ans[a[i].count()-1]++;}// for(int i=1;i<=n;i++)ans[cnt[i]]++;for(int i=0;i<n;i++)cout<<ans[i]<<'\n';
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t=1;// cin>>t;while(t--)solve();return 0;
}