BZOJ4881: [Lydsy1705月赛]线段游戏（二分图）

4881: [Lydsy1705月赛]线段游戏

Time Limit: 3 Sec Memory Limit: 256 MBSubmit: 359 Solved: 205[Submit][Status][Discuss]

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

8

HINT

Source

claris原创，本oj版权所有,翻版必究

题意：即是有多少种方案，把一个序列划分为两个上升子序列。

思路：既然是上升的，我们可以用dp[x][y]，保存两个子序列的最后一位，即两个子序列的最大值。 这样DP的话显然不可能操作。

我们先考虑不合法的情况，如果最长下降子序列LDS>2，那么一定无解，因为x和y都只能连接比自己大的，如果连续下降三次，那么x和y都无法接纳第三个。 所以先判无解，如果一个数前面有比它大的，后面有比它小的，说明LDS>=3，无解。

假设我们把逆序关系连边，那么这个图是个二分图，有解的情况下，一个点要么有入度，要么有出度，一个连通块有两种染色方案，答案就是2^连通块数。

我们用set来维护每个连通块的最大值。 每次新加入一个数X，那么set里面大于X的数都与X连接一条边，所以这些在一个连通块里，删去，且留下最大值。

#include

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

using namespace std;

const int maxn=200010;

const int Mod=998244353;

int a[maxn],pre[maxn],lat[maxn];

sets; set::iterator it;

int qpow(int a,int x){

int res=1; while(x){

if(x&1) res=1ll*res*a%Mod;

a=1ll*a*a%Mod; x>>=1;

} return res;

}

int main()

{

int N; scanf("%d",&N);

rep(i,1,N) scanf("%d",&a[i]);

int Mx=0;

rep(i,1,N){

if(Mx>a[i]) pre[i]=1;

Mx=max(Mx,a[i]);

}

int Mn=N+1;

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

if(Mn

Mn=min(Mn,a[i]);

}

rep(i,1,N) if(pre[i]&&lat[i]) return puts("0"),0;

rep(i,1,N){

int mx=a[i];

while(!s.empty()){

it=s.end(); it--;

if(*it>a[i]) mx=max(mx,*it),s.erase(it);

else break;

}

s.insert(mx);

}

int ans=qpow(2,s.size());

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

return 0;

}