Luogu P1198 [JSOI2008]最大数

　　我会用高级（？？？）的单调栈来打这道题吗？

　　线段树即可水过。

　　假设这个数列刚开始所有数都是0，然后我们每次只要进行一个点的修改和区间求和即可。

　　这不就是 线段树大法。

　　只要用一个len记录一下当前数列长度即可

　　（刚开始智障把求最大数打成求和了，还过样例了）

　　CODE

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
const int N=200005,INF=2147483647;
LL tree[N*4+10],n,d,x,last,len;
char ch;
inline void read(LL &x)
{
    x=0; char ch=getchar(); int flag=1;
    while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=getchar(); }
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    x*=flag;
}
inline void write(LL x)
{
    if (x<0) putchar('-'),x=-x;
    if (x/10) write(x/10);
    putchar(x%10+'0');
}
inline LL max(LL a,LL b) { return a>b?a:b; }
inline void updata(LL root,LL l,LL r,LL id,LL add)
{
    if (l==r)
    {
        if (l==id)
        {
            tree[root]=add;
            return;
        }
    }
    LL mid=l+r>>1;
    if (id<=mid) updata(root*2,l,mid,id,add); else updata(root*2+1,mid+1,r,id,add);
    tree[root]=max(tree[root*2],tree[root*2+1]);
}
inline LL query(LL root,LL l,LL r,LL ql,LL qr)
{
    if (l>=ql&&r<=qr) return tree[root];
    LL res=-INF,mid=l+r>>1;
    if (ql<=mid) res=max(res,query(root*2,l,mid,ql,qr)); 
    if (mid<qr) res=max(res,query(root*2+1,mid+1,r,ql,qr));
    return res;
}
int main()
{
    read(n); read(d);
    while (n--)
    {
        cin>>ch;
        if (ch=='A') 
        { 
            read(x); 
            x+=last;
            x%=d; 
            updata(1,1,N,++len,x); 
        } else 
        { 
            read(x);
            last=query(1,1,N,len-x+1,len);
            write(last);
            putchar('
');
        }
    }
    return 0;
}