COGS 2479 偏序题解

【题意】

给定一个有n个元素的序列，元素编号为1~n，每个元素有三个属性a,b,c，求序列中满足i<j且a_i<a_j且b_i<b_j且c_i<c_j的数对(i,j)的个数。

对于30%的数据，n<=5000。

对于100%的数据，1<=n<=50000(原题写错了哈哈)，保证所有的a_i、b_i、c_i分别组成三个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+树状数组水掉三维偏序之后的脑洞的产物……貌似在报复社会……

自己真是玩疯了……

巴特西

COGS 2479 偏序题解

最新文章

热门文章

巴特西

COGS 2479 偏序 题解

最新文章

热门文章

COGS 2479 偏序题解