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;

}

巴特西

[HZOI2016]偏序&[HZOI2015]偏序II K维偏序问题

description

data range

solution

code

最新文章

热门文章