【BZOJ1012】【JSOI2008】最大数

好像又是个sb题

显然可以用线段树做

也可以用单调队列单调栈做

看了看hzwer的代码。。无法直视单调队列=暴力，随便卡。。

于是写了个单调队列的

#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;
}

#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;

}