题解 | #[NOIP2011]选择客栈#

思路

枚举右端点 i 
当 fee[i] <= p 时，对其有贡献的左端点是：i 左侧所有与 i 同色的点
当 fee[i] > p 时，对其有贡献的左端点分为两种：
(1) i 左侧，所有与 i 同色的，fee[j] <= p 的 j 点   显然： 位置 j < 位置 i
(2) i 左侧，所有与 i 同色的，在某个 j 点左侧的点    ps：j 就是 (1) 中的 j

为了方便 fee[i] > p 的情况，我们在 fee[i] <= p 时 才对 num[color] 进行更新

注：
color[i] ：第 i 个客栈的配色
num[color]：配色为 color 的客栈数目
temp：上一个 fee <= p 的点

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e6+10,M=1e4+10;

int color[N],num[M];
int n,k,p;
int temp;
ll ans;

int main(){
    cin>>n>>k>>p;
    for(int i=1;i<=n;i++){
        int fee;
        cin>>color[i]>>fee;
        if(fee<=p){
            for(int j=i;j>temp;j--) num[color[j]]++;
            temp=i;
            ans+=num[color[i]]-1;
        }
        else ans+=num[color[i]];
    }
    cout<<ans<<endl;
    return 0;
}