【2020五校联考NOIP #3】序列

题面传送门

原题题号：Codeforces Gym 101821B

题意：

给出一个排列 \(p\)，要你找出一个最长上升子序列（LIS）和一个最长下降子序列（LDS），满足它们没有公共元素。或告知无解。

\(1 \leq n \leq 5 \times 10^5\)。

wxh 太强辣！wxhtxdy！

首先可以发现一个小性质，那就是原序列任意一个 LIS 和 LDS 至多只有 \(1\) 个公共元素。

假设它们有 \(2\) 个公共元素 \(p_i,p_j(i<j)\)，由于 \(p_i,p_j\) 同时包含在一个 LIS 中，必有 \(p_i<p_j\)。又因为 \(p_i,p_j\) 同时包含在一个 LDS 中，\(p_i>p_j\)，矛盾！

我们预处理出 \(f_i\) 表示包含 \(p_i\) 的 LDS 个数，\(sum\) 表示总的 LDS 个数。由于这些数可能很大，我们可以将它模上一个比较大的数。

由于我们只需构造出一组合法的解，我们的目标就是检验是否存在一个合法的 LIS，然后顺带着找出原序列扣除掉这个 LIS 后得到的序列 \(p'\) 的一个 LDS。

我们考虑不合法的 LIS 长啥样，假设这个 LIS 为 \([a_{x_1},a_{x_2},\dots,a_{x_l}]\)，因为它不合法，所以不存在与它没有交集的 LDS，也就是所有 LDS 都与它有交集。

而根据之前的性质一个 LIS 和 LDS 至多只有 \(1\) 个公共元素，故 \(f_{x_1}+f_{x_2}+\dots+f_{x_l}=sum\)。

那么怎样找这样一个 LIS 呢？

先用树状数组求出 LIS、LDS 的长度，以及上文提到的 \(f_i,sum\) 的值。

求 LIS 的时候结构体里另外维护四个值 \(m_1,m_2,p_1,p_2\)，表示在满足上升子序列的长度最大的情况下，两个不同的 \(f_{x_1}+f_{x_2}+\dots+f_{x_l}\) 的值，以及它们对应的前驱。

如果发现存在一个 LIS 它的 \(f_{x_1}+f_{x_2}+\dots+f_{x_l} \neq sum\)，那么直接跳出输出就可以了。

/*

Contest: -

Problem: Codeforces Gym 101821 B

Author: tzc_wk

Time: 2020.10.4

*/

#include <bits/stdc++.h>

using namespace std;

#define fi			first

#define se			second

#define pb			push_back

#define fz(i,a,b)	for(int i=a;i<=b;i++)

#define fd(i,a,b)	for(int i=a;i>=b;i--)

#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)

#define all(a)		a.begin(),a.end()

#define fill0(a)	memset(a,0,sizeof(a))

#define fill1(a)	memset(a,-1,sizeof(a))

#define fillbig(a)	memset(a,0x3f,sizeof(a))

#define y1			y1010101010101

#define y0			y0101010101010

typedef pair<int,int> pii;

typedef long long ll;

inline int read(){

	int x=0,neg=1;char c=getchar();

	while(!isdigit(c)){

		if(c=='-') neg=-1;

		c=getchar();

	}

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x*neg;

}

const int MOD=23895631;

inline void add(int &x,int v){

	x+=v;if(x>=MOD) x-=MOD;

}

struct numway{

	int val,way;

	numway(int _val=0,int _way=0){val=_val;way=_way;}

	numway operator +(numway x){

		numway z=*this;

		if(x.val>z.val) z.val=x.val,z.way=0;

		if(x.val==z.val) z.way=(z.way+x.way)%MOD;

		return z;

	}

};

int n=read(),a[500005];

struct bit1{

	numway tr[500005];

	inline void clear(){

		for(int i=1;i<=n;i++)

			tr[i].val=tr[i].way=0;

	}

	inline void modify(int x,numway y){

		for(int i=x;i<=n;i+=(i&(-i)))

			tr[i]=tr[i]+y;

	}

	inline numway query(int x){

		numway ans(0,1);

		for(int i=x;i;i-=(i&(-i)))

			ans=ans+tr[i];

		return ans;

	}

} b1;

struct bit2{

	int tr[500005];

	inline void clear(){

		fill0(tr);

	}

	inline void modify(int x,int y){

		for(int i=x;i<=n;i+=(i&(-i)))

			tr[i]=max(tr[i],y);

	}

	inline int query(int x){

		int ans=0;

		for(int i=x;i;i-=(i&(-i)))

			ans=max(ans,tr[i]);

		return ans;

	}

} b2;

int lds_len=0,lis_len=0;

numway lds1[500005],lds2[500005];

int f[500005];

struct event{

	int val,m1,m2,p1,p2;

	event(int _val=0,int _m1=-1,int _m2=-1,int _p1=0,int _p2=0){

		val=_val;m1=_m1;m2=_m2;p1=_p1;p2=_p2;

	}

	friend event operator +(event a,event b){

		if(a.val>b.val) return a;

		if(a.val<b.val) return b;

		if(a.m1==-1) return b;

		else if(a.m2==-1){

			if(b.m1==-1||b.m1==a.m1) a.m2=b.m2,a.p2=b.p2;

			else a.m2=b.m1,a.p2=b.p1;

			return a;

		}

		else return a;

	}

};

struct bit3{

	event tr[500005];

	inline void modify(int x,event v){

		for(int i=x;i<=n;i+=(i&(-i)))

			tr[i]=tr[i]+v;

	}

	inline event query(int x){

		event ans(0,0,-1,0,0);

		for(int i=x;i;i-=(i&(-i)))

			ans=ans+tr[i];

		return ans;

	}

} b3;

event lis[500005];

vector<int> ans_lis,ans_lds;

bool cant[500005];

struct bit4{

	pii tr[500005];

	inline void modify(int x,pii v){

		for(int i=x;i<=n;i+=(i&(-i)))

			tr[i]=max(tr[i],v);

	}

	inline pii query(int x){

		pii ans=make_pair(0,0);

		for(int i=x;i;i-=(i&(-i)))

			ans=max(ans,tr[i]);

		return ans;

	}

} b4;

pii lls[500005];

inline void dump(int x,int y){

	while(x){

		ans_lis.pb(x);cant[x]=1;

		if(lis[x].m1==y){y=(y-f[x]+MOD)%MOD;x=lis[x].p1;}

		else{y=(y-f[x]+MOD)%MOD;x=lis[x].p2;}

	}

	reverse(all(ans_lis));

	printf("%d\n",lis_len);

	foreach(it,ans_lis) printf("%d ",*it);printf("\n");

	for(int i=n;i>=1;i--){

		if(cant[i]) continue;

		lls[i]=b4.query(a[i]-1);

		lls[i].fi++;

		b4.modify(a[i],make_pair(lls[i].fi,i));

	}

	for(int i=1;i<=n;i++){

		if(lls[i].fi==lds_len){

			for(int j=i;j;j=lls[j].se){

				ans_lds.pb(j);

			}

			break;

		}

	}

	printf("%d\n",lds_len);

	foreach(it,ans_lds) printf("%d ",*it);printf("\n");

}

int main(){

	for(int i=1;i<=n;i++) a[i]=read();

	b1.clear();

	for(int i=1;i<=n;i++){

		lds1[i]=b1.query(n-a[i]);lds1[i].val++;

		b1.modify(n-a[i]+1,lds1[i]);lds_len=max(lds1[i].val,lds_len);

	}

	b1.clear();

	for(int i=n;i>=1;i--){

		lds2[i]=b1.query(a[i]-1);lds2[i].val++;

		b1.modify(a[i],lds2[i]);

	}

//	for(int i=1;i<=n;i++) printf("%d %d %d %d\n",lds1[i].val,lds1[i].way,lds2[i].val,lds2[i].way);

	for(int i=1;i<=n;i++){

		if(lds1[i].val+lds2[i].val-1==lds_len){

			f[i]=1ll*lds1[i].way*lds2[i].way%MOD;

		}

//		cout<<f[i]<<endl;

	}

	int sum=0;

	for(int i=1;i<=n;i++){

		if(lds1[i].val==lds_len)

			sum=(sum+lds1[i].way)%MOD;

	}

//	cout<<sum<<endl;

	for(int i=1;i<=n;i++){

		int x=b2.query(a[i]-1);

		b2.modify(a[i],x+1);

		lis_len=max(lis_len,x+1);

	}

	for(int i=1;i<=n;i++){

		lis[i]=b3.query(a[i]-1);

		lis[i].val++;

		if(lis[i].m1!=-1){

			lis[i].m1=(lis[i].m1+f[i])%MOD;

		}

		if(lis[i].m2!=-1){

			lis[i].m2=(lis[i].m2+f[i])%MOD;

		}

//		printf("%d %d %d %d %d\n",lis[i].val,lis[i].m1,lis[i].m2,lis[i].p1,lis[i].p2);

		if(lis[i].val==lis_len){

			if(lis[i].m1!=-1&&lis[i].m1!=sum){

				dump(i,lis[i].m1);return 0;

			}

			if(lis[i].m2!=-1&&lis[i].m2!=sum){

				dump(i,lis[i].m2);return 0;

			}

		}

		b3.modify(a[i],event(lis[i].val,lis[i].m1,lis[i].m2,(lis[i].m1!=-1)?(i):(0),(lis[i].m2!=-1)?(i):(0)));

	}

	printf("IMPOSSIBLE\n");

	return 0;

}

巴特西

【2020五校联考NOIP #3】序列

最新文章

热门文章