P1311 选择客栈_牛客博客

开始想用分治，找到中间的一个小于 $p$ 的客栈，然后用到它的两边的客栈的贡献就可以用前缀和轻易算出。然后递归处理左右。

后来发现没有这个必要，从左向右扫一遍就好了。

每次找到当前第一个小于 $p$ 的客栈，这样它前面的客栈与他自己的贡献便可以处理。

预处理 $O(n*k)$ ,主过程 $O(n)$ .

#include<iostream>
#include<cstdio>
#define maxn 200010
using namespace std;

int f[maxn][60],v[maxn],col[maxn];
int main(){
    int n,k,p;scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;i++)scanf("%d%d",&col[i],&v[i]);
    for(int k=0;k<=50;k++)
    for(int i=1;i<=n;i++)
    f[i][k]=f[i-1][k]+(col[i]==k);
    //for(int k=0;k<=1;k++)
    //for(int i=1;i<=n;i++)cout<<k<<' '<<i<<' '<<f[i][k]<<endl;
    int Ans=0;
    for(int i=1,l=0,r=0;i<=n;i++){//cout<<i<<endl;
        if(v[i]>p){
            if(l==0&&r==0)l=r=i;
            else r=i;
            //cout<<l<<' '<<r<<endl;
        }
        if(v[i]<=p){
            if(l&&r)
            for(int j=l;j<=r;j++)
            Ans+=f[n][col[j]]-f[r][col[j]];
            Ans+=f[n][col[i]]-f[i][col[i]];
            l=r=0;
            //cout<<Ans<<endl;
        }
    }
    cout<<Ans;
    return 0;
}