题解 P1198 【[JSOI2008]最大数】

· · 题解

WA点提示：很多人说最后两个点要用C++的int才能过= =我只是个搬运工

[delete]反正我3次爆蛋之后就直接A了[/delete]

** 因为数组不定长我还真没看出来用线段树怎么玩。。

我选择 [color=red]单调栈[/color]

好像这一类题单调栈都可以搞定

筛选：假如两x,y x先进栈，y后进栈，那么如果x可以选择的话，y也一定可以选择。

那么如果y>x的话 ，x就没用了，就可以弹出了

于是剩下的就是一个单调递减的单调栈

因为查找是查找后L个数，于是我们要找一个栈中尽量靠左的数，使得它在最后L个进栈的数中，我们仅靠数字并不知道它是否符合要求，

所以这要求我们每个数给一个进栈时间点id，再设一个一共进了多少个数（不是栈中数的个数）变量id_cnt，每次进栈操作时++，这样的话，能选择的数的id>=id_cnt-L+1

(这样搞主要是因为有退栈现象发生)

然后对于每次Q操作 在栈中二分查找

（建议画个图理解起来方便一些，我当时就没有草稿本所以特别烧脑子）

** 我写的丑勿喷


#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=200000+10;
struct Node{
    int id,x;
    Node(){}
    Node(int id,int x):id(id),x(x){}
};

Node stack[maxn];
int MOD,Q,x,p=1;

#define mid ((l+r)>>1)
int search(const int &k,int l,int r)
{
    int ret=0;
    while(l<=r)
    {
        if(stack[mid].id>=k) ret=stack[mid].x,r=mid-1;
        else l=mid+1;
    }
    return ret;
}

char ins[5];
int main()
{
    cin>>Q>>MOD;
    int last_ans=0,id_cnt=0;
    while(Q--)
    {
        scanf("%s%d",ins,&x);
        if(ins[0]=='A')
        {
            x=(x+last_ans)%MOD;
            if(p==1){stack[p++]=Node(++id_cnt,x);continue;}
            else
            {
                while(p!=1&&x>stack[p-1].x) p--;
                stack[p++]=Node(++id_cnt,x);
            }
        }
        else
        {
            last_ans=search(id_cnt-x+1,1,p);
            printf("%d\n",last_ans);
        }
    }
    return 0;
}