noip2011选择客栈

暴力

题面

戳我

解析

一开始想了一个读入完再处理的暴力方法，比较麻烦。

其实可以考虑增量地看待这个问题。
如果当前客栈$val\leq p$，则前面所有同色客栈都可为$ans$作出$1$的贡献。
否则，就是上一个$val\leq p$的客栈出现前，前面所有同色客栈的数量。

所以我们对每种颜色统计两个量：

• 前面所有同色客栈的数量$num$
• 上一个$val\leq p$的客栈出现前，前面所有同色客栈的数量$res$

每当碰到一个$val\leq q$时，可以把所有$res$更新为$num$。
然后每次答案加上同色的$res$即可。

然而有个细节，在$val\leq q$时，当前点对答案没贡献，对$res$有贡献。
复杂度$O(nk)$。
也可以优化到$O(n)$。

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=55;
int n,k,p,num[N],las[N],now;
ll ans;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il int min(re int x,re int y){return x<y?x:y;}
int main()
{
  n=gi();k=gi();p=gi();
  fp(i,1,n)
    {
      re int col=gi(),val=gi();
      if(val<=p)
    fp(j,0,k-1) las[j]=num[j];
      ans+=las[col];
      if(val<=p) ++las[col];
      ++num[col];
    }
  printf("%lld\n",ans);
  return 0;
}