题解 P1198 【[JSOI2008]最大数】

冰翼ACE · 2016-10-02 21:52:57 · 题解

有点离线的想法：如果执行了m次加入操作，那么整个序列的长度也就是m呗

所以，一开始先建好长度为m的线段树，初始化min=-INT_MAX,剩下的就是添加和查询了。

拙劣的代码献上：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;
int m,d;
struct node{
    int l,r,num;
    int umax;
}tree[8*200000+16];
char c;
int num,t,p;
void build(int l,int r,int id){
    int mid=(l+r)/2;
    tree[id].l=l;
    tree[id].r=r;
    tree[id].umax=-INT_MAX;
    tree[id].num=-INT_MAX;
    if(l+1==r) return;
    else{
        build(l,mid,id*2);
        build(mid,r,id*2+1);
    }
}
int change(int l,int r,int id,int n){
    if(tree[id].l==l&&tree[id].r==r){
        tree[id].num=n;
        tree[id].umax=n;
        return n;
    }else{
        int temp,mid=(tree[id].l+tree[id].r)/2;
        if(r<=mid) temp=change(l,r,id*2,n);
        else if(l>=mid) temp=change(l,r,id*2+1,n);
        else temp=max(change(l,mid,id*2+1,n),change(mid,r,id*2+1,n));
        tree[id].umax=max(temp,tree[id].umax);
        return tree[id].umax;
    }
}
int query(int l,int r,int id){
    if(tree[id].l==l&&tree[id].r==r) return tree[id].umax;
    else{
        int mid=(tree[id].l+tree[id].r)/2;
        if(r<=mid) return query(l,r,id*2);
        else if(l>=mid) return query(l,r,id*2+1);
        else return max(query(l,mid,id*2),query(mid,r,id*2+1));
    }
}
int main(){
    #ifdef     ONLINE_JUDGE
    #else
        freopen("in.txt","r",stdin);
    #endif
    scanf("%d %d\n",&m,&d);
    build(1,m+1,1);    
    t=0;
    p=1;
    for(int i=0;i<m;i++){
        scanf("%c %d\n",&c,&num);
        if(c=='A'){
            num+=t;
            num%=d;
            change(p,p+1,1,num);
            p++;
        }else if(c=='Q'){
            t=query(p-num,p,1);
            printf("%d\n",t);
        }
    }
    return 0;
}