BZOJ 4881: [Lydsy2017年5月月赛]线段游戏

4881: [Lydsy2017年5月月赛]线段游戏

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

Sourc

想法：

两人取的线段都互不相交，这意味着如果把线段当成点，相交线段连边。那么这张图一定是若干个二分图组成的，否则无解。

于是变成了求连通图个数，用并查集维护一下。如何判掉不是二分图，如果出现三个递减的数，那就不是二分图了。比如3 2 1.

然后细节.....粗心WA了三发。

#include<cstdio>

typedef long long ll;

const int len(),MP(),INF(0x7fffffff);

int f[len+];

int suc[len+],suc_m[len+],ans,n,p[len+],much[len+];

void umin(int &a,int b){if(a>b)a=b;}

void umax(int &a,int b){if(a<b)a=b;}

void put(int x){for(int y=x;y;y-=y&(-y))umin(suc[y],x);}

int query(int x){int sum=INF;for(;x<=n;x+=x&(-x))umin(sum,suc[x]);return sum;}

void put_m(int x){for(int y=x;y;y-=y&(-y))umax(suc_m[y],much[x]);}

int query_m(int x){int sum=;for(;x<=n;x+=x&(-x))umax(sum,suc_m[x]);return sum;}

int power(int a,int b)

{

    ll t=,y=a;

    for(;b;b>>=)

    {

        if(b&)t=t*y%MP;

        y=y*y%MP;

    }

    return t;

}

int gf(int x)

{

    int v=x;while(v!=f[v])v=f[v];

    for(int o;x!=v;x=o)o=f[x],f[x]=v;

    return v;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)suc[i]=INF,f[i]=i;

    for(int i=;i<=n;i++)scanf("%d",p+i);

    ans=n;

    for(int i=,last,now;i<=n;i++)

    {

        last=query(p[i]);     put(p[i]);

        much[p[i]]=+query_m(p[i]);

        put_m(p[i]);

        if(last==INF)continue;

        else

        {

            now=p[i];

            last=gf(last);

            while(last!=INF)

            {

                f[now]=last; ans--;

                now=last; if(now==n)break;

                last=query(last+);

            }

        }

    }

    ans=power(,ans);

    for(int i=;i<=n;i++)if(much[i]>=)ans=;

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

    return ;

}

秒客网