BZOJ 1012[JSOI 2008]最大数maxnumber問題解&コード

テーマは簡潔明瞭==詳しくは言わないが、線分樹最大値裸題
1つの数列を維持するには、1、クエリー操作の2つの操作が必要です.構文:Q L機能:現在の数列の末尾のL個の数の最大数を問合せ、その数の値を出力します.制限:Lは現在の数列の長さを超えません.2、挿入操作.構文:A n機能:nにtを加え、ここでtは最近のクエリ操作の答え(クエリ操作がまだ実行されていない場合はt=0)であり、得られた結果を一定の定数Dに対して型を取り、数列の末尾に挿入する.制限:nは非負の整数であり、長い範囲内である.注:初期時の数列は空で、数は1つもありません.**注意long long
この線分ツリーがすべて挿入操作=であると仮定すると、線分ツリーは最大m個の要素しかないので、問題を1に簡略化し、クエリー区間[tot-L,tot-1]の最大値(totは現在の要素総数+1)2、totの要素を(n+t)%dに変更して線分ツリーを初期化する際、すべての要素が0線分ツリーで区間最大値を求める問題==コード量は大きくなく、単純な線分ツリーに属する

/************************************************************** Problem: 1012 User: Rainbow6174 Language: C++ Result: Accepted Time:1232 ms Memory:15336 kb ****************************************************************/

#include<iostream>
#include<stdio.h>
using namespace std;
char c[5];
int m,q,a,b,tot;
long long MOD,ans,x,n,val[200005],add[800020],maxn[800020];
void maintain(int o,int l,int r)
{
    if(l!=r)
        maxn[o]=max(maxn[o<<1],maxn[(o<<1)+1]);
    else maxn[o]=val[l];
}
void addnum(int o,int l,int r)
{
    if(l>=a && r<=b)
    {
        maxn[o]=val[a]=x;
        return;
    }
    if(r<a || l>b)return;
    int mid=(l+r)/2;
    addnum(o<<1,l,mid);
    addnum((o<<1)+1,mid+1,r);
    maintain(o,l,r);
    return;
}
void getmax(int o,int l,int r)
{
    if(l>=a && r<=b)
    {
        ans=max(ans,maxn[o]);
        return;
    }
    if(r<a || l>b)return;
    int mid=(l+r)/2;
    getmax(o<<1,l,mid);
    getmax((o<<1)+1,mid+1,r);
    maintain(o,l,r);
    return;
}
int main(void)
{
    scanf("%d%lld",&m,&MOD);
    tot=1;
    for(int i=1;i<=m;i++)
    {
        scanf("%s%lld",&c,&n);
        if(c[0]=='A')
        {
            x=(ans+n)%MOD;
            a=tot;b=tot;
            addnum(1,1,m);
            tot++;
        }
        else
        {
            ans=0;
            a=tot-n;
            b=tot-1;
            getmax(1,1,m);
            printf("%lld
",ans);
        }
    }
    return 0;
}