[8.8] Code Source - [Non-falling subarray game] [Longest rising subsequence count (Bonus)] [Substring (data enhanced version)]

#886. Do not drop subarray games

题意：

题解：(分块/三分) 代码源每日一题Div1 Do not drop subarray games

思路：首先,Pick a point first,The back must be chosen $L,R$ 其中的一个,This will maximize the score.Then take the subscript of the point we choose as the independent variable,Score as the dependent variable,This function is a downward convex function（不会证）,Three points out the extreme point.

问题转化为,给定区间 $[l,r]$ Ask for the fraction of this interval.We block the original sequence,Divide into several non-decreasing subintervals.A length inside the subinterval is $len$ The fraction of the subinterval is $\frac{len(len+1)}{2}$ ,Then we preprocess the prefix sum on the block,and the number of the block where each element is preprocessed,and left border and right border.We ask for an interval $[l,r]$ ,The score is the interval score of the whole block in the interval plus the score of the two residual blocks.

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

#884. Longest ascending subsequence count（Bonus）

题意：Find the number of longest ascending subsequences.区间长度 $n(1\le n\le 4\cdot 10^5)$ .

题解：(DP/线段树/树状数组)Longest ascending subsequence count（Bonus）

思路：Can be a tree of weights segments or a tree-like array.The tree array I use.

定义 $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)$ 的信息,This information can be stored in a tree-like array indexed by the range,Then query prefix information.Then we need to query the maximum value of the range prefix,and the corresponding count for the maximum value.This requires a tree-like array to maintain two-tuples.

The tree-like array maintains the prefix maximum value and the count of the prefix maximum value：

struct trie{
    
	int n;
	int tr[N], tr2[N]; // tr is the prefix maximum value, tr2 is the count of prefix maximum values
	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;
	}
};

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

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

题意：给定一个长度为 $n(1\le n\le 2500)$ 的 $01$ 串,Ask how many divisions there are,Makes each of the divided substrings $1$ The sequence of numbers is palindromic,答案对 $998244353$ 取模.

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

思路：The data of the original title can use the interval DP 来做.Optimize with double pointers,The left pointer enumerates the division points from left to right,Slide the right pointer to the corresponding point,然后统计.

The solution is to use combination counting.

AC代码：borders are bad,没有AC.