题解 P1198 【[JSOI2008]最大数】

hibiki · 2017-11-08 21:13:43 · 题解

思路：用一个单调栈存放数据，对于每一个最大值，

记录它是从开头第x个数到末尾(即末尾第L-X+1开始)的最大值

对于每一个新加入的数，将其入栈，并标记它为第L个（即当前最大长度）的最大值

然后不断与前面的数比较，只要大于前面的数就将前面的数出栈，

并将x--

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#define MAX 200000
using namespace std;
struct node{
    int va,x;
};
node stack[MAX+10];
int found(int x,int y,int k){
    int m=(x+y)/2;
    if (x>=y) return x ;else{
        if (stack[m].x==k) return m;
            else if (stack[m].x>k) return found(x,m-1,k);
            else return (found(m+1,y,k));
    }
}
int m,d;
int top;
char op[1];
int t=0;
int tt;
int cnt=0;
int main(){
    //cin>>m>>d;
    scanf("%d%d",&m,&d);
    for (int i=1;i<=m;i++){
        //cin>>op;
        scanf("%s%d",&op,&tt);
        if (op[0]=='A'){
            //cin>>tt;
            top++;
            cnt++;
            stack[top].va=(t+tt)%d;
            stack[top].x=cnt;
            while((stack[top].va>stack[top-1].va)&&top>1){
                stack[top].x=stack[top-1].x;
                swap(stack[top],stack[top-1]);
                top--;
            }
        } else {
            //cin>>tt;
            int pos=found(1,top,cnt-tt+1);
            //cout<<stack[stack[pos].x<=cnt-tt+1?pos:pos-1].va<<endl;
            printf("%d\n",stack[stack[pos].x<=cnt-tt+1?pos:pos-1].va);
            t=stack[stack[pos].x<=cnt-tt+1?pos:pos-1].va; 
        }
    }
    return 0;
}