题解：P1311 [NOIP2011 提高组] 选择客栈

题目传送门

简化题意

给出 $n$，$k$，$p$。

共有 $n$ 个数字，编号从 $1$ 到 $n$，并对于每个数给出对应的 $a$ 与 $b$。

然后，要求在 $1$ 到 $n$ 中，找出 $l$，$m$，$r$，使得：

• $l \le m \le r$。
• $a _ l = a _ r$。
• $b _ m < p$。

求符合条件的 $l$，$m$，$r$ 的方案数的个数。

大致思路

暴力解法需要三重循环，两个客栈与咖啡厅各需要一层。显然是会超时。我们可以进行如下优化：

每输入一组数，就从当前下标 $i$ 向前遍历。如果找到一个咖啡厅价格符合要求，那么在它之前的所有相同色调的客栈都符合要求。依次递推。

换言之：

• 对于整个数组，在输入时把每一个数作为 $r$。
• 对于每一个 $r$，都向前寻找所有符合条件（即 $b _ m < p$）的 $m$。
• 对于每一个 $m$，都向前寻找所有符合条件（即 $a _ l = a _ r$）的 $l$。

然后将总数相加。这样我们就把三重循环中的两层都优化掉了。其它具体内容放在代码里了。

代码实现

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
ll n,k,p,x,y,d,ans,a[200010],b[200010],c[200010];
int main(){
	cin>>n>>k>>p;
	for(ll i=1;i<=n;i++){
		cin>>x>>y;
		if(y<=p) d=i;//更新
		if(d>=a[x])//如果所有相同色调的都在后面
			b[x]=c[x];//那么所有前面的都符合 
		a[x]=i;//否则根据上一次更新
		ans+=b[x];//方案数增加
		c[x]++;
	}cout<<ans;
	return 0;
}