一种O(kn)做法：
c表示i客栈的色调，v表示i客栈咖啡店的最低消费
设s[i][c]表示i客栈前（包括i客栈）色调为c的客栈总数
e记录i客栈前最近一家最低消费不高于p的咖啡店
设f(i)表示以i为后一个客栈的选择方案数
那么有 s[i][c]-1 v<=p
f(i)={
s[e][c] v>p

最后累加f(i)即可。
代码：（还可优化到O(n)）
~~~
#include <cstdio>
int n,k,p,e,ans;
int c,v,s[200005][55];
int main(){
//freopen("input.txt","r",stdin);
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=n;i++){
scanf("%d%d",&c,&v);
s[i][c]=s[i-1][c]+1;
for(int j=0;j<k;j++)
if(j!=c) s[i][j]=s[i-1][j];
if(v<=p) ans+=s[e=i][c]-1;
else ans+=s[e][c];
}
printf("%d\n",ans);
return 0;
}

**参考了许多大犇的题解。**

我也不清楚自己怎么过的。厚颜无耻的发个题解。。

看了数据马上明白要满分一定有时间复杂度为N*k的算法。因此我们先考虑颜色0的情况（其他颜色在最外层套个for即可）
不难发现这个题目很有想头。
但是实际写起来却有点复杂

这里给出一种类似动规又有点像递推（应该就是递推）的写法。

建立一个数组X，一开始边界是0，用来存这个点（客栈抽象为点）之前有几个能选上的客栈。
因此给出一个递推式
##
x[j]=x[j-1] p[i]>p
x[j]=num p[i]<=p num=之前相同颜色的客栈数

假设当前枚举的客栈颜色是0.我们把颜色0的客栈作为客栈。其他颜色的都当作它只是个点（就是只开咖啡馆的）

怎么得到的呢？如果这个点p[i]<=p，很明显，这个点左边的所有客栈和这个点右边的所有客栈都经过这个点，因为小于P，都可以在这里聚会。显然，如果在这个点右面找到了一个相同颜色的客栈，那么他跟左边所有相同颜色的客栈都可以组成一个答案。即x[j]=num p[i]<=p num=之前相同颜色的客栈数

那么p[i]>p时呢？我们只能根据前面这个点的情况来得到答案。实质类似于把这些不符合条件的客栈压缩成了一个客栈。

然后每次枚举到我们需要的颜色的客栈就ans=ans+x[i]即可。因为x[i]存的是之前符合条件的客栈数。

模拟模拟发现，有个数据我们没考虑到
5 1 3
0 9
0 9
0 9
0 1
0 9

我们算出来是6，但是明显答案是7！！
为毛？
我们发现。X[1]=0 X[2]=0 X[3]=0 X[4]=3，这都是正确的。 X[5]为毛还是3？明明前面4个客栈都行啊！！

原因是我们上面的考虑是基于2个客栈中间有颜色不一样的客栈作为过渡的点情况考虑的。而这个情况我们没把0,1的客栈考虑进去，也把它当成了一个过渡的点！

因此对这个情况加个特判，即
##
if (j<>1) and (a[j-1,1]=i) and (a[j-1,2]<=p) then
x[j]:=num;
如果这个客栈前一个客栈符合条件的。且同时能作为过渡点P，那么他也应该是x[j]:=num(即要算上他自己！）

因此给出下面这个AC代码

本题解法很多。关键自己理解即可。不必在意能否看懂题解。自己可模拟找到自己能理解的写法，其实我觉得考虑的好点的话压根不需要这个特判。若写的渣，望大牛嘴下留情。

写完这题后。顺这个思路下去。发现其实这题可以不枚举K，好像200000的数组都不用开，具体思路就不再废话了....
###pascal code
program P1737;
var a:array[1..200000,1..2] of longint;
x:array[0..200000] of longint;
n,k,p,i,ans,num,j:longint;
begin
read(n,k,p); for i:=1 to n do read(a[i,1],a[i,2]); ans:=0; //读入
for i:=0 to k-1 do //枚举每种颜色
begin
fillchar(x,sizeof(x),0); num:=0; //初始化
for j:=1 to n do
begin
if a[j,2]<=p then //2种递推情况
x[j]:=num
else
x[j]:=x[j-1];

if (j<>1) and (a[j-1,1]=i) and (a[j-1,2]<=p) then //过渡用的客栈也是答案的情况的特判
x[j]:=num;

if a[j,1]=i then //统计我们需要的颜色之前能有几个客栈能跟它组合成答案
begin
ans:=ans+x[j]; inc(num); //记录答案，找到的颜色相同的客栈数num+1
end;
end;
end;

write(ans); //输出
end.

#1 Accepted 3ms 256.0 KiB
#2 Accepted 3ms 296.0 KiB
#3 Accepted 3ms 328.0 KiB
#4 Accepted 3ms 372.0 KiB
#5 Accepted 3ms 368.0 KiB
#6 Accepted 3ms 256.0 KiB
#7 Accepted 4ms 308.0 KiB
#8 Accepted 8ms 324.0 KiB
#9 Accepted 11ms 356.0 KiB
#10 Accepted 11ms 384.0 KiB

#include <cstdio>
#include <cctype>

const int MAXN = 110, L = 10000;

int n, m, k, p, q, sum, a[MAXN], b[MAXN], c[MAXN];

char buf[L], *beg = buf, *end = buf;
inline char getChar() {
  if (!(beg - end)) {
    if (feof(stdin)) return '\0';
    beg = buf, end = buf + fread(buf, 1, L, stdin);
  } return *(beg++);
}

inline int getInt() {
  int sum(0); char _c;
  while (!isdigit(_c = getChar()));
  do sum = sum * 10 + _c - '0';
  while (isdigit(_c = getChar()));
  return sum;
}

int main() {
  //scanf("%d%*d%d", &n, &p);
  n = getInt(), getInt(), p = getInt();
  for (register int i = 1; i <= n; ++i) {
    //scanf("%d%d", &k, &q);
    k = getInt(), q = getInt();
    (q <= p) && (m = i);  //若在最低消费范围内则记录该位置
    (m >= a[k]) && (c[k] = b[k]); //若在当前颜色之前出现过那么记录当前颜色的出现次数
    a[k] = i; //更新当前颜色最后出现的位置
    sum += c[k], ++b[k];
  } printf("%d\n", sum);
  return 0;
}

记录当前点之前各种颜色出现次数，利用前缀和。

#include <iostream>
#define ULL unsigned long long

using namespace std;

int n,m,mi;
int p[200001][2]={0};
int re[200001][50]={0};

int main()
{
    cin>>n>>m>>mi;
    int i,j,last=0;
    for(i=1;i<=n;i++)
    {
        cin>>p[i][0]>>p[i][1];
        for(j=0;j<m;j++)
        {
            re[i][j]=re[i-1][j];
        }
        re[i][p[i][0]]++;
    }
    ULL ans=0;
    for(i=1;i<=n;i++)
    {
        if(p[i][1]<=mi)
        {
            last=i;
        }
        if(last>0)
        {
            if(last==i)
            {
                ans+=re[last-1][p[i][0]];
            }
            else
            {
                ans+=re[last][p[i][0]];
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

暴力O(knlogn)算法，900ms过掉

#   状态  耗时  内存占用
#1   Accepted   3ms 4.215 MiB
#2   Accepted   3ms 4.242 MiB
#3   Accepted   8ms 10.211 MiB
#4   Accepted   8ms 10.125 MiB
#5   Accepted   10ms    10.223 MiB
#6   Accepted   18ms    26.203 MiB
#7   Accepted   276ms   40.375 MiB
#8   Accepted   650ms   40.5 MiB
#9   Accepted   949ms   40.469 MiB
#10  Accepted   971ms   40.609 MiB

#include <stdio.h>

struct node
{
    int pos;
    int price;
} h[200001];

int color[200001], price[200001], chain[51][200001], htot;

void push(int npos, int nprice)
{
    h[++htot].pos = npos;
    h[htot].price = nprice;
    int ptr = htot;
    while ((ptr > 1) && (h[ptr].price < h[ptr / 2].price))
    {
        struct node t = h[ptr]; h[ptr] = h[ptr / 2]; h[ptr / 2] = t;
        ptr /= 2;
    }
}

void pop()
{
    h[1] = h[htot--];
    int ptr = 1;
    while (ptr * 2 <= htot)
    {
        int son = ptr * 2 + 1;
        if ((ptr * 2 == htot) || (h[ptr * 2].price < h[ptr * 2 + 1].price))
            son = ptr * 2;
        if (h[son].price < h[ptr].price)
        {
            struct node t = h[ptr]; h[ptr] = h[son]; h[son] = t;
            ptr = son;
        }
        else
            break;
    }
}

int main()
{
    int n, k, p;
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &color[i], &price[i]);
        chain[color[i]][++chain[color[i]][0]] = i;
    }
    int ans = 0;
    for (int i = 0; i < k; i++)
    {
        int *cchain = (int*)chain[i];
        if (cchain[0] < 2)
            continue;
        int l = 1, r = 2;
        htot = 0;
        for (int j = cchain[1]; j <= cchain[2]; j++)
            push(j, price[j]);
        while (l < r)
        {
            while (h[1].pos < cchain[l])
                pop();
            if (h[1].price <= p)
            {
                ans += cchain[0] - r + 1;
                l++;
            }
            if ((l == r) || (h[1].price > p))
            {
                if (r < cchain[0])
                    r++;
                else
                    break;
                for (int j = cchain[r - 1] + 1; j <= cchain[r]; j++)
                    push(j, price[j]);
            }
        }
    }
    printf("%d", ans);
}

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,k,p,a[200002],st[200002][20],ans;
vector<int> b[50];
void init(){
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)<=n+1;i++)
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int rmq(int l,int r){
int s=0;
while((1<<s)<=r-l+1)s++;
s--;
return min(st[l][s],st[r-(1<<s)+1][s]);
}
int main(){
cin>>n>>k>>p;
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&st[i][0]);
b[a[i]].push_back(i);
}
init();
for(int i=0;i<k;i++){
if(b[i].size()>1){
for(int j=0;j<b[i].size()-1;j++){
//if(rmq(b[i][j],b[i][j+1])<=p)ans+=b[i].size()-j-1;
for(int m=j+1;m<b[i].size();m++){
if(rmq(b[i][j],b[i][m])<=p){
ans+=b[i].size()-m;
break;
}
}
}
}
}
cout<<ans<<endl;
}

暴力模拟......

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
int color[200001],money[200001];
int all[51],_mid[51],_left[51];
int main()
{
    int n,k,p,ans=0;
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&color[i],&money[i]);
        all[color[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        _mid[color[i]]++;
        if(money[i]<=p)
        {
            ans+=_mid[color[i]]-_left[color[i]]-1;
            for(int j=0;j<k;j++)
            {
                ans+=(_mid[j]-_left[j])*(all[j]-_mid[j]);
                _left[j]=_mid[j];
            }
        }
    }
    printf("%d",ans);
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

struct st_1
{
    int l,r,mid,x;
}st[2*262144+2];

int n,m,t,ans;
int cnt[50];
int c[200000+1];
int p[200000+1];
int num[200000+1];
vector<vector<int> > cp;

void build_st_1(int now,int l,int r)
{
    st[now].l=l,st[now].r=r,st[now].mid=(l+r)/2;
    if (l<r)
    {
        if (l<=st[now].mid)
            build_st_1(now*2,l,st[now].mid);
        if (st[now].mid+1<=r)
            build_st_1(now*2+1,st[now].mid+1,r);
    }
    if (l==r)
        st[now].x=p[l];
    else
        st[now].x=min(st[now*2].x,st[now*2+1].x);
}

int sum_1(int now,int l,int r)
{
    if (st[now].l==l&&r==st[now].r)
        return st[now].x;
    else if (r<=st[now].mid)
        return sum_1(now*2,l,r);
    else if (st[now].mid+1<=l)
        return sum_1(now*2+1,l,r);
    else
        return min(sum_1(now*2,l,st[now].mid),sum_1(now*2+1,st[now].mid+1,r));
}

int main()
{
    while (~scanf("%d%d%d",&n,&m,&t))
    {
        cp.resize(0);
        cp.resize(m);
        for (int i=0;i<m;i++)
            cp[i].resize(0);
        memset(cnt,0,sizeof(cnt));
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&c[i],&p[i]);
            cnt[c[i]]++;
            num[i]=cnt[c[i]];
            cp[c[i]].push_back(i);
        }
        for (int i=1;i<=n;i++)
            num[i]=cnt[c[i]]-num[i]+1;
        ans=0;
        build_st_1(1,1,n);
        for (int i=0;i<m;i++)
        {
            int temp_size=cp[i].size();
            for (int j=0;j<temp_size;j++)
                for (int k=j+1;k<temp_size;k++)
                    if (sum_1(1,cp[i][j],cp[i][k])<=t)
                    {
                        ans+=num[cp[i][k]];
                        break;
                    }
        }
        printf("%d\n",ans);
    }
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;

const int INF=200000+34;
int n,k,p,total=0;
int mval[INF][20],color[INF];
vector<int>Grather[51];
int max(int a,int b) { return a>b?a:b;}
int min(int a,int b) { return a<b?a:b;}
int log(int x) //求log2(x)
{
int tot=0;
while(x>>1) tot++,x>>=1;
return tot;
}

void ST()
{
for(int j=1;j<=log(n);j++)
{
int p=(1<<(j-1)); //2^(j-1);
for(int i=1;i<=n;i++)
if((i+p)<=n)
mval[i][j]=min(mval[i][j-1],mval[i+p][j-1]);
}

}

int query(int x,int y)
{
int lv=log(abs(x-y)+1);
return min(mval[x][lv],mval[y-(1<<lv)+1][lv]);
}

int main()
{
scanf("%d%d%d",&n,&k,&p);
int pi;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&color[i],&pi);
mval[i][0]=pi;
Grather[color[i]].push_back(i);
}

ST(); //跑倍增；

for(int i=0;i<k;i++)
{
int len=Grather[i].size()-1;
for(int j=0;j<=len;j++)
{
for(int v=j+1;v<=len;v++)
{
if(query(Grather[i][j],Grather[i][v])<=p)
{
total+=len-v+1;
break;
}
}
}
}

cout<<total;

return 0;
}

看了楼上的题解 很久才明白 我把它讲清楚些
#include <cstdio>

int main(){
int n,k,p,color,last=-1,v,a[60]={0},b[60]={0},c[60]={0},ans=0;
//a[i]=m 色调i最后出现的位置为m
//b[i]=m 色调i已经出现了m次
//c[i]=m 最新一个可以作为咖啡馆的客栈 该客栈之前的色调为i的总数为m

//last 最新一个可以作为咖啡馆的客栈
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=n;i++){
scanf("%d%d",&color,&v);
if(v<=p)
last=i;
if(last>=a[color])//(1)找到咖啡馆可以使 客栈i 与 last之前的客栈 形成方案
c[color]=b[color];
a[color]=i;
b[color]++;
ans+=c[color];
//如果 (1)处更新 代表i点可以成为咖啡馆 那么i与i之前的可以形成方案
//如果 (1)处未更新 则i可以 以last为咖啡馆 与last之前的形成方案
}
printf("%d",ans);
return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Shop
{
    int cost;
    int color;
};
bool judge(Shop shops[],int i1,int i2,int p)
{
    for(int i=i1;i<=i2;i++)
    {
//      cout<<shops[i].cost<<endl;
        if(shops[i].cost<=p)
            return true;
    }
    return false;
}
int solve(Shop shops[],vector<int> v,int p)
{
    int dp[v.size()];dp[0]=0;
    int ans=0; 
    for(int i=1;i<v.size();i++)
    {
        if(judge(shops,v[i-1],v[i],p))
            dp[i]=i+dp[i-1];
        else
            if(i==1)
                dp[i]=dp[i-1]*2;
            else
                dp[i]=dp[i-1]*2-dp[i-2];
//      cout<<dp[i]<<endl;
    }
    return dp[v.size()-1];
}
int main ()
{
    int n,k,p;
    cin>>n>>k>>p;
    int cost,color;
    Shop shops[n];
    vector<int> v[k];
    for(int i=0;i<n;i++)
    {
        cin>>shops[i].color>>shops[i].cost;
        v[shops[i].color].push_back(i);
    }
    int ans=0;
    for(int i=0;i<k;i++)
    {
        ans+=solve(shops,v[i],p);
//      cout<<ans<<endl;
    }
    cout<<ans<<endl;
    return 0;
}

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int cnt[200001][51];
int c[200001],v[200001],last[51];
int n,k,p,ans;
int main()
{
    scanf("%d%d%d",&n,&k,&p);
    For(i,1,n)
        scanf("%d%d",&c[i],&v[i]);
    For(i,1,n)  For(j,0,k)  cnt[i][j]=cnt[i-1][j]+(c[i]==j);
    int tp=-1;
    For(i,1,n)
    {
        if(v[i]<=p) tp=i;
        if(tp==-1)  continue;
        if(last[c[i]]<=tp&&tp<=i)   ans+=cnt[i-1][c[i]];
        else
            ans+=cnt[tp][c[i]];
        last[c[i]]=i;
    }
    printf("%d",ans);
}

为啥你萌的代码都这么短(/ω＼)
顺序扫描，对每种颜色分别处理
细节比较多，怼了4个小时才AC掉……（吐槽一下AStyle君，窄代码给调的略坑啊）
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define rep(id,a,b) for(int id=(a);id<(b);++id)
#define irep(id,a,b) for(int id=(a);id>(b);--id)
#define reset(arr,c) memset(arr,c,sizeof(arr))

typedef long long int64;

const int maxN = 200000 + 5;
const int maxK = 50 + 5;

int N, K, P;
int color[maxN], cost[maxN];

void read (int* a)
{
*a = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
do
{
(*a) = (*a) * 10 + c - '0';
c = getchar();
}
while (c >= '0' && c <= '9');
}

void input()
{
read (&N);
read (&K);
read (&P);
rep (i, 0, N)
{
read (color + i);
read (cost + i);
}
}

int flag (0);
int cnt[maxK] = {0};

inline void mv (int i, int d)
{
if (cost[i] <= P) flag += d;
}

int64 solve()
{
rep (i, 0, N) ++cnt[color[i]];
int64 ans (0);
rep (i, 0, K)
{
int h, t, rem;
t = 0;
while (color[t] != i) ++t;
h = t;
rem = cnt[i] - 1;
flag = (cost[t] <= P) ? 1 : 0;
while (1)
{
if (t < h && flag) ans += (rem + 1);
else if (rem)
{
do
{
--rem;
do
{
++h;
mv (h, 1);
}
while (color[h] != i);
}
while (rem && !flag);
if (flag) ans += (rem + 1);
}
else break;
do
{
mv (t, -1);
++t;
}
while (color[t] != i);
}
}
return ans;
}

int main()
{
input();
printf ("%lld\n", solve() );
return 0;
}
提供一组易错数据：
8 2 2
0 3 1 1 1 3 0 3 1 3 1 3 1 1 1 1
输出：13

可以用倍增来做，（加一点点的并查集的思想）。。。
代码有点多。

/* a数组是记录同一种颜色中的酒店所出现的最后一次的位置；
b数组记录同一种颜色的酒店的出现次数，
而c数组则是临时记录当前同样颜色的酒店出现的次数，
也就是为找对应点而进行的临时记录（也可以理解为当前色调的方法数量）。
那么，通过使用上述方法，仅仅需要一个for循环，即可解决问题*/
#include<iostream>
using namespace std;
int n,k,p,m,x,y,sum;
int a[100],b[100],c[100];
int main()
{

cin>>n>>k>>p;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
if(y<=p) m=i;//如果咖啡店的最低消费地于标准，那么记录其位置
if(m>=a[x]) c[x]=b[x];//如果在当前颜色的酒店之前有出现过同样颜色的酒店那么记录当前同种颜色的酒店的出现次数
/*特注：当到COODVS上第四组数据时也许会因为“y<=p”不会记录当前的位置，
但是会记录之前有满足“y<=p”条件的位置，
也就是说两个人住的客栈之间有满足条件的咖啡馆，
那么也就可以让c数组的对应颜色加上1了，即“c[x]=b[x]”
从而使后面的总数加上1*/

a[x]=i;//记录同样颜色的酒店最后一次的出现位置
sum+=c[x];
/*每一个酒店都可以作为对应点，所以不需要再去加上任何的判断，记录住宿的方法，
c数组可以理解为当前色调位置，到之前满足“y<=p”色调位置的方案 */
b[x]++;//记录出现次数的总数
}
cout<<sum;
return 0;
}

#include<iostream>
using namespace std;
int color[51]={0},color_ok[51]={0};
long long ans=0;
int main()
{
int n,k,p,ci,pi;
cin>>n>>k>>p;
for(int i=0;i<n;i++){
cin>>ci>>pi;
if(pi<=p){
ans+=color[ci]++;
for(int j=0;j<k;j++)
color_ok[j]=color[j];
}
else{
ans+=color_ok[ci];
color[ci]++;
}

}

cout<<ans<<endl;
return 0;
}

###时间复杂度O(nk)，空间复杂度O(k).

使用sum[i]存储上一个可用咖啡店及之前的色调i的客栈数，cnt[i]存储上一个可用咖啡店之后色调为i的客栈数，每次遇到可用的客栈就把cnt加到sum中。

###C++代码

#include<cstdio>
#include<cstring>
int n,k,p,i,j,t,cl,pr,sc=0,sum[51],cnt[51];
char tmp[1024];
long long ans=0;

void read(int &v)
{
scanf("%d",&v);
return;
}
void readln(int &v0)
{
scanf("%d",&v0);
gets(tmp);
return;
}
int main()
{
read(n);
read(k);
readln(p);
for(i=0;i<k;i++)
{
sum[i]=0;
cnt[i]=0;
}
for(i=1;i<=n;i++)
{
read(cl);
readln(pr);
cnt[cl]++;
if(pr<=p)
{
for(j=0;j<k;j++)
{
sum[j]+=cnt[j];
cnt[j]=0;
}
}
ans+=sum[cl]-(pr<=p?1:0);
}
printf("%lld",ans);
return 0;
}

Pascal

//NOIP2015赛前留念

一个统计题目，渣渣做了一下注释求轻喷

思路

·如果当前最低消费可选，以此为结束，前面所有与此色调相同的都可搭配
·如果当前最低消费不可选，依次为结束，前面最后一个可选（不一定同色调）之前的与此色调相同的都可搭配

代码

program VijosP1737;

var
n, k, p, x, y, i, j: longint;
ans: int64;
col, col1: array[0..50] of longint;
//col1保存最后一个最低消费可选前的每个色调数目

begin
readln(n, k, p);
fillchar(col, sizeof(col), 0);
fillchar(col1, sizeof(col1), 0);
ans := 0;
for i := 1 to n do
begin
readln(x, y);
Inc(col[x]);
if y <= p then
begin
Inc(ans, col[x] - 1); //前面同色都可选（自己不能同自己搭配）
for j := 0 to k - 1 do
col1[j]:=col[j]; //每种颜色在此之前【可选的数目】更新为这个颜色【所有的数目】
end
else
begin
Inc(ans, col1[x]);
end;
end;
writeln(ans);
end.

第一次用lower_bound，调了一个下午.....奇怪的是时间居然变长了
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cctype>

using namespace std;

int n, k, p;
vector<int> h[51];
int cost[200001];
int next0[200002];

inline int in() {
int RV = 0;
char p = getchar();
while(!isdigit(p)) {
p = getchar();
}
while(isdigit(p)) {
RV *= 10;
RV += (p - '0');
p = getchar();
}
return RV;
}
int main(int argc, const char *argv[]) {
scanf("%d %d %d", &n, &k, &p);
int color;
for (int i = 1; i <= n; ++i) {
color = in();
cost[i] = in();
h[color].push_back(i);
}
for (int i = n; i >= 1; --i) {
if (cost[i] > p)
next0[i] = next0[i + 1];
else
next0[i] = i;
}
int temp[200001];
int ans = 0;
for (int i = 0; i < k; ++i) {
int cnt = h[i].size();
for (int j = 0; j < cnt; ++j)
temp[j] = h[i][j];
for (int j = 0; j < cnt; ++j) {
int now = temp[j];
if (next0[now] == 0) break;
int p = lower_bound(temp + j + 1, temp + cnt, next0[now]) - temp;
ans += (cnt - p);
}
}
printf("%d\n", ans);
return 0;
}

O(n)算法
循环读入颜色为col[i]，价格为pri[i]的客栈，维护前缀和s[i]，表示前i个咖啡店最低消费不超过p的个数

那么我们可以发现以下性质：

性质1:对于同一种颜色的客栈i j k (i<j)
如果(i,j)是可行方案，那么对于任意k>j,(i,k)是可行方案

性质2:s单调不降

性质3:s[i]-s[j-1]=0等价于j到i之间没有价格不超过p的咖啡店，若i<j，且s[i]=s[j]，那么对于任意i<k<j，有s[i]=s[k]=s[j]

性质4:综合以上几点，假设我们设b[i]表示第一个与i无法形成合法方案的客栈编号，那么对于任意i<j，有b[i]<=b[j]具有单调性

因此我们对于任一种颜色color，设立一个单调队列，储存所有颜色为color且不能与i组成合理方案的客栈
显然，队列中的任一元素j，满足s[j]=s[i]

同时，我们记录一个数组tot[color]，表示颜色为color且能与i组成合法方案的客栈个数

循环处理
当 当前客栈i满足
s[i]-s[color队头元素-1]>0，
那么color队头出队，tot[col]增加1

此时，与i能构成合法方案的客栈j(j<i)有tot[col]个，将答案加上tot[col]

最后，再将i插入单调队列color中即可

另：由于不知道每个单调队列中最多有多少个元素，因此，可以使用指针或数组模拟指针实现单调队列
#include<cstdio>
const int maxk=50,maxn=200000;
struct node{int v,ne;};
int n,k,p,col,pri,st,head[maxk],last[maxk],s[maxn+10],tot[maxk];
node me[maxn+10];
long long ans;
char c;
void scan(int *x){
while ((c=getchar())<'0');
*x=c-'0';
while ((c=getchar())>='0')
*x=*x*10+c-'0';
}
int main(){
scan(&n);
scan(&k);
scan(&p);
for (int i=1;i<=n;i++){
scan(&col);
scan(&pri);
s[i]=s[i-1];
if (pri<=p)
s[i]++;
while ((head[col])&&(s[i]>s[me[head[col]].v-1])){
tot[col]++;
head[col]=me[head[col]].ne;
}
ans+=tot[col];
if (head[col])
me[last[col]].ne=++st;
else
head[col]=++st;
last[col]=st;
me[st].v=i;
}
printf("%lld\n",ans);
return 0;
}