选择客栈超短题解

下面进入正题：

先解释题意
简单来讲就是在一段一维客栈中 任意选择两个客栈a,b
客栈a,b满足两个条件：

1. a,b颜色相同
2. [a,b]闭区间之间必须存在某个客栈的咖啡店的花费 $\le p$ ;
   我们要求成立的a,b共有多少对

既然是 $O(n)$ 的做法 那我们肯定是枚举
因为我们要找到所有成立的 a,b
那么我们就枚举每个b 想办法找到此时符合条件的a有多少个

先解释下变量t

t记录的是当前枚举客栈过程中 离我们枚举到的客栈最近的最低消费<=p的客栈的下标（第几个客栈）
例如 样例中 $p=3$：

我们枚举到1号客栈是 $5>3, t=0$ ;
枚举2号客栈 $3\le 3$ 发现成立 $t=3$ ;
枚举3号客栈 $2\le 3 ,t=2$ ;

那么 t有什么用呢？

仔细一想我们会发现
我们枚举b时 此时成立的a的个数
a要成立 显然a一定要在t前面
这样就满足了上述第二个条件
a要成立 是不是还要满足第一个条件？
第一个条件是什么 不是a,b颜色相同?
那此时a成立的个数 不就在t前面 和b颜色相同的客栈的个数？
那就开个数组 $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代码：

#include<iostream>
using namespace std;
int n,k,p,t,ans,price,num[105],color[200005];
int main(){
	cin>>n>>k>>p;
	for(int i=1;i<=n;i++){
		cin>>color[i]>>price;
		if(price<=p){
			for(int j=i;j>t;j--)num[color[j]]++;
			t=i;
			ans+=num[color[i]]-1;
		}
		else ans+=num[color[i]];
	}
	cout<<ans;
}