Educational Round 165
E. Unique Array
首先有一个贪心，对于一个区间 $[l, r]$ 我修改其中任何一个数，整个序列就会被这个数分成不包含这个数的左半部分和右半部分。所以，如果我从左向右考虑，找到了一个不unique的区间，那么我肯定是更改区间最右端的数。现在，我们只需要从左向右扫一遍，考虑从上一个更改过的下标一直到当前下标（左开右闭）有没有不满足unique的区间。
有一个经典trick，如果我想判断一个区间里的数是否存在unique的数，我只需要从左向右扫一遍，第一次遇到某个数时 cnt++，第二次遇到某个数时 cnt--，如果最后 cnt==0，那么就是不unique的。有点类似扫描线。
现在，我们维护每个数字最后出现的位置 $las_x$ 和倒数第二次出现的位置 $sec_x$ 。当我们遇到一个新的数 $x$ 时，我们把 $(las_x,i]$ 里的unique数字个数++，$(sec_x,i]$ 的unique数字个数–，使用线段树维护区间更新，区间最小值如果为0，就说明出现了一个不unique的区间，答案++。然后更新sec和las。
我因为先更新las和sec再update线段树WA了一发，因为一个数可能出现多次，这样会有问题。
Submission #301317965 - Codeforces
Luogu
P2846
线段树维护亮灯个数，lazytag维护区间的灯是否反转，反转操作使用区间长度减去亮灯个数，使用异或来做标记下推。
| [记录详情 - 洛谷 | 计算机科学教育新生态](https://www.luogu.com.cn/record/198716765) |
P4392
线段树维护区间最大最小值即可。如果使用ST表会爆空间，由于m是有限的，ST表的第二维可以只开 $log(m)$ ，这样就不会爆了。这题还可以使用单调队列啥的。
| [记录详情 - 洛谷 | 计算机科学教育新生态](https://www.luogu.com.cn/record/198732456) |
P1253
这题需要维护区间修改，区间加以及区间最大值。加和修改需要两个lazytag，当下推时，先下推修改的标记，再下推加的标记。修改时，将加的标记直接置零。
有一个小点是修改标记一开始不应该赋值为0而应该赋值为inf，表示没有修改，而不是修改成0。这题有负数，所以-1也不行。
| [记录详情 - 洛谷 | 计算机科学教育新生态](https://www.luogu.com.cn/record/198763010) |
牛客小白月赛109
C-猪猪养成计划1
由于每个猪猪只会被玩耍一次，我们只需把vis数组中表示vis过了的true换成右边第一个尚没有被玩耍过的下标即可。那么标记的过程将变成 $O(n)$ 的。
这题还有一种做法是使用set，我赛时没往这想。
D-猪猪养成计划2
由于最终一定会在第 $n+1$ 天结束一切活动，我们把天数看成点，给猪猪买礼物的价钱以及陪猪猪的精力啥的看成边权，那么这就变成了一道最短路问题。现在，我们的准备工作就是求出边权。
首先，如果当天没有猪猪想要被陪伴，那么连一条权值为 $0$ 的边指向下一天，这是必须的，之前cf上面的题就忘了这一点。
然后，我们总是可以花钱买礼物而不陪伴当天需要陪的小猪，同样连一条边指向下一天，此时的边权应该是所有当天需要陪的小猪的 $val$ 之和。注意：小猪需要陪的 $a_i$ 可能相同。
再然后，我们总是可以选择陪伴这只小猪，然后跳到 $m$ 天以后，此时的边权应当为这 $m$ 天里所有没有陪伴的小猪的 $val$ 之和。我们预先把小猪按照 $a_i$ 排序，然后对排序后的 $val$ 求前缀和。那么这个边权可以通过 lower_bound 二分出前缀和的左端点和右端点，然后算出。
最后，我们通过迪杰斯特拉算出最短路即可。从第 $1$ 天到达第 $n+1$ 天的最短距离就是我们的最终答案。