零散思绪

CF2156B:

​如何压缩每一轮的运算？O(n)->O(1):

记运算ABBABA…为C

考虑组合运算的逆运算：$C^{-1}:$ x–>kx+b

则：C：x–> $\lfloor \frac{(x-b)}{k} \rfloor$

具体证明：考虑A,B的运算的单调性可逆性，和组合起来的单调性可逆性

实则完全没有必要：n<20

CF2149E:

three-pointer:p2,p3对应最近最远的不同值个数为m的区间

$1< a_i<10^9 $ : int cnt[(int)1e9+7]+memset()=TLE+MLE

memset为O(n)，使用需谨慎，且最好放前面

解决方法：

• 离散化：将ai映射到$[1,n]$上，序关系不变，对每一个区间而言，其不等元素数不变，故映射后答案不变。此时int cnt[(int)2e5+7]+memset()在时间空间上都是可行的
• 使用map<int,int>：空间优化，时间多个log，不过可过数据

BUAA-E6-I:

上题的改版

需注意若不离散化+memset，在空间上可行的但在时间上是不可行的

只需将序列中的值对应的cnt清零即可，时间上得到优化可过

注意到单调性+可反向验证=>构造check,用二分找到答案所在的美丽值