题解 P1311 【选择客栈】
YoungNeal
2018-05-23 23:02:52
题解在博客[食用](https://www.cnblogs.com/YoungNeal/p/9080195.html)效果更佳哦~
## Solution
~~我竟然做了一个小时我好菜啊~~
跟楼下dalao们不一样这里有种比较巧的题解。
---
### 构思部分
观察到如果区间 $[l,r]$ 可行的话，那么一定存在 $i\in [l,r] $ 使得 $val[i]\leq p$。
也就是说，对于这个区间的右端点 $r$，如果知道了它左边有一个 $i$ 满足 $val[i]\leq p$，那么这个 $i$ 左边的点都可以对答案有贡献。
稍微贪心的想，我们想找的这个 $i$ 一定是离 $r$ 最近的点，否则，一定可以找到离 $r$ 更近且满足要求的点，使得答案不会变差。
那么问题就转化为了对于每一个点 $p$，找出它左边第一个满足 $val[i]\leq p$ 的点 $i$，然后所有与 $p$ 颜色相同并且在 $i$ 左边的点都会与 $p$ 对答案产生 $1$ 的贡献。
---
### 实现部分
所以，我们只需要对每个颜色开一个数组 $col[i][j]=k$ 表示所有颜色为 $i$ 的点中从左向右第 $j$ 个是点 $k$。
另外，每个点记录它左边且最接近它的一个点 $i$ 使得 $val[i]\leq p$ 记为 $last$ 数组(注意这里 $last[i]$ 是可以等于 $i$ 的)。
然后枚举每个点 $i$，首先在 $col[idx[i]]$ 中二分出相同颜色这个点前面有 $b$ 个点，同时根据 $last[i]$ 二分出相同颜色在 $last[i]$ 前面有 $c$ 个点。
注意，这时候要分情况讨论了：
1. 如果 $i=last[i]$ ，也就是说无论左端点在哪，这两个人都可以去右端点吃饭，所以直接 $ans+=b$ 即可。
2. $i!=last[i]$ 但是 $idx[i]=idx[last[i]]$，也就是说，这个点前面满足要求的最近的点跟它颜色一样。注意到我们的 $c$ 是 $last[i]$ **前面** 有 $c$ 个点，如果颜色相同的话，应该算上 $last[i]$ ，所以 $ans+=c+1$。
3. 最后一种情况，即 $i!=last[i]\;and\;idx[i]!=idx[last[i]]$ ，这种情况是最简单的， $ans+=c$ 就OK了。
时间复杂度 $\mathcal{O(nlogn)}$。
## Code
```cpp
#include<cstdio>
#include<algorithm>
#define N 200005
#define ll long long
#define min(A,B) ((A)<(B)?(A):(B))
ll ans;
int n,k,p;
int qzh[N];
int val[N];
int idx[N];
int last[N];
int col[55][N];
signed main(){
scanf("%d%d%d",&n,&k,&p);
qzh[0]=p+1;
for(int i=1;i<=n;i++){
int a;
scanf("%d%d",&a,&val[i]);
idx[i]=a;
col[a][++col[a][0]]=i;
qzh[i]=min(qzh[i-1],val[i]);
last[i]=(val[i]<=p?i:last[i-1]);
//printf("i=%d,qzh=%d,last=%d\n",i,qzh[i],last[i]);
}
for(int i=1;i<=n;i++){
if(qzh[i]>p) continue;
int b=std::lower_bound(col[idx[i]]+1,col[idx[i]]+1+col[idx[i]][0],i)-col[idx[i]];
int c=std::lower_bound(col[idx[i]]+1,col[idx[i]]+1+col[idx[i]][0],last[i])-col[idx[i]]-1; //因为要求的是**前面**有多少，所以要减一
if(last[i]==i) ans+=(ll)b-1;
else if(idx[last[i]]!=idx[i]) ans+=(ll)c;
else ans+=(ll)c+1;
//printf("i=%d,b=%d,c=%d,ans=%lld\n",i,b,c,ans);
}
printf("%lld\n",ans);
return 0;
}
```