P1311 [NOIP2011 提高组] 选择客栈
P6032 选择客栈 加强版
只要\([l,r]\)区间之内存在一个\(i\)使得\(w[i]\le p\)，这个区间就是符合条件的。
所以我们遍历每一个元素\(i\)，根据贪心的思想我们维护\([1,i]\)区间内满足\(w[i]\le p\)的最大\(i\)，记为\(mp\)。
对于每个元素\(i\)，寻找\([1,mp]\)之间颜色和\(i\)相同的元素（不能是\(i\)本身）个数，累计答案即可。
可以用数组维护\([1,i]\)中各个颜色的位置，二分求解。时间复杂度\(O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define N 2000010
#define int long long
using namespace std;
int n,k,p,ans,mp;
vector<int> pos[N];
signed main(){
cin>>n>>k>>p;
for(int i=1;i<=n;i++){
int k,v;
cin>>k>>v;
if(v<=p) mp=i;
if(!pos[k].empty()) ans+=upper_bound(pos[k].begin(),pos[k].end(),mp)-pos[k].begin();
pos[k].emplace_back(i);
}
cout<<ans<<"\n";
return 0;
}
容易发现，对\(pos[k]\)进行二分，得到的答案一定是单调的，所以放弃二分，直接动态维护每个当前颜色的答案即可。
点击查看代码
#include<bits/stdc++.h>
#define N 2000010
#define int long long
using namespace std;
int n,k,p,ans,mp,res[N];
vector<int> pos[N];
signed main(){
memset(res,-1,sizeof res);
cin>>n>>k>>p;
for(int i=1;i<=n;i++){
int k,v;
cin>>k>>v;
if(v<=p) mp=i;
if(!pos[k].empty()){
while(res[k]+1<pos[k].size()&&pos[k][res[k]+1]<=mp) res[k]++;
ans+=res[k]+1;
}
pos[k].emplace_back(i);
}
cout<<ans<<"\n";
return 0;
}