丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从1 到n 编号。每家客栈都按照某一种色调进行装饰（总共k 种，用整数0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过p。
他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。

共n+1 行。
第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；
接下来的 n 行，第i+1 行两个整数，之间用一个空格隔开，分别表示i 号客栈的装饰色调和i 号客栈的咖啡店的最低消费。

输出只有一行，一个整数，表示可选的住宿方案的总数。

5 2 3
0 5
1 3
0 2
1 4
1 5

3

【输入输出样例说明】

2 人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，④⑤，
但是若选择住 4、5 号客栈的话，4、5 号客栈之间的咖啡店的最低消费是 4，而两人能承受
的最低消费是 3 元，所以不满足要求。因此只有前 3 种方案可选。

【数据范围】
对于 30%的数据，有n≤100；
对于 50%的数据，有n≤1,000；
对于 100%的数据，有2≤n≤200,000，0<k≤50，0≤p≤100， 0≤最低消费≤100。

#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<vector>#include<queue>#include<stack>#include<algorithm>#define maxn 200005#define maxint ~0U>>2using namespace std;int n,k,p,money[maxn],col[maxn],d[maxn][30],ans = 0;vector<int> hotel[55];void input(){    cin>>n>>k>>p;    for(int i = 0;i < n;i++){        scanf("%d%d",&col[i],&money[i]);        hotel[col[i]].push_back(i);    }}void init_rmq(){    for(int i = 0;i < n;i++) d[i][0] = money[i];    for(int j = 1;(1<<j) <= n;j++){        for(int i = 0;i + (1<<j) - 1 < n;i++){            d[i][j] = min(d[i][j-1],d[i+(1<<(j-1))][j-1]);        }    }}int rmq(int l,int r){    int k = 0;    while((1<<(k+1)) <= r-l+1) k++;    return min(d[l][k],d[r-(1<<k)+1][k]);}void work(){    int now;    for(int i = 0;i < k;i++){        if(hotel[i].size() < 2) continue;        for(int j = 0;j < hotel[i].size() - 1;j++){            for(int k = j + 1;k < hotel[i].size();k++){                now = rmq(hotel[i][j],hotel[i][k]);                if(now<=p) {ans += hotel[i].size() - k;break;}            }        }    }    cout<<ans<<endl;}int main(){    input();    init_rmq();    work();    return 0;}#include <iostream>#include <cstdio>using namespace std;int n,k,p,sum[201000][60],colour[201000],f[201000],ans;//f[]记录距每个点最近的花费小于p的点，sum[i][j]存从0到i第j种颜色有几个（前缀和）int main(){scanf("%d%d%d",&n,&k,&p);for(int i=1;i<=n;i++){int x;scanf("%d%d",&colour[i],&x);for(int j=0;j<k;j++)sum[i][j]+=sum[i-1][j];sum[i][colour[i]]++;if(x<=p)f[i]=i;elsef[i]=f[i-1];}for(int i=2;i<=n;i++){if(f[i]==i)ans+=sum[i][colour[i]]-1;//若其本身便是离其最近的花费小于p的点，那么前面榆次店一样颜色的点都可与之组合，符合题目要求，所以加上前缀和，但因为会多加一个（该点自己，因两两组合），所以要减去一个elseans+=sum[f[i]][colour[i]];//若本身不是离其最近的花费小于p的点，那么离它最近的那个点向前与现在n所在这个点颜色相同的（包含n所在这个个点）点都可与之形成符合题目要求的组合，所以加上前缀和（从f[]往前的区间)}printf("%d",ans);return 0;}