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<i$).
考虑转移：
- $f_{i,j}=f_{i-1,j},j<i-1$ 且 $p_{i-1}<p_{i}$
- $f_{i,i-1}=\sum f_{i-1,k},p_{k}<p_{i}$
$f_{i,j}$ 的转移只和 $f_{i-1,?}$ 的转移有关，所以可以将第一维滚掉.
而每一次 $f$ 的更新只有两种：区间清零，用一个区间和来更新单点的点值.
这些操作可以用线段树来实现.
#include <cstdio>
#include <algorithm>
#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;
}
