今天晚上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; }