题解 P1198 【[JSOI2008]最大数】

Ash1mar · 2017-05-03 20:02:36 · 题解

单调队列+二分查找lower_bound。。。

#include<iostream>  
#include<cstring>  
#include<cstdio>   
using namespace std;  
int M,D,t=0; 
int size;  
int a[200500];  
int num[200500];  
int main()  
{  
    int Ln,len=0;  
    char QA[5];  
    scanf("%d%d", &M, &D);  
    while(M--)  
    {  
        scanf("%s %d", QA, &Ln); 
        if(QA[0] == 'A')//查询操作 
        {  
            Ln=(Ln+t)%D;  
            num[++len]=Ln;//每次加入一个Ln,num数组长度++ 
            while(size&&num[a[size]]<=Ln) 
                size--;//单调栈操作 
            a[++size]=len;  
        }  
        else //插入操作 
        {  
            int pos=lower_bound(a+1,a+size+1,len-Ln+1)-a; //二分查找 
            t=num[a[pos]]; 
            cout<<t<<endl;  
        }  
    }  
    return 0;  
}