丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从1到n编号。
每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0 ~ k−1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。
晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p 。
他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。
样例说明
两人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，④⑤，但是若选择住④⑤号客栈的话，④⑤号客栈之间的咖啡店的最低消费是4，而两人能承受的最低消费是3元，所以不满足要求。因此只有前 3 种方案可选。
我还是太菜了，看到题之后想了一个DP，也没有证明，就交上去了
然后挂的飞起
后来才发现少考虑了几种情况
然后邮箱了一下，发现是个递推
首先我们记录每一种颜色的个数，然后记录当前最近的符合要求的咖啡馆，然后在记录当颜色能匹配的最多的同种颜色的个数
如果能更新就更新，不能更新就用原来的值
下面给出代码：
#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } int n,m,p; int cnt[2000006],last[2000006]; int f[2000006]; int set=0; int ans=0; int main(){ n=rd(),m=rd(),p=rd(); for(int i=1;i<=n;i++){ int x=rd(),y=rd(); if(y<=p) set=i; if(set>=last[x]) f[x]=cnt[x]; ans+=f[x]; last[x]=i; cnt[x]++; } write(ans); return 0; }