写些不知道写在哪的东西。
看了一下THUSC2023Day1T1。
有一个长度为 \(n\) 的序列，\(q\) 次操作，形如区间加和询问区间内至少几次区间 ±1 使得区间内所有数等于 \(x\)
结论是把区间两边接上 \(x\)，答案是差分序列的绝对值之和除以 \(2\)
是这样的，考虑区间加在差分序列上的改变，即为一个数 \(+1\)，一个数 \(-1\)，显然要把 \(<0\) 的 \(+1\)，\(>0\) 的 \(-1\)。这样一定可以构造出一种方案。
启示我们区间加减操作在差分序列上考虑问题。
还有PKUSC2023Day1T1
给两个长度为 \(n\) 的字符串 \(S,T\)，对于 \(1\leq i\leq n\)，询问将 \(S_i\) 替换为 \(T_i\) 后 \(S\) 的 border 长度。\(n\leq 2\times 10^6\)
首先是 border 不受修改影响的情况，容易解决。
考虑一对前后缀 \(S[1...i]\) 和 \(S[n-i+1...n]\)，若其有 \(\geq 2\) 个不同的位置，就肯定不行。否则设不同的位置在原串中对应的位置分别为 \(i\) 和 \(j\)。将 \(S_i\) 改为 \(S_j\) and vice versa。
怎么找这种位置呢？\(O(n\log n)\) 的二分+hash 是容易的，怎么 \(O(n)\) 呢？
这启示了我们什么呢？
重庆我来啦！
标签：2024.1,16,差分,leq,序列,...,区间,border From： https://www.cnblogs.com/Assemblyline/p/17968523