好像又是个sb题
显然可以用线段树做
也可以用单调队列单调栈做
看了看hzwer的代码。。无法直视 单调队列=暴力,随便卡。。
于是写了个单调队列的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=200001; int tot,s[MAXN],k[MAXN]; int main(){ int m=gi(),D=gi(),t=0; char q[1]; int l=1,r=0; while(m--){ scanf("%s",q); if(q[0]=='A'){ k[++tot]=(gi()+t)%D; while(l<=r&&k[s[r]]<k[tot])r--; s[++r]=tot; }else{ int rk=lower_bound(s+l,s+r+1,tot-gi()+1)-s; printf("%d\n",t=k[s[rk]]); } } return 0; } |