Final Dash
信竞路上的重要节点
写在前面 👇
今年的CSP-S就是初中生涯的最后一次竞赛了。初二成绩不理想（110左右，二等），希望初三拿个一等。而且，年段排名也掉到了70，副科炸开。所以，来个Ultra Dash吧。
初审题
题目
题目信息整理后如上图，要求求解的是同色调，且最低消费不超过他们支付能力的两两组合数目。
以上信息只要知道客栈编号，相应的色调，最低消费就都清楚了，可能很容易想到暴力搜索。
做法
法一：O(n^3)
直接进行暴力枚举，用i,j枚举两个人的客栈位置，判断区间是否合法，用ans统计并输出。
预估：过前两个测试点。约
法二：O(n^2)
在算法一大基础上进行优化。我们会发现算法一用了O(n)的时间来判断这个区间是否合法。如果我们做一些预处理，那么就可以节省这一部分的时间。
很快，就想到了前缀和。即从第一家客栈到目前的客栈为止符合消费能力的客栈数。
预估：
法三O(n*k)
观察数据范围，10^5平方级别的算法会超时。观察到k（颜色）很小，这时应当尽量朝
O(n*k)优化算法
中间有好多位置我需要访问好多遍，能不能一遍完成呢。可以从左往右依次扫过去的过程中记下在i位置之前已经出现了几个颜色一样的了，记为num[i]，然后再保存一下当前最后的一个够便宜的客栈的位置，记为last，每次遇到一个新的当前颜色的客栈，我就给答案加上最后一个够便宜的客栈之前的相同颜色的个数，即就是加上num[last]。
预估：
法四：O(n)
通过观察数据范围，O(n*k)的算法也对于加强版数据会超时，这时就要继续将算法优化至O(n)
可以设置三个数组：
SZ1[X]: 色调X到当前客栈有几家
SZ3[X]: 上一次遇到不超过P的时间节点（客栈号）
SZ2[X]: 该时间点之前色调与i相同的客栈有几家
细节：同色数目先统计再累加，所以不会出现自己和自己配对的情况。
加强
法四可以过加强版
