题解 P1311 【选择客栈】
Zhang_RQ
2017-10-28 11:11:47
翻了一下题解，竟然没有人发过单调指针的做法。~~(所以我就来骗题解了）~~
看题，我们可以发现一个显然的性质，即当最左边的客栈向右移动时，最右边的客栈时单调向右的，并且右端点往右的客栈也符合要求。(因为只要左侧有一个满足的，右边的自然可以选)
所以很自然的想到单调指针。
我们不妨将每种颜色的宾馆分别放到 vector 中。
然后在每个 vector 中枚举左端点，维护一个单调指针来确定右端点 (vector中的下标)。
我们接下来就要快速判断一段区间是否合法，我们开一个first数组，表示从i点开始最近的满足条件的位置(不考虑颜色)。
易得到转移 $$first[i]=i(p[i]<=P)$$ 否则 $$first[i]=first[i+1]$$ ，特别的，注意 $$first[n+1]=n+1$$ 代表若 $$p[n]>P$$ ,则 $$first[n]=n+1$$ ,即不合法。
每个端点都对答案有 $$size()-r$$ 的贡献。
接下来上代码
```cpp
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
vector<int> hotel[60];
int p[200100],col[200100],first[200100];
int n,P,k;
ll ans=0;
void get_first()
{
first[n+1]=n+1;
for(int i=n;i>=1;i--)
{
if(p[i]<=P) first[i]=i;
else first[i]=first[i+1];
}
}
int main()
{
scanf("%d%d%d",&n,&k,&P);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&col[i],&p[i]);
hotel[col[i]].push_back(i);
}
get_first();
for(int i=0;i<k;i++)
{
int r=0;
for(int j=0;j<hotel[i].size();j++)
{
r=max(r,j+1);
while(hotel[i][r]<first[hotel[i][j]]&&r<hotel[i].size())
r++;
ans+=hotel[i].size()-r;
}
}
printf("%lld\n",ans);
}
```