选择客栈

洛咕

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

分析:本题方法很多,时间复杂度从\(O(nk)\)到\(O(nlog_n)\)到\(O(n)\)都有.因为\(O(nk)\)实在是太水就不讲了(主要是懒得写代码).

先看\(nlog_n\)的,考虑枚举每个位置\(i\)作为左端点产生的贡献,分类讨论:如果\(cost[i]<=p\),那么我们只要知道i位置右边有多少个与\(color[i]\)色调相同的客栈即可.如果\(cost[i]>p\),那么我们先要找到右边第一个\(cost[j]<=p\)的客栈\(j\),然后再在\(j\)的右边找有多少个与\(color[i]\)色调相同的客栈.

现在的时间复杂度主要是如何找?我们记录一个\(pos\)数组,\(pos[i]\)表示从左往右第i个消费小于等于\(p\)的客栈的位置,再开\(k\)个\(vector\),\(q[i][j]\)记录颜色\(i\)第j次出现的位置.这样我们上面的两类查找都可以通过二分答案实现.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=2000005;
const int M=10005;
int n,m,k,tot;ll ans;
int p[N],h[N],pos[N];
vector<int>q[M];
int main(){
    n=read();k=read();m=read();
    for(int i=1;i<=n;++i){
        p[i]=read();h[i]=read();
        q[p[i]].push_back(i);
        if(h[i]<=m)pos[++tot]=i;
    }
    for(int i=1;i<=n;++i){
        if(h[i]<=m){
            int l=0,r=q[p[i]].size()-1,mid,cnt=-1;
            while(l<=r){
                mid=(l+r)>>1;
                if(q[p[i]][mid]>=i){
                    cnt=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            if(cnt==-1)continue;
            ans+=q[p[i]].size()-(cnt+1);
        }
        else{
            int l=1,r=tot,mid,cnt=-1;
            while(l<=r){
                mid=(l+r)>>1;
                if(pos[mid]>=i){
                    cnt=pos[mid];
                    r=mid-1;
                }
                else l=mid+1;
            }
            if(cnt==-1)continue;
            l=0,r=q[p[i]].size()-1;int midd,cntt=-1;
            while(l<=r){
                midd=(l+r)>>1;
                if(q[p[i]][midd]>=cnt){
                    cntt=midd;
                    r=midd-1;
                }
                else l=midd+1;
            }
            if(cntt==-1)continue;
            ans=ans+q[p[i]].size()-cntt;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

我们上面是考虑枚举i作为左端点,结果要去"找"右边我们想要的一些东西.那么我们可以枚举\(i\)作为右端点,这样左边的信息我们在之前扫描的时候就统计出来.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=2000005;
ll ans;
int a[N],b[N],sum[N];
int main(){
    int n=read(),k=read(),p=read();
    for(int i=1;i<=n;++i)a[i]=read()+1,b[i]=read();
    int pos=0;
    for(int i=1;i<=n;++i){
        if(b[i]<=p){
            for(int j=pos+1;j<=i;++j)++sum[a[j]];
            pos=i;ans+=sum[a[i]]-1;
        }
        else ans+=sum[a[i]];
    }
    printf("%lld\n",ans);
    return 0;
}