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

2022-10-29 12:45:52

4881: [Lydsy1705月赛]线段游戏

Time Limit: 3 Sec Memory Limit: 256 MB
Submit: 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

HINT

Source

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

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

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

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

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

#include<bits/stdc++.h>

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

using namespace std;

const int maxn=;

const int Mod=;

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

set<int>s; set<int>::iterator it;

int qpow(int a,int x){

    int res=; while(x){

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

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

    } return res;

}

int main()

{

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

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

    int Mx=;

    rep(i,,N){

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

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

    }

    int Mn=N+;

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

        if(Mn<a[i]) lat[i]=;

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

    }

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

    rep(i,,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(,s.size());

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

    return ;

}

码农公寓