题解 P1198 【[JSOI2008]最大数】

707001933K · 2017-08-07 21:02:05 · 题解

以前的线段树打一次错一次，请求一下我的心理阴影面积QAQ

发个题解庆祝第一次线段树的1A^_^

一个裸的线段树模板。

上代码（放心copy，没有bug）

#include<cstdio>
#include<algorithm>
using namespace std;
int T,Mod;
const int N=410000;
int tree[N];
int cnt=0;
void add(int p,int l,int r,int ql,int qr,int x){
    if (l+1==r){
        tree[p]=x;
        return;
    }
    int mid=(l+r)>>1;
    if (ql<mid)add(2*p,l,mid,ql,qr,x);
    if (mid<qr)add(2*p+1,mid,r,ql,qr,x);
    tree[p]=max(tree[2*p],tree[2*p+1]);
}
int query(int p,int l,int r,int ql,int qr){
    if (ql<=l && r<=qr)return tree[p];
    int mid=(l+r)>>1;
    int t=0;
    if (ql<mid)t=max(t,query(2*p,l,mid,ql,qr));
    if (mid<qr)t=max(t,query(2*p+1,mid,r,ql,qr));
    return t;
}
int main(){
    scanf("%d%d",&T,&Mod);
    int last=0;
    while (T--){
        char opt;int xx;
        scanf("\n%c%d",&opt,&xx);
        if (opt=='A'){
            cnt++;
            xx+=last;xx%=Mod;
            add(1,1,200000,cnt,cnt+1,xx);
        }else{
            last=query(1,1,200000,cnt-xx+1,cnt+1);
            printf("%d\n",last);
        }
    }
    return 0;
}