1638

首先介绍尺取（双指针） 用于求解满足条件的最小区间问题 首先，从数组最左边元素开始，向右延伸r，使得最初满足条件。此时对于l为1来说，是最小的满足条件区间 接下来，开始将l变为2。变为2后，需要将r延长到能够满足条件的下一个r（可能不用延长，也可以先延长再把l变成2）。这样就得到了l为2时的最小区间 ......

题意 给定一个长度为 \(n\) 的数组，初始每个数的颜色为 \(1\)，值为 \(0\)。 维护以下操作： 将 \(l \to r\) 的颜色替换成 \(c\)。 将数组中颜色为 \(c\) 的元素的值加上 \(x\)。 输出 \(a_i\) 的值。 \(n, q \le 10 ^ 6\) Sol ......

浅浅证明一下这种做法的正确性。 首先，答案一定是一个最优解，那么枚举右端点到b的时候，由于最优解是合法解，我们的左端点会走到不能走了为止，这样就求出了最优解，而且最优解一定是最小的，所以一定会记入答案。 其实可以理解为把区间按照右端点分类了，而且每类区间中的最优解的左端点是递增的（和右端点正相关）， ......

考虑这样一种贪心策略： 按序号遍历 $a$，如果 $a_i=i$ 则继续，否则暴力向下找到一个 $a_j=i$，暴力翻转区间 $[i,j]$，然后退出。 正确性证明： 当遍历到 $a_i$ 时，$a_1$ 到 $a_{i-1}$ 一定已经是不需要翻转就已经字典序最小，因为如果不是的话程序在这之前就已 ......

蒟蒻有一种用 set 的乱搞（？）做法。 将题目中的连边要求反着说一遍：$i>j$ 且 $a_i<a_j$。 考虑遍历 $a$ 时，遍历到的 $a_i$ 编号一定要比它前面的大，只需要将前面比它大的元素都和它连起来。 将每个连通块看作一个整体，只要 $a_i$ 比其中任意一个小，$a_i$ 就可以加 ......

考虑这样一种贪心策略： 按序号遍历 $a$，如果 $a_i=i$ 则继续，否则暴力向下找到一个 $a_j=i$，暴力翻转区间 $[i,j]$，然后退出。 正确性证明： 当遍历到 $a_i$ 时，$a_1$ 到 $a_{i-1}$ 一定已经是不需要翻转就已经字典序最小，因为如果不是的话程序在这之前就已 ......

蒟蒻有一种用 set 的乱搞（？）做法。 将题目中的连边要求反着说一遍：$i>j$ 且 $a_i<a_j$。 考虑遍历 $a$ 时，遍历到的 $a_i$ 编号一定要比它前面的大，只需要将前面比它大的元素都和它连起来。 将每个连通块看作一个整体，只要 $a_i$ 比其中任意一个小，$a_i$ 就可以加 ......

有高度分别为1到n的n根杆子排成一行。如果你从左侧或右侧看这些杆，较小的杆被较高的杆遮挡。 给出杆子的数量n，从左能看到的杆子数量L，从右能看到的杆子数量R，求杆子有多少种排列方式 考虑高度1~n的柱子， 把高度1的插入 2~i 的某个排列中转移 f[i ][j] [k ]=f[i-1][j-1][ ......

LeetCode | 1638.统计只差一个字符的子串数目 给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。 比方说， "computer" and  ......