下面进入正题：
先解释题意
简单来讲就是在一段一维客栈中 任意选择两个客栈a,b
客栈a,b满足两个条件：
1. a,b颜色相同
2. [a,b]闭区间之间必须存在某个客栈的咖啡店的花费 ≤p\le p≤p ;
我们要求成立的a,b共有多少对
既然是 O(n)O(n)O(n) 的做法 那我们肯定是枚举
因为我们要找到所有成立的 a,b
那么我们就枚举每个b 想办法找到此时符合条件的a有多少个
先解释下变量t
t记录的是当前枚举客栈过程中 离我们枚举到的客栈最近的最低消费<=p的客栈的下标（第几个客栈）
例如 样例中 p=3p=3p=3：
我们枚举到1号客栈是 5>3,t=05>3, t=05>3,t=0 ;
枚举2号客栈 3≤33\le 33≤3 发现成立 t=3t=3t=3 ;
枚举3号客栈 2≤3,t=22\le 3 ,t=22≤3,t=2 ;
那么 t有什么用呢？
仔细一想我们会发现
我们枚举b时 此时成立的a的个数
a要成立 显然a一定要在t前面
这样就满足了上述第二个条件
a要成立 是不是还要满足第一个条件？
第一个条件是什么 不是a,b颜色相同?
那此时a成立的个数 不就在t前面 和b颜色相同的客栈的个数？
那就开个数组 num[]num[ ]num[] 实时更新在t前面的各个颜色的客栈有多少个啊
快速模拟一下样例：
我们枚举到2号客栈时 t更新为3 num[1]++ （1号颜色的客栈数）;
枚举到三号客栈，t又更新为2 ，num[0]++，ans+=num[0],ans=1;
枚举到4号客栈 ans+=num[1],ans=2;
枚举到5号客栈 ans+=num[1],ans=3；
这时我们就得到了答案 当然我们还用了一个color[]数组记录每个客栈的颜色
再提几点注意的地方
1 我们每发现新的符合条件的t 都要把(pre,t]区间客栈对应的颜色++（实时更新）
（pre）是上一个t， 同时注意上诉区间是左开右闭，这些细节问题自己很好想
2 如果这个客栈更新了t，ans+=num[这个客栈的颜色]-1
如果这个客栈没有更新t，ans+=num[这个客栈的颜色]
这也是细节问题 为什么呢
因为当这个客栈更新t时 我们在把[pre,t]区间客栈对应的颜色++
此时 这个客栈的颜色数包含了自己 所以要减一
写题解不易 望各位给我点个赞
下面奉上AC代码：
