1012: [JSOI2008]最大数maxnumber

单点更新，区间求最大值的题；

可以使用树状数组和线段树；

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 2000009
#define ll long long
using namespace std;

int m,n=0;
ll ma[maxn],d[maxn];

void insert(int w,ll x)
{
    d[w]=x;
    while(w<=m)
    {
        ma[w]=max(ma[w],x);
        w+=w&-w;
    }
}

ll query(int l,int r)
{
    ll ret=d[r];
    while(l<=r)
    {
        int cnt=r&-r;
        ret=max(ret,d[r]);
        if(r-cnt+1>=l)
        {
            ret=max(ret,ma[r]);
            r-=r&-r;
        }
        else r--;
    }
    return ret;
}

char s[10];
ll x,mod;

int main()
{
    ll t=0;
    scanf("%d%lld",&m,&mod);
    for(int i=0;i<m;i++)
    {
        scanf("%s",s);
        if(s[0]=='A')
        {
            scanf("%d",&x);
            ++n;
            insert(n,(x+t)%mod);
        }
        else
        {
            scanf("%d",&x);
            t=query(n-x+1,n);
            printf("%lld
",t);
        }
    }
    return 0;
}