【题解】牛客IOI周赛16-提高组

像鱼

60分做法：

发现三角形想要倒过来，中间一部分可以不动，例如红色和蓝色 以每一行为中心最多能保留不动的就是这一行到最底行取min的两个没有尖倒三角减去中间一行

我们枚举每行取min就可以拿到六十分了

100分做法

通过六十分做法我们发现，当每一行确定时它能保留的硬币数也是一定的，所以我们设保留从底往上数第i行不动，列一个方程，最后消项，发现是个一元二次方程，那答案就可以用最值公式解出。

复杂度

小L扔垃圾

30分：

每次修改后对整个新字符串处理，可以枚举所有区间看是否满足条件，更新答案，时间复杂度。

60分：

每次修改后对整个新字符串处理，设两种垃圾分别为1和-1，可回收垃圾为0，进行前缀和，发现前缀和数组中两位置数相等时，两位置区间满足条件，可记录每一种数的第一次出现位置，不断更新答案即可，时间复杂度。

100分：

根据60分解法的前缀和特性，发现只要用一个桶维护每一种数的第一次出现位置和最后一次出现位置即可，在最后插入新数容易维护，但在前面插入新数会改变全前缀和数组，但我们发现每个数字不重要，只需要最前和最后出现位置，所以用一个标识记录当前桶中谁是0，前端插入1或-1时标识前后移动即可，时间复杂度。

最小鸽

30分

枚举区间数据结构大力爆算就可以了

60分

我们发现枚举完区间就不能带了，考虑用表判断这个区间是否满足要求

我们发现维护答案也需要一点技巧，对于一个符合要求的区间，我们在处打一个，在处打一个

然后开一个桶，从左到右扫整个序列，对于每个位置先把标记加入桶对应位置，然后再桶内找出现过的最小的数字

判断区间，后续每个符合要求的区间只会被加入一次删除一次，每个位置只会遍历一次桶，桶的上限是，总复杂度

100分

显然区间或不小于区间最大值，那么对于某个最大值存在的区间，在这段范围答案满足二分性质

先对于每个位置找出右边第一个大于它的数字

对于某个位置，二分向右找到最近满足条件的区间右端点，然后利用线段树对右边所有位置更新答案

对于，赋值,对于中个每个，赋值

线段树维护一个最小值，需要进行的操作是区间赋值和区间等差数列赋值

其实区间等差数列赋值在维护最值问题的时候是很好实现的

C题被各种奇奇怪怪的暴力跑过去了，十分抱歉