题目描述

丽江河边有n家很有特色的客栈，客栈按照其位置顺序从1到n编号。每家客栈都按照某一种色调进行装饰（总共k种，用整数 0~k-1表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过p。
他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。

输入描述:

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

输出描述:

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

示例1

输入
5 2 3
0 5
1 3
0 2
1 4
1 5
输出
3
说明

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

备注

对于30%的数据，有 n ≤ 100；
对于50%的数据，有 n ≤ 1,000；
对于100%的数据，有 2 ≤ n ≤ 200,000，0 < k ≤ 50，0 ≤ p ≤ 100，0 ≤ 最低消费 ≤ 100。

解答

看到没人用ST表，我就来水一发~

题目大意：选两个颜色相同的点，要求两点之间的最小值不能大于 p ，求有多少个这样的点对。

看到题目，首先想到暴力：枚举点对，暴力判断两点之间最小值，最坏情况 。 可一看数据范围, ，这程序能T到天上去......

想想怎么优化这个程序。首先，看到区间最小值，还不带修改操作，自然而然的想到ST表这个查询 的优秀算法。这样，程序已经优化到 了，但是大数据还是过不了，还能怎么优化呢？ 我们来观察一下我们要查询的区间：

我们惊喜的发现，只要第 j 号点满足 这个条件，那么之前所有的点都可以对答案做出1的贡献！所以，这个区间是单调的，我们可以二分找到这个点，并且记录数组 num[i][j]num[i][j] 表示第i号点之前（包括自己）有多少个颜色为 j 的点，二分答案后直接累加相应的 num 数组即可。这样，时间复杂度为 ，可以通过了。

最后亮出代码~~~ 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<climits>
using namespace std;
int num[200005][55];
int st[200005][55];
int color[200005];
int n,k,p;
long long sum;
int query(int x,int y)
{
    if(y<x)
        swap(x,y);
    int l=log2(y-x+1);
    return min(st[x][l],st[y-(1<<l)+1][l]);
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int main()
{
    scanf("%d%d%d",&n,&k,&p);
    int i,j,l,r;
    memset(st,63,sizeof(st));
    for(i=1;i<=n;i++)
    {
        color[i]=read();
        num[i][color[i]]++;
        st[i][0]=read();
    }
    for(i=1;i<=n;i++)
        for(j=0;j<=50;j++)
            num[i][j]+=num[i-1][j];
    for(j=1;j<=log2(n)+1;j++)
        for(i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    for(i=1;i<=n;i++)
    {
        if(st[i][0]<=p)//特判，若当前点满足条件，直接跳出
        {
            sum+=num[i-1][color[i]];
            continue;
        }
        if(num[i-1][color[i]]==0)//特判，若之前没有相同颜色的点，则直接跳出
            continue;
        l=1;
        r=i-1;
        int ans=0;
        int mid=(l+r)>>1;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(query(mid,i-1)<=p)
                l=mid+1,ans=max(ans,mid);
            else
                r=mid-1;
        }
        if(ans==INT_MAX)
            continue;
        sum+=num[ans][color[i]];
    }
    cout<<sum;
    return 0;
}


来源：handsome·wjc