现在我随机@一个人 这个人必须帮我写题目概括
@gzn7264
这篇题解就不在洛谷博客上发布了。
首先枚举点对的右端点。显而易见，合法的左端点必须满足：
- 左端点与右端点颜色相同
- 左端点到右端点之间必须存在至少一个客栈，使得其费用小于等于 $P$
第二个条件有点麻烦，我们可以稍微转化一下。记 $l_i$ 为客栈 $i$ 的左侧第一个费用小于等于 $P$ 的客栈编号。那么，以 $i$ 为右端点的情况下，左端点的可选位置即为 $1-l_i$ 种所有颜色与客栈 $i$ 相同的客栈个数。
由于本题卡空间，必须采用滚动数组。数组 $s_i$ 记录颜色 $i$ 的出现次数，数组 $c_i$ 记录颜色 $i$ 的可选左端点个数。每次更新答案时，加上 $c_{color}$ 即可。
在示例代码中，可选的左端点包括其本身，因此当 $money\le P$ 时存在重复计算，答案减一。
代码如下：
1 | #include <bits/stdc++.h> |