【题意】
给定一个有n个元素的序列，元素编号为1~n，每个元素有三个属性a,b,c，求序列中满足i<j且a<a且b<b且c<c的数对(i,j)的个数。
对于30%的数据，n<=5000。
对于100%的数据，1<=n<=50000(原题写错了哈哈)，保证所有的a、b、c分别组成三个1~n的排列。
【解法】
标题已经说了这是偏序，读完题，这就是个四维偏序模板题(位置一维，a,b,c剩下三维)。
解法多多，我用的是CDQ树套树(树套树写的树状数组套替罪羊树，毕竟在我的印象里替罪羊树在随机数据下跑得飞快)。
第一维已经有序，不用我们预处理，这样就可以按第一维(位置)分治，再把第二维(a)排序，剩下的第三维(b)和第四维(c)直接树套树就可以了(我用的是第三维树状数组，第四维平衡树)。
当然写CDQ套CDQ+树状数组应该也可以，然而本鶸渣不会写……
也可以写树套树套树……然而怎么写……
贴个代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define siz(x) ((x)?((x)->size):(0))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=;
const double A=0.65;
struct node{//Scapegoat Tree
int data,size;
node *lc,*rc,*prt;
node(int d=):data(d),size(),lc(NULL),rc(NULL),prt(NULL){}
inline void refresh(){size=siz(lc)+siz(rc)+;}
}*root[maxn];
struct B{
int id,a,b,c;
bool operator<(const B &a)const{return this->a<a.a;}
}a[maxn],b[maxn];
void CDQ(int,int);
void add(int,int);
void del(int,int);
int query(int,int);
void insert(int);
void erase(int);
int rank(int);
node *insert(node*);
node *find(int);
node *erase(node*);
node *findmax(node*);
void rebuild(node*);
void zorder(node*);
void removetree(node*);
node *rebuild(int,int);
int n,T,cnt,data[maxn];
long long ans=0ll;
int main(){
#define MINE
#ifdef MINE
freopen("partial_order.in","r",stdin);
freopen("partial_order.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=;i<=n;i++)a[i].id=i;
for(int i=;i<=n;i++)scanf("%d",&a[i].a);
for(int i=;i<=n;i++)scanf("%d",&a[i].b);
for(int i=;i<=n;i++)scanf("%d",&a[i].c);
CDQ(,n);
printf("%lld",ans);
#ifndef MINE
printf("\n-------------------------DONE-------------------------\n");
for(;;);
#endif
return ;
}
void CDQ(int l,int r){
if(l>=r)return;
int mid=(l+r)>>;
CDQ(l,mid);
CDQ(mid+,r);
int i=l,j=mid+,k=l;
while(i<=mid&&j<=r){
if(a[i]<a[j])b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=mid)b[k++]=a[i++];
while(j<=r)b[k++]=a[j++];
for(int i=l;i<=r;i++){
a[i]=b[i];
if(a[i].id<=mid)add(a[i].b,a[i].c);
else ans+=query(a[i].b,a[i].c);
}
for(int i=l;i<=r;i++)if(a[i].id<=mid)del(a[i].b,a[i].c);
}
void add(int x,int d){
while(x<=n){
T=x;
insert(d);
x+=lowbit(x);
}
}
void del(int x,int d){
while(x<=n){
T=x;
erase(d);
x+=lowbit(x);
}
}
int query(int x,int d){
int ans=;
while(x){
T=x;
ans+=rank(d);
x-=lowbit(x);
}
return ans;
}
void insert(int x){
node *rt=insert(new node(x));
if(rt)rebuild(rt);
}
void erase(int x){
node *rt=erase(find(x));
if(rt)rebuild(rt);
}
int rank(int x){
node *rt=root[T];
int ans=;
while(rt){
if(x<=rt->data)rt=rt->lc;
else{
ans+=siz(rt->lc)+;
rt=rt->rc;
}
}
return ans;
}
node *insert(node *x){
if(!root[T]){
root[T]=x;
return NULL;
}
node *rt=root[T];
for(;;){
if(x->data<rt->data){
if(rt->lc)rt=rt->lc;
else{
rt->lc=x;
break;
}
}
else{
if(rt->rc)rt=rt->rc;
else{
rt->rc=x;
break;
}
}
}
x->prt=rt;
x=NULL;
for(;rt;rt=rt->prt){
rt->refresh();
if(max(siz(rt->lc),siz(rt->rc))>A*rt->size)x=rt;
}
return x;
}
node *find(int x){
node *rt=root[T];
while(rt){
if(x==rt->data)return rt;
else if(x<rt->data)rt=rt->lc;
else rt=rt->rc;
}
return NULL;
}
node *erase(node *x){
if(x->lc&&x->rc){
node *y=findmax(x->lc);
x->data=y->data;
return erase(y);
}
if(!x->lc&&!x->rc){
if(x->prt){
if(x==x->prt->lc)x->prt->lc=NULL;
else x->prt->rc=NULL;
}
else root[T]=NULL;
}
else if(x->lc&&!x->rc){
x->lc->prt=x->prt;
if(x->prt){
if(x==x->prt->lc)x->prt->lc=x->lc;
else x->prt->rc=x->lc;
}
else root[T]=x->lc;
}
else if(!x->lc&&x->rc){
x->rc->prt=x->prt;
if(x->prt){
if(x==x->prt->lc)x->prt->lc=x->rc;
else x->prt->rc=x->rc;
}
else root[T]=x->rc;
}
node *rt=x->prt;
delete x;
x=NULL;
for(;rt;rt=rt->prt){
rt->refresh();
if(max(siz(rt->lc),siz(rt->rc))>A*rt->size)x=rt;
}
return x;
}
node *findmax(node *x){
while(x->rc)x=x->rc;
return x;
}
void rebuild(node *rt){
cnt=;
zorder(rt);
node *x=rebuild(,cnt);
x->prt=rt->prt;
if(rt->prt){
if(rt==rt->prt->lc)rt->prt->lc=x;
else rt->prt->rc=x;
}
else root[T]=x;
removetree(rt);
}
void removetree(node *x){
if(!x)return;
removetree(x->lc);
removetree(x->rc);
delete x;
}
void zorder(node *x){
if(!x)return;
zorder(x->lc);
data[++cnt]=x->data;
zorder(x->rc);
}
node *rebuild(int l,int r){
if(l>r)return NULL;
int mid=(l+r)>>;
node *x=new node(data[mid]);
x->lc=rebuild(l,mid-);
if(x->lc)x->lc->prt=x;
x->rc=rebuild(mid+,r);
if(x->rc)x->rc->prt=x;
x->refresh();
return x;
}
【后记】
这个题是用CDQ+树状数组水掉三维偏序之后的脑洞的产物……貌似在报复社会……
自己真是玩疯了……