今天晚上ygp讲了一下单调队列，所以就写了这道题。
建立一个单调队列(升序)，然后维持该升序后利用二分查找符合标准的值作为ans。
据说线段树和单调栈也可以搞这题，那我也得到以后再写了(我现在不会线段树啊QAQ)
单调队列：
#include<cstdio>
int n,d,rear=1,lastans=0,counted=0;
char x;
struct Node{
int i,v;
}q[200005];
int main(){
freopen("1012.in","r",stdin);
freopen("1012.out","w",stdout);
scanf("%d %d",&n,&d);
while(n--){
int w;
scanf("%s %d",&x,&w);
if(x=='Q'){
int l=1,r=rear,mid,ans=-1;
while(l<=r){
mid=(l+r)/2;
if(counted-q[mid].i+1>w){
l=mid+1;
}
else {
ans=mid;
r=mid-1;
}
}
printf("%d\n",q[ans].v);
lastans=q[ans].v;
}
else {
w=(w+lastans)%d;
while(rear>0 && q[rear].v<w)rear--;
q[++rear].i=++counted;
q[rear].v=w;
}
}
return 0;
}
评论 (0)
