P1311 选择客栈

传送门

枚举右端点

可以发现左右端点中有一个合法的咖啡店就可以了

而且为了让合法的左端点尽量多

咖啡店要尽量靠右

所以可以记录目前最右边的合法咖啡店左边每种颜色的客栈的个数 cnt[ color ]

然后如果更右边有合法的咖啡店，就更新一波 cnt

累计所有右端点的情况

复杂度 O(nk)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=5e5+7;
int n,k,p;
int col[N],val[N],ans;
int cnt[57],sum[57];
int main()
{
    cin>>n>>k>>p;
    for(int i=1;i<=n;i++)
        scanf("%d%d",&col[i],&val[i]);
    for(int i=1;i<=n;i++)
    {
        sum[col[i]]++;//中间数组
        if(val[i]<=p)
            for(int j=0;j<k;j++) cnt[j]+=sum[j],sum[j]=0;//如果更右边有合法咖啡店就更新cnt
        ans+=val[i]<=p ? cnt[col[i]]-1 : cnt[col[i]];//注意左右端点不能重复
    }
    cout<<ans;
    return 0;
}

可以发现我们很多时间花在了更新cnt上

每次有咖啡店就把所有的cnt都更新了

但是其实每次我们只要更新当前颜色的cnt就可以了

所以可以记 las[ i ] 表示颜色 i 最右边出现的位置

pos 表示最右边合法的咖啡店的位置

如果 pos >= las[ lolor[r] ] 才更新cnt

复杂度 O(n)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=5e5+7;
int n,k,p;
int col[N],val[N],ans;
int cnt[57],sum[57],las[57];
int main()
{
    cin>>n>>k>>p;
    for(int i=1;i<=n;i++)
        scanf("%d%d",&col[i],&val[i]);
    int pos=0;
    for(int i=1;i<=n;i++)
    {
        if(val[i]<=p) pos=i;
        if(pos>=las[col[i]]) cnt[col[i]]+=sum[col[i]],sum[col[i]]=0;
        las[col[i]]=i;
        ans+=cnt[col[i]];
        sum[col[i]]++;
    }
    cout<<ans;
    return 0;
}