【题解】Luogu P1198【[JSOI2008]最大数】

这里就差不多是个线段树的板题,尽管在洛谷只有80分,$BZOJ$居然超时了233,但是自认为还是写的不错的。

#include<cstdio>
#include<iostream> 

typedef long long int64;

const int64 MAXN = 200000 + 6;

int64 a[MAXN],d;

class SegmentTree{
    public:int64 l,r;
    public:int64 max;
};
SegmentTree t[MAXN * 4];

inline int64 LEFT(int64 x){return x << 1;}
inline int64 RIGHT(int64 x){return x << 1 | 1;}
inline int64 MID(int64 l,int64 r){return (l + r) >> 1;}
inline int64 max(int64 a,int64 b){return a > b ? a : b;}

void build(int64 p,int64 l,int64 r){
    t[p].l = l;t[p].r = r;
    if(l == r){
        t[p].max = 0;
        return;
    }
    build(LEFT(p),l,MID(l,r));
    build(RIGHT(p),MID(l,r) + 1,r);
    t[p].max = max(t[LEFT(p)].max,t[RIGHT(p)].max);
}

void change(int64 p,int64 x,int64 v){
    if(t[p].l == t[p].r){
        //t[p].max = v;
        t[p].max=max(t[p].max,v);
        return;
    }
    if(x <= MID(t[p].l,t[p].r)){
        change(LEFT(p),x,v);
    }else{
        change(RIGHT(p),x,v);
    }
    t[p].max = max(t[LEFT(p)].max,t[RIGHT(p)].max);
}

int64 ask(int64 p,int64 l,int64 r){
    if(l <= t[p].l && r >= t[p].r){
        return t[p].max;
    }
    int64 ans = -0x7fffffff;
    if(l <= MID(t[p].l,t[p].r)){
        ans = max(ans,ask(LEFT(p),l,r));
    }
    if(r > MID(t[p].l,t[p].r)){
        ans = max(ans,ask(RIGHT(p),l,r));
    }
    return ans;
}

int main(){
    int64 m,d;
    //scanf("%lld %lld\n",&m,&d);
    
    std::cin >> m >> d;
    
    int64 ans = 0,j = 0;
    
    for(int64 i = 1;i <= m;i++){
        //a[i] = -0x7fffffff;
    }
    
    build(1,1,m);
    
    bool running = true;
    
    while(m--){ 
        char op;
        int64 key;
        //scanf("%c %lld\n",&op,&key);
        
        std::cin >> op >> key;
        
        //if(op == 'Q' && running){
        //  printf("0\n");
        //  running = false;
        //}
        
        if(op == 'A'){
            j++;
            change(1,j,(key + ans) % d);
        }else{
            if(j != 0){
                ans = ask(1, j - key + 1,j) % d;
                printf("%lld\n",ans);
            }else{
                printf("0\n");
            }
            
        }
    }
        
    return 0;
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注