【BZOJ4881】5月月赛D 线段游戏树状数组+set

Description

quailty和tangjz正在玩一个关于线段的游戏。在平面上有n条线段，编号依次为1到n。其中第i条线段的两端点坐

标分别为(0,i)和(1,p_i)，其中p_1,p_2,...,p_n构成了1到n的一个排列。quailty先手，他可以选择一些互不相交

的线段，将它们拿走，当然他也可以一条线段也不选。然后tangjz必须拿走所有剩下的线段，若有两条线段相交，

那么他就输了，否则他就赢了。注意若quailty拿走了全部线段，那么tangjz也会胜利。quailty深深喜欢着tangjz

，所以他不希望tangjz输掉游戏，请计算他有多少种选择线段的方式，使得tangjz可以赢得游戏。

Input

第一行包含一个正整数n(1<=n<=100000)，表示线段的个数。

第二行包含n个正整数p_1,p_2,...,p_n(1<=p_i<=n)，含义如题面所述。

Output

输出一行一个整数，即tangjz胜利的方案数，因为答案很大，请对998244353取模输出。

Sample Input

5
1 2 4 5 3

Sample Output

题解：题意可理解为给定一个序列，求将这个序列分成两个上升序列的方案数

先判断是否输出0，方法是用树状数组求最长下降序列，若长度>2，说明无解

然后从左往右扫，将这些数一个一个加到set里，在加入之前，先将set中比当前数大的数全都删掉，然后将这些数中最大的数加到set中去，最后若set中还剩m个数，答案就是2^m

考试时除了G以外唯一想出来的题~

#include <cstdio>

#include <cstring>

#include <iostream>

#include <set>

using namespace std;

int n,ans,v[100010],tr[100010];

set<int> s;

void updata(int x,int val)

{

	for(int i=x;i<=n;i+=i&-i)	tr[i]=max(val,tr[i]);

}

int query(int x)

{

	int i=x,ret=0;

	for(i=x;i;i-=i&-i)	ret=max(ret,tr[i]);

	return ret;

}

int main()

{

	scanf("%d",&n);

	int i,a,b;

	set<int>::iterator it;

	for(i=1;i<=n;i++)	scanf("%d",&v[i]);

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

	{

		a=query(v[i]-1)+1;

		if(a>=3)

		{

			printf("0");

			return 0;

		}

		updata(v[i],a);

	}

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

	{

		b=v[i];

		while(!s.empty())

		{

			it=s.upper_bound(b);

			if(it==s.end())	break;

			b=*it,s.erase(b);

		}

		s.insert(b);

	}

	b=s.size(),ans=1;

	while(b--)	ans=(ans*2)%998244353;

	printf("%d",ans);

	return 0;

}

巴特西

【BZOJ4881】5月月赛D 线段游戏树状数组+set

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

【BZOJ4881】5月月赛D 线段游戏 树状数组+set

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

【BZOJ4881】5月月赛D 线段游戏树状数组+set