description
Cogs:
[HZOI2016]偏序
[HZOI2015]偏序 II
data range
\[n\le 5\times 10^4
\]
\]
solution
嵌套\(CDQ\)的应用
前面的\(CDQ\)用来对前面的维度进行合并和标记
最后一个\(CDQ\)统计答案
一开始用的\(4\)重嵌套\(CDQ\)，要\(3.7s\)...
const int K=5;//K维偏序
int n,ans;
struct node{int d[K],tg[K];}Q[K][N];
bool cmp(node x,node y,int k){
if(k==K-1)return x.d[k]<y.d[k];
return x.d[k]<y.d[k]||(x.d[k]==y.d[k]&&x.d[k+1]==y.d[k+1]);
}
il int pd(node x,int v){
for(RG int i=1;i<K-1;i++)if(x.tg[i]!=v)return 0;return 1;
}
void cdq(int l,int r,int k){
if(l==r)return;RG int mid=(l+r)>>1;cdq(l,mid,k);cdq(mid+1,r,k);
for(RG int i=l,p1=l,p2=mid+1,sum=0;i<=r;i++)
if(p2>r||(p1<=mid&&cmp(Q[k-1][p1],Q[k-1][p2],k))){
if(k==K-1&&pd(Q[k-1][p1],0))sum++;
Q[k][i]=Q[k-1][p1++];Q[k][i].tg[k]=0;
}
else{
if(k==K-1&&pd(Q[k-1][p2],1))ans+=sum;
Q[k][i]=Q[k-1][p2++];Q[k][i].tg[k]=1;
}
for(RG int i=l;i<=r;i++)Q[k-1][i]=Q[k][i];if(k!=K-1)cdq(l,r,k+1);
}
之后无奈地把一重\(CDQ\)换成了\(BIT\)，只要\(1.6s\)，看来\(BIT\)常数要小些
const int K=5;//K维偏序
int n,ans;
struct node{int d[K],tg[K];}Q[K][N];
bool cmp(node x,node y,int k){
if(k==K-2)return x.d[k]<y.d[k];
return x.d[k]<y.d[k]||(x.d[k]==y.d[k]&&x.d[k+1]==y.d[k+1]);
}
il int pd(node x,int v){
for(RG int i=1;i<K-2;i++)if(x.tg[i]!=v)return 0;return 1;
}
int t[N];
il void insert(int i){for(i;i<=n;i+=(i&-i))t[i]++;}
il void clear(int i){for(i;i<=n;i+=(i&-i))t[i]=0;}
il int query(int i){int r=0;for(i;i;i-=(i&-i))r+=t[i];return r;}
void cdq(int l,int r,int k){
if(l==r)return;RG int mid=(l+r)>>1;cdq(l,mid,k);cdq(mid+1,r,k);
for(RG int i=l,p1=l,p2=mid+1,sum=0;i<=r;i++)
if(p2>r||(p1<=mid&&cmp(Q[k-1][p1],Q[k-1][p2],k))){
if(k==K-2&&pd(Q[k-1][p1],0))insert(Q[k-1][p1].d[k+1]);
Q[k][i]=Q[k-1][p1++];Q[k][i].tg[k]=0;
}
else{
if(k==K-2&&pd(Q[k-1][p2],1))ans+=query(Q[k-1][p2].d[k+1]-1);
Q[k][i]=Q[k-1][p2++];Q[k][i].tg[k]=1;
}
for(RG int i=l;i<=r;i++)Q[k-1][i]=Q[k][i],clear(Q[k][i].d[k+1]);
if(k!=K-2)cdq(l,r,k+1);
}
code
切换题目只须修改\(K\)的值即可
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define Cpy(x,y) memcpy(x,y,sizeof(x))
#define Set(x,y) memset(x,y,sizeof(x))
#define FILE "partial_order"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-6;
const int mod=1e9+7;
const int N=50010;
const int M=1e6+10;
const int inf=2147483647;
const ll INF=1e18+1;
const ll P=100000;
namespace IO{
const int maxn=(1<<21)+1;
char ibuf[maxn],*iS,*iT,c;int f;
inline char getc(){
return iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,maxn,stdin),iS==iT?EOF:*iS++):*iS++;
}
template<class T>inline void read(T &x){
for(f=1,c=getc();(c<'0'||c>'9');c=getc())f=c=='-'?-1:1;
for(x=0;(c>='0'&&c<='9');c=getc())x=(x<<1)+(x<<3)+(c^48);
x*=f;
}
}
using IO::read;
il void file(){
srand(time(NULL)+rand());
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
}
const int K=5;//K维偏序
int n,ans;
struct node{int d[K],tg[K];}Q[K][N];
bool cmp(node x,node y,int k){
if(k==K-2)return x.d[k]<y.d[k];
return x.d[k]<y.d[k]||(x.d[k]==y.d[k]&&x.d[k+1]==y.d[k+1]);
}
il int pd(node x,int v){
for(RG int i=1;i<K-2;i++)if(x.tg[i]!=v)return 0;return 1;
}
int t[N];
il void insert(int i){for(i;i<=n;i+=(i&-i))t[i]++;}
il void clear(int i){for(i;i<=n;i+=(i&-i))t[i]=0;}
il int query(int i){int r=0;for(i;i;i-=(i&-i))r+=t[i];return r;}
void cdq(int l,int r,int k){
if(l==r)return;RG int mid=(l+r)>>1;cdq(l,mid,k);cdq(mid+1,r,k);
for(RG int i=l,p1=l,p2=mid+1,sum=0;i<=r;i++)
if(p2>r||(p1<=mid&&cmp(Q[k-1][p1],Q[k-1][p2],k))){
if(k==K-2&&pd(Q[k-1][p1],0))insert(Q[k-1][p1].d[k+1]);
Q[k][i]=Q[k-1][p1++];Q[k][i].tg[k]=0;
}
else{
if(k==K-2&&pd(Q[k-1][p2],1))ans+=query(Q[k-1][p2].d[k+1]-1);
Q[k][i]=Q[k-1][p2++];Q[k][i].tg[k]=1;
}
for(RG int i=l;i<=r;i++)Q[k-1][i]=Q[k][i],clear(Q[k][i].d[k+1]);
if(k!=K-2)cdq(l,r,k+1);
}
int main()
{
file();read(n);
for(RG int k=0;k<K;k++)
for(RG int i=1;i<=n;i++){
if(k)read(Q[0][i].d[k]);
else Q[0][i].d[k]=i;
Q[0][i].tg[k]=-1;
}
cdq(1,n,1);
printf("%d\n",ans);
return 0;
}