这个题听说二分，但是我太菜不会二分，我就会模拟做qwq，时间复杂度O(nk)
我们可以先预处理出所有花费不超过p的咖啡厅，然后预处理一下各色客栈的前缀和。
之后我们假设咖啡厅左边及自己共有li间i色客栈，右边有ri间i色客栈，那么答案应该加上li*ri。但是我们发现这样是会漏掉一种情况的，当这家咖啡厅所在的客栈作为右边被人居住的客栈的时候，我们会漏算。因此我们需要for两边第一遍处理li*ri的情况，第二遍再单独处理咖啡厅作为右端点的情况。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; typedef long long lo; lo n,k,p,x,se[200020],s[200020][50],ans,wei[200020],tot; int main() { scanf("%lld%lld%lld",&n,&k,&p); for(int i=1;i<=n;i++) { scanf("%lld%lld",&se[i],&x); if(x<=p)//记录下所有的消费小于p的咖啡厅 wei[++tot]=i; } for(int i=1;i<=n;i++)//统计下前缀和 { for(int j=0;j<k;j++) s[i][j]+=s[i-1][j]; s[i][se[i]]++; } for(int i=1;i<=tot;i++)//先处理一般情况 for(int j=0;j<k;j++) ans+=(s[wei[i]][j]-s[wei[i-1]][j])*(s[n][j]-s[wei[i]][j]); for(int i=1;i<=tot;i++)//再对作为右侧客栈的情况进行处理 ans+=s[wei[i]-1][se[wei[i]]]-s[wei[i-1]][se[wei[i]]]; cout<<ans; }
原文：http://www.cnblogs.com/Loi-dfkdsmbd/p/7800351.html