4099 FTT

题面

内容

有 $n$ 只青蛙排成一排青蛙序列在开会，其中第 $i$ 只青蛙的叫声大小是 $a_i$。

对于任意两只青蛙 $i,j$，如果 $i\neq j$，则 $a_i\neq a_j$。

现在要从青蛙中选出一支青蛙集训队，集训队的成员编号为 $0$，$1$，$...$，$k$。

集训队要求：

1. 对于第 $i$ 名集训队成员和第 $j$ 名集训队成员，假设 $i<j$，那一定需要满足第 $i$ 名集训队成员在青蛙序列中的位置比第 $j$ 名集训队在青蛙序列中的位置更靠前。

2. 对于第 $i$ 名集训队成员和第 $j$ 名集训队成员，假设 $i<j$，那一定需要满足第 $i$ 名集训队成员的叫声比第 $j$ 名集训队的叫声更小。

你需要求出有多少种选出青蛙集训队的方案。

答案对 $998244353$ 取模。

输入

第一行输入两个数 $n,k$。

接下来输入 $n$ 行，每行一个数，其中第 $i$ 行输入 $a_i$，表示第 $i$ 只青蛙的叫声。

输出

输出一个数，答案对 $998244353$ 取模后的结果。

样例

输入

5 2
1
2
3
5
4

输出

7

提示

样例解释

我们用青蛙序列的下标位置来表示每一名青蛙集训队成员，用集合来表示青蛙集训队，则合法的青蛙集训队有：

{1,2,3}，{1,2,4}，{1,2,5}，{1,3,4}，{1,3,5}，{2,3,4}，{2,3,5}。

数据范围

对于 $20\%$ 的数据，$1\le n\le 100$，$0\le k\le 10$。

对于 $60\%$ 的数据，$1\le n\le 1000$，$0\le k\le 10$。

对于 $100\%$ 的数据，$1\le n\le 10^5$，$0\le k\le 10$ ， $1\le a_i\le n$。

思路

求长度为$k+1$的最长上升子序列的方案数。

$f_i$代表以$i$为结尾的最长上升子序列，

$i$的值可以由$j$的状态转移过来。

那么我们可以令$f_{i,j}$表示以$i$结尾长度为$j$的最长上升子序列的方案数。

那么如果一个$y$的位置长度为$j$可以被更新，那么它的上一个位置$x$长度为$j-1$可以更新它，也就是累加上$x$的答案。

因此要更新需要满足的条件是$a[y]>a[x]$，更新给$f_x$ 的值就是所有满足这个条件的$y$的和。

即图中所有的$x$的$f$值都需要累加。

那么我们可以开一个二元组来维护这个关系，

$(a_i,f_i)$

这样其实就是在找$a_i$左边的所有的$f_j$的和。

怎么保证$j<i$？

是从前往后插入的。

用树状数组优化区间求和问题。

由于$k=11$，因此需要开$11$个树状数组来维护这个问题。

每次更新第$j$层时，需要访问第$j-1$层树状数组。

$i$表示最后一个选择的区间的右端点，

$f_i$表示最多能选的区间，优先选短的区间，

对i而言，找到一个最大的j使得区间和为0，即右端点和左端点左边的前缀和相同

记录一个last为上次和i前置和相同的点的位置，

i一定从j-1转移过来么？

不一定，因为上一段不一定以j-1结尾

那就把j之前的区间的f值取个max来更新$f_i$

$f_i=max(f_j)+1$

那么q次询问就需要通过数据结构来优化复杂度

以每个i结尾的区间最多只有一个有意义，即最小的，

那么总共就有n个区间有意义，将它预处理出来，然后建树

以i结尾的区间for一遍就可以通过last维护最小的这个区间

选完一个区间后就可以选右端点最小的区间

所以说选完以后选下一个区间是一个固定的过程

预处理

这样出来以后就是一棵树

第一个的是左端点大于l右端点最小的区间

然后一直走直到超出r

倍增求解就可以了。