cogs2479 偏序 cdq+树套树

cdq+树状数组套替罪羊树。

cdq归并a，树套树解决b,c.

记住平衡树树根不能暴力清零！！！
// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define Fname "partial_order"

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

typedef long long ll;

il int gi(){

    rg int x=0,f=1;rg char ch=getchar();

    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*f;

}

const int maxn=50001;

int n,ans;

struct frog{int a,b,c;};

frog f[maxn];

const double alpha=0.77777777;

class sgt{

public:int rt[maxn],tot;

private:

	int ch[maxn*15][2],siz[maxn*15],val[maxn*15],div[maxn];

	il vd dfs(const int&x){if(x)dfs(ch[x][0]),div[++div[0]]=x,dfs(ch[x][1]);}

	il int divide(int l,int r){

#define mid ((l+r)>>1)

		ch[div[mid]][0]=divide(l,mid-1);

		ch[div[mid]][1]=divide(mid+1,r);

		siz[div[mid]]=r-l+1;

		return div[mid];

#undef mid

	}

	il vd rebuild(int*x){div[0]=0,dfs(*x),*x=divide(1,div[0]);}

	il int*_ins(int&x,const int&num){

		if(!x){x=++tot;siz[x]=1;val[x]=num;ch[x][0]=ch[x][1]=0;return NULL;}

		int*p=_ins(ch[x][num>val[x]],num);

		siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;

		if((siz[x]>>2)*3+2<min(siz[ch[x][0]],siz[ch[x][1]]))p=&x;

		return p;

	}

public:

	sgt(){rep(i,0,n)rt[i]=0;siz[0]=0;}

	il vd ins(int root,int num){int*p=_ins(root[rt],num);if(p)rebuild(p);}

	il int query(int root,int num){

		int ret=0,x=rt[root];

		while(x)

			if(num<val[x])x=ch[x][0];

			else ret+=siz[ch[x][0]]+1,x=ch[x][1];

		return ret;

	}

};

class bit{

#define lb(o) ((o)&-(o))

public:

	sgt s;

	il vd update(int pos,int num){while(pos<=n)s.ins(pos,num),pos+=lb(pos);}

	il vd query(int pos,int num){while(pos)ans+=s.query(pos,num),pos-=lb(pos);}

	il vd hehe(int pos){while(pos<=n)s.rt[pos]=0,pos+=lb(pos);}

#undef lb

};

il vd cdq(int l,int r){

	if(l==r)return;

	static frog tmp[maxn];

	static bit g;

#define mid ((l+r)>>1)

	cdq(l,mid),cdq(mid+1,r);

	g.s.tot=0;

	int _l=l,_r=mid+1,L=mid+1,R=r+1,cnt=l;

	while((_l^L)&&(_r^R))

		if(f[_l].a<f[_r].a)g.update(f[_l].b,f[_l].c),tmp[cnt++]=f[_l++];

		else g.query(f[_r].b,f[_r].c),tmp[cnt++]=f[_r++];

	while(_r^R)g.query(f[_r].b,f[_r].c),tmp[cnt++]=f[_r++];

	for(rg int i=l;i<_l;++i)g.hehe(f[i].b);

	while(_l^L)tmp[cnt++]=f[_l++];

#undef mid

	rep(i,l,r)f[i]=tmp[i];

}

int main(){

	freopen(Fname".in","r",stdin);

	freopen(Fname".out","w",stdout);

	n=gi();

	rep(i,1,n)f[i].a=gi();

	rep(i,1,n)f[i].b=gi();

	rep(i,1,n)f[i].c=gi();

	cdq(1,n),printf("%d\n",ans);

	return 0;

}
巴特西

cogs2479 偏序 cdq+树套树

最新文章

热门文章
