洛谷P1311

$ O(n) $ 做法

首先预处理一个数组res[i],表示第 $ 1 $ 到 $ i $ 的客栈中编号最大且满足最低消费小于等于q的客栈编号;

维护一个前缀和数组ans[i][j],i为颜色,j为编号, $ O(1) $ 求出 1~j 中有多少个颜色为i的客栈;

枚举较大的客栈的编号i,1~res[i] 是不考虑颜色因素所能选的区间,ans[i][res[i]]即是右端点为i时的答案.

注意当res[i]=i时,因为一个客栈不能选两次,因此答案要减一.

累加即可.

#include<cstdio>
#include<cstring>
using namespace std;
int n,k,p;
int a[200005],b,res[200005],ans[55][200005];
long long ret=0;
int main(){
	memset(res,-1,sizeof res);
	scanf("%d%d%d",&n,&k,&p);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b);
		if(b<=p){
			res[i]=i;
		}
		else{
			res[i]=res[i-1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int type=0;type<=k;type++){
			ans[type][i]=ans[type][i-1];
			if(a[i]==type){
				ans[type][i]++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(i==res[i]){
			ret--;
		}
		ret+=ans[a[i]][res[i]];
	}
	printf("%lld",ret);
	return 0;
}