多维偏序
在编程中，经常有多维偏序的应用。这里讲一下二维，三维和更高维偏序的板子
二维偏序 HDU1541 Stars
按照x的坐标进行排序，然后用树状数组统计y。
这里就是一个逆序对
代码：
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll n,sum[320010],ans[320010];
struct node{
ll x,y,id;
}a[320010];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
ll y=10,len=1;
while(y<=x){
y=(y<<3)+(y<<1);
len++;
}
while(len--){
y/=10;
putchar(x/y+48);
x%=y;
}
}
inline ll lowbit(ll x){
return x&(-x);
}
inline void update(ll x){
for(; x<=n; x+=lowbit(x)) sum[x]++;
}
inline ll query(ll x){
ll ans=0;
for(; x; x-=lowbit(x)) ans+=sum[x];
return ans;
}
inline bool cmp(node a,node b){
return a.x==b.x?a.y<b.y:a.x<b.x;
}
int main(){
while(scanf("%lld",&n)!=EOF){
memset(a,0,sizeof(a));
memset(sum,0,sizeof(sum));
memset(ans,0,sizeof(ans));
for(ll i=1; i<=n; i++){
a[i].x=read();
a[i].y=read();
a[i].id=i;
}
sort(a+1,a+1+n,cmp);
for(ll i=1; i<=n; i++){
update(a[i].id);
ans[query(a[i].id-1)]++;
}
for(ll i=0; i<n; i++){
write(ans[i]);
putchar('\n');
}
}
return 0;
}三维偏序 luogu3810
CDQ套CDQ
按第一个属性排序，再按后两个跑CDQ
代码：
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define N 100010
#define M 200010
#define ll long long
using namespace std;
struct node{
ll x,y,z,ans,w;
}a[N],b[N];
ll n,m,cnt[M],_,sum[M];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline void write(ll x){
ll y=10,len=1;
while(y<=x){
y=(y<<3)+(y<<1);
len++;
}
while(len--){
y/=10;
putchar(x/y+48);
x%=y;
}
}
inline bool cmpx(node a,node b){
if(a.x!=b.x) return a.x<b.x;
if(a.y!=b.y) return a.y<b.y;
if(a.z!=b.z) return a.z<b.z;
}
inline bool cmpy(node a,node b){
return a.y==b.y?a.z<b.z:a.y<b.y;
}
inline ll lowbit(ll x){
return x&(-x);
}
inline ll query(ll x){
ll ans=0;
for(; x; x-=lowbit(x)) ans+=sum[x];
return ans;
}
inline void update(ll x,ll val){
for(; x<=m; x+=lowbit(x)) sum[x]+=val;
}
void cdq(ll l,ll r){
if(l==r) return;
ll mid=(l+r)>>1;
cdq(l,mid); cdq(mid+1,r);
sort(a+l,a+mid+1,cmpy);
sort(a+mid+1,a+r+1,cmpy);
ll i=mid+1,j=l;
while(i<=r){
while(a[j].y<=a[i].y&&j<=mid){
update(a[j].z,a[j].w);
j++;
}
a[i].ans+=query(a[i].z);
i++;
}
for(ll i=l; i<j; i++) update(a[i].z,-a[i].w);
}
int main(){
_=read(); m=read();
for(ll i=1; i<=_; i++){
b[i].x=read();
b[i].y=read();
b[i].z=read();
}
sort(b+1,b+_+1,cmpx);
ll c=0;
for(ll i=1; i<=_; i++){
c++;
if(b[i].x!=b[i+1].x||b[i].y!=b[i+1].y||b[i].z!=b[i+1].z){
a[++n]=b[i];
a[n].w=c;
c=0;
}
}
cdq(1,n);
for(ll i=1; i<=n; i++) cnt[a[i].ans+a[i].w-1]+=a[i].w;
for(ll i=0; i<_; i++){
write(cnt[i]);
putchar('\n');
}
return 0;
}更高维的偏序就不一样了
四维偏序 XJOI ctps
实测这题bitset更快！！！
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
#define N 30010
using namespace std;
ll n,m,k,C;
struct node{
double x[4];
ll id;
}a[N],b[N];
bitset<N> now,ans[N];
inline double read(){
double x=0,y=1;
ll tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=x*10+(ch^48);
ch=getchar();
}
if(ch=='.'){
ch=getchar();
while(isdigit(ch)){
x+=(y/=10)*(ch^48);
ch=getchar();
}
}
return tmp*x;
}
inline bool cmp(node a,node b){
return a.x[C]<b.x[C];
}
int main(){
n=read();
for(ll i=1; i<=n; i++){
for(ll j=0; j<4; j++) a[i].x[j]=read();
a[i].id=i;
}
m=read();
for(ll i=1; i<=m; i++){
for(ll j=0; j<4; j++) b[i].x[j]=read();
b[i].id=i;
ans[i].set();
}
for(C=0; C<4; C++){
sort(a+1,a+n+1,cmp);
sort(b+1,b+m+1,cmp);
now=0; ll i=1;
for(ll j=1; j<=m; j++){
while(i<=n&&a[i].x[C]<=b[j].x[C]) now[a[i++].id]=1;
ans[b[j].id]&=now;
}
}
for(ll i=1; i<=m; i++) printf("%lld\n",ans[i].count());
return 0;
}