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

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

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

8

HINT

Sourc

想法：

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

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

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

#include

typedef long long ll;

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

int f[len+10];

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

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

void umax(int &a,int b){if(a

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=0;for(;x<=n;x+=x&(-x))umax(sum,suc_m[x]);return sum;}

int power(int a,int b)

{

ll t=1,y=a;

for(;b;b>>=1)

{

if(b&1)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=1;i<=n;i++)suc[i]=INF,f[i]=i;

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

ans=n;

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

{

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

much[p[i]]=1+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+1);

}

}

}

ans=power(2,ans);

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

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

return 0;

}