分析

如果枚举左右端点复杂度的下界为 。那么只能枚举一个端点，那么对于另一个端点，我们只关心这两个端点中间有没有最低消费不大于 的。如果我们从左向右扫描，我们一定希望这个点越靠右越好，因为这可以影响更多的点对。对于每一个颜色记录上一个同颜色在哪里。那么只需要最小值点出现在 的右边，那么就可以更新答案，否则只能继承上一个节点的答案。时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5+100;
int c[N],val[N],cnt[N],last[N],tot[N],n,k,p,R;
LL ans = 0;
int main() {
    scanf("%d%d%d",&n,&k,&p);
    for(int i = 1;i <= n;i++) {
        scanf("%d%d",&c[i],&val[i]);
    } 
    for(int i = 1;i <= n;i++) {
        if(val[i] <= p) R = i;
        if(R >= last[c[i]]) tot[c[i]] = cnt[c[i]];
        last[c[i]] = i;
        ans += tot[c[i]];
        cnt[c[i]]++;
    }
    cout << ans << endl;
    return 0;
}