看看大家都是\(O(n)\)的，小蒟蒻已经方得不行……
那我来一篇\(O(nk+nlogn)\)的好了,还是可以AC哒
用\(cnt_i\)表示前i家中最低消费不超过\(p\)元的咖啡馆的数量
用\(sum_{i,k}\)表示前i家中k色调的客栈总数
我们枚举第一家客栈
并计算此时选择第二家客栈的方法总数
（就是有多少家客栈符合要求，是同色调，中间有合适的咖啡馆的）
同色调我们已经用前缀和维护了
现在的关键是怎么找到合适的咖啡馆
O(n)枚举显然会TLE
但是我们快乐地发现cnt数组（合适的咖啡馆的前缀和）是递增的
所以我们可以二分来寻找这个最靠前的合适的咖啡馆
由于我是个又懒又容易写错二分的人
我们使用upper_bound来寻找
但是当你兴冲冲地写完的时候会发现过不了样例
是不是很自闭？
tmp_i=max(tmp_i,i+1);
我们需要这句话,
不然我们的答案就是错的
会多算一个。
如果想不明白把样例带进去就可以了
输入+计算前缀和\(O(nk)\)
计算方案总数\(O(nlogn)\)
可以过
#include <bits/stdc++.h>
using namespace std;
struct pos{
int color,cost;
}inn[200005];
int n,k,p,ans;
int cnt[200005];
//【前缀和】前i家中合适的咖啡馆的数量
int sum[200005][55];
//【前缀和】sum[i][k] 前i家中k色调的客栈总数
int main() {
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=n;i++){
cnt[i]=cnt[i-1];
for(int j=0;j<=k-1;j++) sum[i][j]=sum[i-1][j];
scanf("%d%d",&inn[i].color,&inn[i].cost);
if(inn[i].cost<=p) cnt[i]++;
sum[i][inn[i].color]++;
}
//输入+计算前缀和
for(int i=1;i<=n;i++){
int tmp_i=upper_bound(cnt+1,cnt+n+1,cnt[i-1])-cnt;
tmp_i=max(tmp_i,i+1);
//寻找第一家最低消费不超过p元的咖啡馆
int qaq=sum[n][inn[i].color]-sum[tmp_i-1][inn[i].color];
if(qaq>0) ans+=qaq;//计算方法总数
}
printf("%d\n",ans);
return 0;
}