洛谷 1311 选择客栈——思路

题目：https://www.luogu.org/problemnew/show/P1311

记录一下每个位置往后的各种颜色个数，再记录每个位置往后第一个可作为咖啡店的位置在哪即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+5,M=55;
int n,k,p,col[N],w[N],ans,g[N],ct[N][M];
int rdn()
{
  int ret=0;bool fx=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}
  while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
  return fx?ret:-ret;
}
int main()
{
  n=rdn(); k=rdn(); p=rdn();
  for(int i=1;i<=n;i++)
    col[i]=rdn(),w[i]=rdn();
  int p0=n+1;
  for(int i=n;i;i--)
    {
      if(w[i]<=p)p0=i;  g[i]=p0;
      for(int j=0;j<k;j++)ct[i][j]=ct[i+1][j];
      ct[i][col[i]]++;
    }
  for(int i=1;i<=n;i++)
      ans+=ct[g[i]+(g[i]==i)][col[i]];
  printf("%d
",ans);
  return 0;
}