【8.8】代码源 - 【不降子数组游戏】【最长上升子序列计数（Bonus）】【子串（数据加强版）】

#886. 不降子数组游戏

题意：

题解：(分块/三分) 代码源每日一题Div1 不降子数组游戏

思路：首先，先手选了一个点，后手必定要选 $L,R$ 其中的一个，这样才能使分数最大。那么把我们选择的点的下标作为自变量，分数作为因变量，这个函数是一个下凸函数（不会证），三分出极值点即可。

问题转化为，给定区间 $[l,r]$ 问这个区间的分数。我们对原序列进行分块，划分为若干非降子区间。子区间内部一个长度为 $len$ 的子区间的分数是 $\frac{len(len+1)}{2}$ ，那么我们对块预处理前缀和，以及预处理每个元素所在块的编号，以及左边界右边界。我们询问一个区间 $[l,r]$ ，分数就是区间内的整块的区间分数和加上两个残块的分数。

AC代码：http://oj.daimayuan.top/submission/326684

---

#884. 最长上升子序列计数（Bonus）

题意：求最长上升子序列的个数。区间长度 $n(1\le n\le 4\cdot 10^5)$ 。

题解：(DP/线段树/树状数组)最长上升子序列计数（Bonus）

思路：可以权值线段树或树状数组。我用的树状数组。

定义 $len(i)$ 表示以 $a_i$ 结尾的 LIS 长度，$cnt(i)$ 表示对应的 LIS 方案。转移： $len(i)=1+{\max }_{j<i,a_j<a_i}len(j),cnt(i)={\sum }_{j<i,len(j)+1=len(i)}cnt(j)$

对于 $a_i$ ，我们要找到 $a_j(j<i,a_j<a_i)$ 的信息，这个信息可以按照值域为下标存到树状数组，然后查询前缀信息。那么我们就需要查询值域前缀的最大值，以及最大值的对应计数。这个需要树状数组维护二元组。

树状数组维护前缀最大值以及前缀最大值的计数：

struct trie{
	int n;
	int tr[N], tr2[N]; // tr 是前缀最大值, tr2 是前缀最大值的计数
	void init(int n){
		this -> n = n;
		rep(i, 0, n) tr[i] = tr2[i] = 0;
	}
	void add(int x, int k, int c){
		for(int i = x; i <= n; i += i & -i){
            if(tr[i] < k) tr[i] = k, tr2[i] = c;
            else if(tr[i] == k) tr2[i] = (tr2[i] + c) % p;
        }
	}
	PII query(int x){
		PII res = {0, 0};
		for(int i = x; i ; i -= i & -i){
            if(res.fi < tr[i]) res.fi = tr[i], res.se = tr2[i];
            else if(res.fi == tr[i]) res.se = (res.se + tr2[i]) % p;
        }
		return res;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

AC代码：http://oj.daimayuan.top/submission/326785

---

#922. 子串（数据加强版）

题意：给定一个长度为 $n(1\le n\le 2500)$ 的 $01$ 串，问有多少种划分，使得每一个划分出来的子串的 $1$ 的个数组成的序列是回文的，答案对 $998244353$ 取模。

题解：(插板法)代码源每日一题 Div1 子串（数据加强版）

思路：原题的数据可以用区间 DP 来做。用双指针优化，左指针从左到右枚举划分点，右指针滑动到对应点，然后统计。

题解则是用组合计数。

AC代码：边界不好搞，没有AC。