选择客栈

https://loj.ac/problem/2597

题目描述

  有\(n\)家客栈，每家客栈都设有咖啡店，最低消费为\(p_i\)；每家客栈都有一种颜色。求有多少组客栈满足两个客栈颜色相同且中间有一个客栈的咖啡店的最高消费不超过p。

思路

  我们考虑直接扫一遍所有客栈，事实上有意义的只是上一个同种颜色的客栈所处的位置和之前相同颜色的个数。假设我们现在在\(i\)位置，相当于以i作为右端点，显然我们只要得到满足价格小于等于\(p\)位置中最大的那个就可以了，每次维护一个\(now\)来更新。在考虑维护在\(now\)之前的相同颜色的个数，我们需要用两个数组来维护，\(cnt[col]\)表示到\(i\)为止的颜色为\(col\)的总数量，\(sum[col]\)表示在\(now\)之前的颜色为\(col\)的总数量，维护一下就行了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+10;

int read()
{
    int res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
    return res*w;
}
void write(ll x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
void writeln(ll x)
{
    write(x);
    putchar('\n');
}

int last[N],sum[N],cnt[N];
int main()
{
    int n,k,p,now;
    ll ans=0;
    n=read();k=read();p=read();
    for(int i=1;i<=n;++i)
    {
        int col=read(),cost=read();
        if(cost<=p)
            now=i;
        if(now>=last[col])
            sum[col]=cnt[col];
        last[col]=i;
        ans+=sum[col];
        ++cnt[col];
    }
    writeln(ans);
}