考虑对于一组询问的合法的解， \(\tt (a,b,c)\)， 如果有 \(\tt a\le i\le b\) 使得 \(\tt A_i \ge min(A_a,A_b)\)， 那么把 \(\tt a、b\) 中那个 \(\tt A\) 值较小的换成 \(\tt i\)， 答案不会变劣， 所以只需考虑满足它们之间的数都严格小于 \(\tt min(A_a,A_b)\) 的 \(\tt a,b\) 。这样的 \(\tt a,b\) 只有 \(\tt O(n)\) 组， 这是因为它们必然分别是它们之间的最大的数的 “左边第一个比这个数大的数” 和 “右边第一个比这个数大的数”。(相邻的 \(\tt (a,b)\) 也要考虑)
不会了， 看题解了。
首先预处理出所有这样的 \(\tt (a,b)\)， 然后考虑把询问离线， 按照左端点从大到小的顺序排序， 逐个处理， 这样可以使得决策集合单调不减。 考虑对于每个新加入的 \(\tt (a,b)\)， 把所有满足题目条件的 \(\tt c\) 都维护一个 \(\tt B\) 值， 为最大的 \(\tt A_a+A_b\)， 再用线段树维护下整个序列的 \(\tt max(B_i+A_i)\) 就做完了。
从粉兔那学了不少代码经验啊ovo， 以前维护复杂线段树信息好像也是从他那学的。
甚至还学到了一次单调栈预处理序列里某个数左右最近的更大值
这种题就是算出 \(\tt [1,R]\) 和 \(\tt [1,L-1]\) 的答案， 相减。
考虑计算 \(\tt [1,N]\) 的答案， 考虑枚举前 \(\tt i\) 位都和 \(\tt N\) 的前 \(\tt i\) 位都相等且第 \(\tt [i+1,k]\) 位和 \(\tt N\) 的第 \(\tt [i+1,k]\) 位都不相等的答案， 具体来说， 从大到小枚举从小到大的第 \(\tt i\) 位填什么， 若小于 \(\tt N\) 的这一位， 则后面的数可以随便填， 把方案累加到答案里； 否则， 令这一位等于 \(\tt N\) 的这一位， \(\tt i=i-1\) ， 继续这一过程。
考虑如何累加答案，发现很难统计， 因为最终的数位和不确定。
由于数位和的范围很小， 考虑在外层枚举数位和，假设枚举到的数位和为 \(\tt sum\)。
考虑在枚举第 \(\tt i\) 位的时候维护最高位到第 \(\tt i\) 位的数位和 \(\tt t\) 和当前数值对 \(\tt sum\) 取模的结果 \(\tt q\)。（当前数值是指后面补 \(\tt 0\) 后的数值）。
设第 \(\tt i\) 位当前从小到大枚举到数字 \(\tt p\)，
考虑情况一的答案怎么统计， 这个答案一共有这么几个限制： “膜一个数的余数”、“数位和”、“位数”。
其实这就可以上数位 DP 了，
设 \(\tt F[i,j,k,l]\) 表示由 \(\tt i\) 位数字组成、数位和为 \(\tt j\)、对 \(\tt k\) 取模余数为 \(\tt l\) 的数有多少个。（允许前导零）
状态转移方程比较好想：
那么情况一要加到总答案里的就是： \(\tt F[i-1,sum-t-p,sum,(sum-q-p*10^{i-1})\mod sum]\)
话说数位 DP 其实还有其它实现， 这题的加强版是 [AHOI2009]同类分布 ，用这种方法过不了qwq， 建议学一下更优的写法。
原文：https://www.cnblogs.com/tztqwq/p/13697148.html