A.小y的序列

对于每种颜色，只要找到出现的最靠右的位置和最靠左的位置输出即可。如果找不到，那就藏在下一种颜色下面。

其实可以做到数据范围受限于

B.小y的线段

画出图来，可以发现具有单调性，只要计算出有多少个位置回到了源点就行了。

C.小y的质数

首先换个姿势看这个问题

求有多少个满足，并且

众所周知，与等价。

所以问题转化为求区间内有多少满足

因为区间比较大。所以可以对分解质因子。

然后容斥一下公因数，假设当前枚举到的质因子个数为。那就暴力搜索出来所有可能的公因数。然后计算内为当前公因数倍数的数字个数。然后容斥就行了。

D.小y的盒子

此题为送温暖题目。。

把所有的数字转换为三进制，对于每个卡片都是形如的形式

所以为的形式，共有位

然后考虑当第位上为的时候，表示这一位上需要选个的卡片，同样，为时需要个，为时只需一个。

当需要个时，有两种选择，其他的都只有一种选择。

又因为的形式是

我们从枚举到，只需考虑哪些位置上面是2即可。

如果当前有个位置为那么共有种情况，且贡献为，然后其他位置可以为，也可以为.所以贡献为。所以当前的贡献就是

所以最终答案为

将提出来。那就是。

用二项式定理合并那个，其实就是，所以最终答案为.

注意到当时是不符合题目要求的，所以要减去他的贡献.

所以真正的最后答案是

E.小y的工资

首先树形一下,用表示以为根的子树最大收益是多少。

询问的简单路径中，有些边是必须跑的，所以j把这些边从里面单独拿出来。然后再强制加回去就行了。

F.小y的纸牌

题目大意：

给出一个序列，分成两个子序列(长度可以不相同，位置可以不连续)，使得两个序列各个位置的前缀最大值的和最小。

一道非常巧妙的dp + 非常套路的分块题

首先考虑的dp怎么做

可以发现两个性质：
设原数组为
性质：假设分成的两个序列为,。若其中某个位置时，a中的最大值比b小，那么以后肯定一直都是a中的最大值比b小。因为要使a中的最大值比b大，那么只能是有一个且s被分到了a数组中。显然，s分到b数组中会更优秀

性质:假设a数组中的最大值一直比b小，那么所有分到b数组中的数字的贡献是原序列中该数字前面所有数字的最大值。因为b中的最大值一直比a大，所以这个很显然。

根据上面的两个性质，我们就可以设出状态。设表示第i个数字分到了a数组且作为a数组中的最大值最终的贡献。

那么对于原序列S中第i个元素我们可以分成以下两种情况，

1.将该元素放到b数组中。

显然，只有当比a数组中的最大值大时，我们才可能会选择这种情况。所以我们对于每个将

2.将放到a数组中。

如果放到a数组中且a数组中的最大值不变，即,那么将即可

如果放到a数组中a数组中的最大值变为，这时，只要找到前面最小的一个来更新即可

考虑得到了这个的dp之后怎么优化，可以直接对着代码考虑

现在相当于一道数据结构题，需要支持：

1. 查询满足的的最小值
2. 让的
3. 让的

这是一个经典的分块维护凸包的模型，对于每个转移点，我们可以将其看做的形式，是常量，是被执行过操作的次数

接下来可以将每个按照分块，因为，所以只要分为块即可

对于每一块，可以通过打标记来维护操作(相同块内加的值是相同的)。同时我们可以将块内的每个转移点看做一个函数(也就是)，其中自变量每次只会，现在我们只需要知道对于每个，这些函数对应的最小值。

也就是说我们只需要维护出红色的线段

这又是个经典模型，，而且考虑到该题比较好的性质，对于每一块只需要从前往后扫一遍，判断一下相邻点的位置关系即可。

查询的时候由于单增，只需要判断第一个元素和第二个元素的关系，如果不满足弹出队首即可

复杂度

代码

A: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40569856
B: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40569861
C: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40569871
D: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40569872
E: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40569877
F: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40570772