BZOJ 4881: [Lydsy1705月赛]线段游戏 动态规划 + 线段树

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取模输出。

问题可以转化为：给定一个序列，求将这个序列分成两个上升子序列的方案数. 令 $f_{i,j}$ 表示一个序列选 $i$，令一个序列的最大值为 $p_{j}$ 的方案数 ($j

$f_{i,j}=f_{i-1,j},j

$f_{i,i-1}=\sum f_{i-1,k},p_{k}

$f_{i,j}$ 的转移只和 $f_{i-1,?}$ 的转移有关，所以可以将第一维滚掉. 而每一次 $f$ 的更新只有两种：区间清零，用一个区间和来更新单点的点值. 这些操作可以用线段树来实现.

#include

#include

#define N 100006

#define mod 998244353

#define setIO(s) freopen(s".in", "r" , stdin)

using namespace std;

int a[N], n ;

struct Node

{

int sum, lazy ;

}t[N << 2];

inline void mark(int now)

{

t[now].sum = 0, t[now].lazy = 1;

}

inline void pushdown(int l, int r, int now)

{

int mid = (l + r) >> 1;

if(t[now].lazy)

{

mark(now << 1);

if(r > mid) mark(now << 1 | 1);

t[now].lazy = 0;

}

}

inline void pushup(int l, int r, int now)

{

int mid = (l + r) >> 1;

t[now].sum = t[now << 1].sum ;

if(r > mid) t[now].sum += t[now << 1 | 1].sum, t[now].sum %= mod ;

}

inline void update(int l, int r, int now, int p, int v)

{

if(l == r)

{

t[now].sum += v, t[now].sum %= mod;

return ;

}

int mid = (l + r) >> 1;

pushdown(l, r, now);

if(p <= mid) update(l, mid, now << 1, p, v);

else update(mid + 1, r, now << 1 | 1, p, v);

pushup(l, r, now);

}

inline int query(int l, int r, int now, int L, int R)

{

if(l >= L && r <= R) return t[now].sum ;

pushdown(l, r, now);

int mid = (l + r) >> 1, re = 0;

if(L <= mid) re += query(l, mid, now << 1, L, R);

if(R > mid) re += query(mid + 1, r, now << 1 | 1, L, R);

return re % mod;

}

int main()

{

// setIO("input");

int i , j ;

scanf("%d", &n);

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

update(0, n, 1, 0, 1);

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

{

int sum = query(0, n , 1, 0, a[i] - 1);

if(a[i] < a[i - 1]) mark(1);

update(0, n, 1, a[i - 1], sum);

}

printf("%d\n", query(0, n, 1, 0, n) * 2 % mod);

return 0;

}