P1311 选择客栈
题目描述
丽江河边有 \(n\) 家很有特色的客栈，客栈按照其位置顺序从 \(1\) 到 \(n\) 编号。每家客栈都按照某一种色调进行装饰（总共 \(k\) 种，用整数 \(0\) ~ \(k-1\) 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 \(p\) 。
他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 \(p\) 元的咖啡店小聚。
输入输出格式
输入格式：
共\(n+1\) 行。
第一行三个整数 \(n ,k ,p\) ，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；
接下来的 \(n\) 行，第 \(i+1\) 行两个整数，之间用一个空格隔开，分别表示 \(i\) 号客栈的装饰色调和 \(i\) 号客栈的咖啡店的最低消费。
输出格式：
一个整数，表示可选的住宿方案的总数。
数据范围
对于 \(30\%\) 的数据，有 \(n ≤100\) ；
对于 \(50\%\) 的数据，有 \(n ≤1,000\) ；
对于 \(100\%\) 的数据，有 \(2 ≤n ≤200,000,0<k ≤50,0≤p ≤100\), \(0≤\) 最低消费 \(≤100\) 。
这是一道很神奇的题目，因为我在短短20分钟错了四次（考场必拍啊）
做完瞅了一下题解，发现做法非常之多。
我的想法是，先用vector把每种颜色搞出来，然后前缀和统计某个区间是否有咖啡
对每种颜色，我们考虑每一个相邻两点区间，这个区间对答案的贡献即是区间左边的点数 \(\times\) 区间右边的点数
好的，它是错的。因为重复统计了。
我们考虑删去重复统计的，稍稍模拟一下即可发现，前一个合法的区间的左端点及其左边的点不需要统计，好了，维护一个指针就行了
Code:
#include <cstdio>
#include <vector>
#define ll long long
using namespace std;
const int N=2000010;
const int M=10010;
ll ans;
int n,k,p,f[N];
vector <int> ctsc[M];
int main()
{
scanf("%d%d%d",&n,&k,&p);
for(int color,cost,i=1;i<=n;i++)
{
scanf("%d%d",&color,&cost);
ctsc[color].push_back(i);
f[i]=f[i-1]+(cost<=p);
}
for(int i=0;i<k;i++)
for(int s=0,j=1;j<ctsc[i].size();j++)
if(f[ctsc[i][j]]-f[ctsc[i][j-1]-1])
{
ans+=(ll)(j-s)*(ll)(ctsc[i].size()-j);
s=j;
}
printf("%lld\n",ans);
return 0;
}
2018.8.5