没用二分居然过了
#include <cstdio>
#include <cstdlib>
#include <cctype>

using namespace std;

struct N {
int x, next;
} node[51][200005];

int n, k, p;
int color[200005], cost[200005], next[200005];
int tot[51];

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);
for (int i = 1; i <= n; ++i) {
color[i] = in();
cost[i] = in();
}
for (int i = n; i >= 1; --i)
{
if (cost[i] <= p)
next[i] = i;
else
next[i] = next[i + 1];
}
for (int i = 0; i < k; ++i) {
for (int j = 1; j <= n; ++j) {
if (color[j] == i) {
node[i][++tot[i]].x = j;
node[i][tot[i]].next = next[j];
}
}
}
int ans = 0;
for (int i = 0; i < k; ++i) {
for (int j = 1; j < tot[i]; ++j) {
if (node[i][j].next == 0)
break;
/
int l = j + 1, r = tot[i], mid;
mid = (l + r) / 2;
while (l + 1 <= r) {
mid = (l + r) / 2;
if (mid == l || mid == r)
break;
if (node[i][mid].x < node[i][j].next)
{
l = mid;
}
if (node[i][mid].x == node[i][j].next)
break;
if (node[i][mid].x > node[i][j].next)
r = mid;
}
//printf ("%d %d %d\n", i, j, mid);
if (node[i][mid].x < node[i][j].next)
continue;*/
int ss = j + 1;
for (ss = j + 1; ss <= tot[i]; ++ss)
if (node[i][ss].x >= node[i][j].next)
break;
ans += (tot[i] - ss + 1);
}
}
printf("%d\n", ans);
return 0;
}

include<iostream>
include<cstdio>
include<algorithm>
include<vector>
using namespace std;
const int MAXN=200010;
int n,k,p;
long long ans;
int c[MAXN],l[MAXN],cost[MAXN];
int G[110][200010];
int cnr[200010];
int main(){
cin>>n>>k>>p;
int count=0;
for (int i=1;i<=n;i++) {
scanf("%d%d",&c[i],&p[i]);
G[c[i]][cnr++]=i;
if (l[i]<=p)
cost[i]=cost[i-1]+1;
else cost[i]=cost[i-1];
}
for (int i=0;i<k;i++) {
int x=0;
for (int j=1;j<=cnr[i];j++) {
if (cost[G[i][j]]-cost[G[i][j-1]-1]>0) {
ans=ans+(j-x)*(cnr[i]+1-j);
x=j;
}
}
}
cout<<ans<<endl;
return 0;
}

###O(n)
#include <iostream>
#include <cstring>
using namespace std;

int n,k,p;
int c[51][200001], top[51];
long long total=0;

int main()
{
memset(top,-1,sizeof(top));
memset(c,0,sizeof(c));

ios::sync_with_stdio(false);
cin>>n>>k>>p;

int cnt=0;
bool P=false;
for (int i=0; i<n; i++)
{
int x,y;
cin>>x>>y;

int t=++top[x];
if (y<=p || P)
cnt++;
c[x][t]=cnt;

P = y<=p;
}

for (int color=0; color<k; color++)
{
int prev=c[color][0];
long long sum=0;

for (int i=0; i<=top[color]; i++)
{
if (c[color][i]-prev>0) sum=i;
total+=sum;
prev=c[color][i];
}
}

cout<<total<<endl;
return 0;
}

#include<cstdio>
using namespace std;
const int MAXN = 200000+10;

int f[MAXN], s[MAXN], ans[MAXN], num[MAXN];

int main()
{
int n, p, k, c, l, da=0;
scanf("%d%d%d", &n, &k, &p);
for(int i=1; i<=n; i++){
scanf("%d%d", &c, &l);
c %= k;
if(l <= p)
f[i] = f[i-1]+1;
else
f[i] = f[i-1];
if(s[c] == 0){
s[c] = i;
num[c]++;
continue;
}
if(f[i]-f[s[c]-1] > 0)
ans[i] = num[c];
else
ans[i] = ans[s[c]];
s[c] = i;
num[c]++;
}

for(int i=1; i<=n; i++)
da += ans[i];
printf("%d", da);
return 0;
}
模拟，O(n)。

O(nk)算法，稍加改动就是O(n)算法了（去掉i=0~k-1循环，为basic、num、front建立数组对应每种色调即可）
不过O(nk)跑得也不慢，懒得改了

#include<stdio.h>
int colors[200001]={0},price[200001]={0},sc[200001][2];//sc[j][1]表示到j为止情况数总和，sd[j][2]表示客栈j的情况数
int main( )
{

int n,k,p;
int i,j,flag=0,front=0,num=0,ans=0,basic=0;

scanf("%d %d %d",&n,&k,&p);

for(i=1;i<=n;i++)
scanf("%d %d",&colors[i],&price[i]);

for(i=0;i<=n;i++)
for(j=0;j<=1;j++)
sc[i][j]=0;

for(i=0;i<=k-1;i++)
{
front=0; //上一个客栈位置
num=0; //客栈数
basic=0; //上一个可被选择的客栈位置
flag=0; //记录两个客栈之间是否有符合消费的咖啡馆

for(j=1;j<=n;j++)
{
if(price[j]<=p) flag++;

if(colors[j]==i)

{
if(flag==0) {sc[j][0]=sc[front][0]+sc[front][1];sc[j][1]=sc[basic][1];}

else
{
basic=j;

sc[j][0]=sc[front][0]+sc[front][1];sc[j][1]=num;

if(price[j]>p) flag=0;
}

num++;
front=j;
}
}

ans=ans+sc[front][0]+sc[front][1];

}

printf("%d",ans);

return 0;
}

来个组合的
#include<cstdio>
using namespace std;
int n,k,p,ans=0,s[51],c[51],over[51];
int cb(int a)
{
return a*(a-1)/2;
}
int main()
{
scanf("%d%d%d",&n,&k,&p);
for(int i=0,a,b;i<n;i++)
{
scanf("%d%d",&a,&b);
s[a]++;
if(b<=p)
for(int i=0;i<k;i++)
c[i]+=cb(over[i]),over[i]=0;
else over[a]++;
}
for(int i=0;i<k;i++)
c[i]+=cb(over[i]);
for(int i=0;i<k;i++)
if(s[i]>1)
ans+=cb(s[i])-c[i];
printf("%d",ans);
return 0;
}

type
yu=longint;
var z:array[1..2,1..200000]of longint;
x:array[0..50,1..2]of longint;
sum:int64;

procedure tonglie;
var s,d,f:yu;
begin
for s:=0 to 50 do
if (x[s,1]>0)and(x[s,2]>0)
then begin
inc(sum,x[s,1]*x[s,2]);
x[s,2]:=0;
end;
end;

procedure main;
var n,k,p,a:longint;
begin
fillchar(z,sizeof(z),0);
fillchar(x,sizeof(x),0);
readln(n,k,p);
for a:=1 to n do
begin
readln(z[1,a],z[2,a]);
inc(x[z[1,a],1]);
end;
for a:=1 to n do
begin
if z[2,a]<=p
then tonglie;
dec(x[z[1,a],1]);
inc(x[z[1,a],2]);
if z[2,a]<=p
then tonglie;
end;
writeln(sum);
end;

begin
main;
end.
大概是O（50n)复杂度

program hotel;
var i,m,ans,t,n,k,p:longint;
lc,w,c:array[1..200000]of longint;
l,r:array[0..50]of longint;

procedure cal(x:longint);
var j:longint;
begin
for j:=0 to k-1 do
inc(ans,l[j]*r[j]);
inc(ans,l[c[lc[x]]]-1);
end;

begin
readln(n,k,p);
t:=0;
ans:=0;
for i:=1 to n do
begin
readln(c[i],w[i]);
if w[i]<=p then
begin
inc(t);
lc[t]:=i;
end;
end;
for i:=1 to n do
begin
if i<=lc[1] then
inc(l[c[i]])
else inc(r[c[i]]);
end;
cal(1);
for i:=2 to t do
begin
fillchar(l,sizeof(l),0);
for m:=lc[i-1]+1 to lc[i] do
begin
inc(l[c[m]]);
dec(r[c[m]]);
end;
cal(i);
end;
writeln(ans);
end.
//时间复杂度和空间复杂度均为O（n）的算法，不知道怎么想出来的。。。

var m,q:array[0..50]of longint;
n,k,p,i,a,b,s:longint;
begin
readln(n,k,p);
for i:=1 to n do begin
readln(a,b);
inc(s,m[a]);
if b<=p then fillchar(q,sizeof(q),0) else begin
dec(s,q[a]);
inc(q[a]);
end;
inc(m[a]);
end;
writeln(s);
end.
//Accepted, time = 201 ms, mem = 612 KiB, score = 100

var
n,k,p,c,m,ans,i,j:longint;
col,sum:array[0..50]of longint;
begin
readln(n,k,p);
for i:=1 to n do
begin
readln(c,m);
inc(col[c]);
if m<=p then
begin
inc(ans,col[c]-1);
for j:=0 to k-1 do
begin
inc(ans,sum[j]*col[j]);
sum[j]:=sum[j]+col[j];
col[j]:=0;
end;
end;
end;
for j:=0 to k-1 do
inc(ans,sum[j]*col[j]);
writeln(ans);
end.
O(n)算法，直接统计

var
n,k,p,i,j,g,h,s:longint;
no,yes,c:array[0..50]of longint;
begin
readln(n,k,p);
for i:=1 to n do
begin
readln(g,h);
s:=s+yes[g];
if h<=p then begin
s:=s+no[g];
fillchar(c,sizeof(c),0);
inc(yes[g]);
end
else begin
s:=s+no[g]-c[g];
inc(c[g]);
inc(no[g]);
end;
end;
writeln(s);
end.

O(n)打法：http://www.cnblogs.com/qq359084415/p/3374094.html

s[i]：到i为止最小消费<=p的客栈个数
a[i,j]：颜色为i的客栈序列
t[i]：颜色为i的客栈总数
然后枚举每一种颜色c
再枚举c里A选择的客栈ID
往右二分查找找到第一个客栈j满足s[j]-s[i-1]>0的j，对答案的贡献为t[c]-j+1
时间复杂度O(nlogn)

o(￣▽￣)o 1A！
Var n,k,p,i,j,ans:longint;
f:array[0..200000,0..50] of 0..200000;
pre,c,color:array[0..200000] of longint;
Begin
readln(n,k,p);
For i:=1 to n do
Begin
readln(color[i],c[i]);
For j:=0 to k-1 do f[i,j]:=f[i-1,j];
inc(f[i,color[i]]);
End;
For i:=1 to n do
If c[i]<=p then pre[i]:=i Else pre[i]:=pre[i-1];
For i:=1 to n do
If pre[i]<>i then ans:=ans+f[pre[i],color[i]]
Else ans:=ans+f[pre[i]-1,color[i]];
writeln(ans);
readln;
End.

用总的线段数去剪掉不包含可行咖啡厅的线段数目，复杂度O(kn)
思路貌似有点奇怪。。。
#include <cstring>
#include <cstdio>

using namespace std;

#define MAXN 200001
#define MAXK 50

int suff[MAXN];
int color[MAXN],cost[MAXN];

struct node {
node *next;
int rank;
};

node *head[MAXK];

int num[MAXK];

int n,k,c;

bool check(int l,int r){
if (suff[r]-suff[l-1]){
return true;
}
return false;
}

int main(){
scanf("%d%d%d",&n,&k,&c);
suff[0]=0;
for (int i=0;i<k;i++){
head[i]=NULL;
}
memset(num,0,sizeof(num));
for (int i=0;i++<n;){
scanf("%d%d",&color[i],&cost[i]);
node *p=new(node);
(*p).next=head[color[i]];
(*p).rank=i;
head[color[i]]=p;
num[color[i]]++;
suff[i]=suff[i-1];
if (cost[i]<=c){
suff[i]++;
}
}
int ans=0;
for (int i=0;i<k;i++){
if (num[i]>1){
int last=0;
ans+=((num[i]*(num[i]-1))/2);
node *p=head[i];
while ((p).next!=NULL){
if (!check(((*p).next).rank,(p).rank)){
last++;
} else {
if (last){
ans-=((last)(last+1)/2);
last=0;
}
}
p=(p).next;
}
if (last){
ans-=((last)(last+1)/2);
}
}
}
printf("%d\n",ans);
return 0;
}

#include

#include

#include

using namespace std;

int lowprice[200001],color[200001],f[200001]; // the sum of element before n+1

vector pairs[51]; // color the same

int main()

{

int n,k,p,l;

bool flag=false;

unsigned long long tot=0;

cin>>n>>k>>p;

for(int i=1;i

用 i 枚举 后一个人住的旅馆

i = 1 →n

pre 表示 在 i 旅店之前 有合适酒店可选的 最后一个旅店

rank 表示 当前旅店在同颜色旅店中的排位

last 表示 此颜色 在i之前 最后一个旅店

can 表示 在 i 旅店之前 离他最近 的酒店

num 表示 第二个人住 i 旅店时，第一个人可能的旅店个数。

can[i]=i(pcost[now])

pre[i]=last(last=can[i])

num[i]=rand[pre[i]]

答案就是 ∑num[i]

时间复杂度 O(n)

空间复杂度 O(n)

在线做 离线做 都可以

f[i] 表示以i结尾的方案的个数

back[i]表示同种颜色上一次出现的位置那么

num[i]表示 i之前的店当中 和i颜色相同的个数

答案则是sum(f[i])

转移方程为

f[i] = num[i](min[back[i],i]k)

令r[i]=min[back[i],i]

r数组可以在 o（k*n）的时间内预处理出来

总复杂度是O(k*n)

#include

#include

#include

#include

using namespace std;

int N, K, P;

int ans;

int a[200005];

int b[60];

void read_data()

{

    scanf("%d%d%d", &N, &K, &P);

    for(int i = 0; i < N; i++)

    {

        int cost, k;

        scanf("%d%d", &k, &cost);

        if (cost > P)

        {

            if (b[k] == 0)

            {

                a[k]++;

            }

            if (b[k] > 0)

            {

                ans += b[k];

                a[k] ++;

            }

        }

        if (cost

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int a[51]={0},f[51]={0};//a 按风格存储 f 实际可住的人
int n,k,p;
int main()
{
int i,j,x,y,ans;
cin>>n>>k>>p;
for(j=1;j<=n;j++)
{
scanf("%d%d",&x,&y);
a[x]++;
if(y<=p)
{
for(i=0;i<=k;i++)
{
f[i]=a[i];
}
}
ans+=f[x];
if(f[x]==a[x]) ans--;
}
cout<<ans;
return 0;
}