### ~~ST表+二分+树状数组胡搞~~
- 题目要求在相邻客栈中找到一家最低消费不超过p元的咖啡店，那么就用ST表找区间最小值就好了，**最小值超过p，那么就找不到所要求的咖啡店了**。
- 对于每一个客栈，我们二分找到离这个客栈**最近的一个咖啡店且刚好满足最低消费不超过p**。假设这个客栈的位置是X，所找到咖啡店的位置是Y，**那么在[X,Y-1]内肯定没有满足最低消费不超过p的咖啡店了，反之在[Y,n]中的所有与该客栈色调相同的客栈都可以与该客栈组合形成一种方案，因为都可以在之间找到最低消费不超过p的咖啡店，那么只需求出在给定区间中与该客栈色调相同的客栈个数就好了。**然后就可以开始~~经过一些神奇的前缀和加减~~，加之总答案中。
- 对于每一种颜色的都开一个树状数组（因为总颜色比较少），前缀和加减，只能靠自行手推或者看代码了。
LuckyCloud
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 200100
using namespace std;
long long n,m,ans,c[60][maxn],t,Min[maxn][20],k,p,l,r,mid;
struct data
{
int col,mon;
}hotel[maxn];
inline long long read()
{
long long cnt=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){cnt=cnt*10+ch-48;ch=getchar();}
return cnt*f;
}
inline void add(long long g,long long x)
{
for (int i=x;i<=n;i+=i&-i)
c[g][i]++;
}
inline long long query(long long g,long long x)
{
long long ret=0;
for (int i=x;i;i-=i&-i)
ret+=c[g][i];
return ret;
}
void load()
{
for (int i=1;i<=n;i++)
Min[i][0]=hotel[i].mon;
}
inline long long get_min(long long l,long long r)
{
long long len=(long long)(log(r-l+1)/log(2));
return min(Min[l][len],Min[r-(1<<len)+1][len]);
}
int main()
{
n=read();k=read();p=read();
for (int i=1;i<=n;i++)
{
hotel[i].col=read();
hotel[i].mon=read();
add(hotel[i].col,i);
}
load();//ST表初始化
for (int i=1;i<=log(n)/log(2);i++)
for (register int j=1;j<=n-(1<<i)+1;j++)
Min[j][i]=min(Min[j][i-1],Min[j+(1<<(i-1))][i-1]);
for (int i=1;i<n;i++)
{
l=i+1;
r=n;
while (l<r)
{
mid=(l+r)>>1;
t=get_min(i,mid);
if (t>p) l=mid+1;
else r=mid;
}
t=get_min(i,l);
if (t>p) break;//从当前位置到最后一个位置已经没有最低消费不超过p的
//咖啡店里，继续做下去答案也不会发生变化，故直接跳出循环好了。
ans+=query(hotel[i].col,n)-query(hotel[i].col,l-1);//算出答案
}
printf("%d\n",ans);
return 0;
}
```