题解:
这道题有很多解法 如线段树 树状数组 st表
这里介绍一种$O(n)$解法
我们要统计所有情况 那不妨考虑第二个旅店 然后把所有符合要求的第一个旅店加进贡献 也就是说我们可以维护一个$pos$(在$i$个旅店之前的最近的满足最低消费小于$p$的旅店) 那么我们统计一下
在$pos$之前的颜色相同的旅店的个数加进答案 那么扫描一遍即可
所以现在的问题就是怎么在线性扫描时统计$pos$之前的颜色相同的旅店的个数
我们可以用三个数组$sum$和$pre$和$cnt$来实现
$sum$即统计$pos$之前的颜色相同的旅店的个数
$pre$是上一个颜色相同的旅店的位置
$cnt$是该颜色旅店的总数
那么我们在扫描时每发现上一个颜色相同的旅店在最近咖啡馆的前面 我们就可以令$sum=cnt$ 然后再顺应的维护一下
ans+=sum[c];
cnt[c]++;
pre[c]=i;
然后这是完整代码
AC代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=200500;
int a[maxn],w[maxn],pre[maxn],cnt[maxn],pos,sum[maxn];
int n,k,p,ans;
int main()
{
cin>>n>>k>>p;
for(int i=1;i<=n;i++) cin>>a[i]>>w[i];
for(int i=1;i<=n;i++)
{
int c=a[i];
if(w[i]<=p) pos=i;
if(pre[c]<=pos) sum[c]=cnt[c];
ans+=sum[c];
cnt[c]++;
pre[c]=i;
}
cout<<ans<<endl;
return 0;
}
发现#define int long long 即可
FFFFFF
被卡掉了呜呜