选择客栈

丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0∼k−1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。

两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p。

他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。

输入

• 第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；
• 接下来的 n 行，第 i+1 行两个整数，之间用一个空格隔开，分别表示 i 号客栈的装饰色调和 i 号客栈的咖啡店的最低消费。

输出

• 输出只有一行，一个整数，表示可选的住宿方案的总数。

样例一

input

5 2 3
0 5
1 3
0 2
1 4
1 5

output

3

explanation

客栈编号	①	②	③	④	⑤
色调	0	1	0	1	1
最低消费	5	3	2	4	5

2 人要住同样色调的客栈，所有可选的住宿方案包括：

住客栈 ①③，②④，②⑤，④⑤，但是若选择住 ④、⑤ 号客栈的话，④、⑤ 号客栈之间的咖啡店的最低消费是 4，而两人能承受的最低消费是 3 元，所以不满足要求。因此只有前 3 种方案可选。

限制与约定

• 对于 30% 的数据，有 n≤100
  
• 对于 50% 的数据，有 n≤1000
  
• 对于 100% 的数据，有 2≤n≤200000，k≤50，0≤p≤100，0<=最大消费<=100
  

时间限制：$\mathrm{1s}$

空间限制：$\mathrm{128MB}$

---

 思路：

$\mathrm{60分线段树优化（跟没优化一样）}$

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MX=200001;
struct Tree {
    int l,r,m;
}tree[MX*4];
int n,k,p,pri[MX];
long long ans;
vector<int> stk[51];

void build(int l,int r,int k)
{
    tree[k].l=l,tree[k].r=r;
    if(l==r) {
        tree[k].m=pri[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,k*2);
    build(mid+1,r,k*2+1);
    tree[k].m=min(tree[k*2].m,tree[k*2+1].m);
}

int ask(int l,int r,int k,int lm,int rm)
{
    if(tree[k].l>=l && tree[k].r<=r)
        return tree[k].m;
    
    int mid=(tree[k].l+tree[k].r)>>1;
    if(l<=mid) lm=ask(l,r,k*2,lm,rm);
    if(r>mid) rm=ask(l,r,k*2+1,lm,rm);
    return min(lm,rm);
}

int main()
{
//    freopen("hotel.in","r",stdin),freopen("hotel.out","w",stdout);
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;++i) 
    {
        int cor;
        scanf("%d%d",&cor,&pri[i]);
        stk[cor].push_back(i);
    }
    build(1,n,1);
    for(int i=0;i<k;++i) 
    {
        for(int j=0;j<stk[i].size();++j)
        {
            int l=stk[i][j];
            for(int k=j+1;k<stk[i].size();++k)
            {
                int r=stk[i][k];
                if(ask(l,r,1,999,999)<=p) ans++;
            }
        }
    }
    printf("%lld",ans);
    return 0;
}
/*
10 2 50
1 30    
1 89    
0 32    
1 50    
0 40    
1 78    
1 89    
0 30    
0 22     
1 98    
*/

 后四个点仍然会T，只是一个优化的暴力做法

正解其实是一个 O(n) 的递推

递推非常奇妙，有了递推的思维，只需短短几行就可做出正解

#include<stdio.h>
const int MX=200001;
int cnt[MX],last[MX],sum[MX],n,k,p,now;

int main()
{
    int ans=0;
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;++i)
    {
        int cor,pri;
        scanf("%d%d",&cor,&pri);
        if(pri<=p)
            now=i;
        if(now>=last[cor])
            sum[cor]=cnt[cor];
        last[cor]=i;
        ans+=sum[cor];
        cnt[cor]++;
    }
    printf("%d",ans);
    return 0;
}