首页 > 代码库 > bzoj1012 [JSOI2008]最大数maxnumber

bzoj1012 [JSOI2008]最大数maxnumber

  这道题有很多的做法

  裸的线段树

#include<cstdio>
#define lc o*2
#define rc o*2+1
#define mid (l+r)/2
inline int max(int x,int y){
    return x>y? x:y;
}
inline int read(){
    char c; while(c=getchar(),c<0 || c>9); int x=c-0;
    while(c=getchar(),c>=0 && c<=9) x=x*10+c-0; return x;
}
int MOD,maxv[2000001],a[2000001];
inline void maintain(int o,int l,int r){
    if(l==r) maxv[o]=a[l];
    if(l<r)
        maxv[o]=max(maxv[o*2],maxv[o*2+1]);
    return;
}
int l0,r0,maxx;
void update(int o,int l,int r,int x){
    if(l==r) a[l]=x;
    else {
        if(l0<=mid) update(lc,l,mid,x);
        if(r0>mid) update(rc,mid+1,r,x); 
    }
    maintain(o,l,r);
}
void query(int o,int l,int r){
    if(l>=l0 && r<=r0) maxx=max(maxv[o],maxx);
    else {
        if(l0<=mid) query(lc,l,mid);
        if(r0>mid) query(rc,mid+1,r);
    }
}
int pre=0;
int main(){
    int n=read(); MOD=read(); int m=0;
    for(int i=1;i<=n;i+=1){
        char c; while(c=getchar(),c!=Q && c!=A);
        if(c==A) l0=r0=++m,update(1,1,n,((long long)read()+pre)%MOD);
        if(c==Q) l0=m-read()+1,r0=m,maxx=-2e9,query(1,1,n),printf("%d\n",pre=maxx);
    }
}

  倍增

#include<cstdio>
#include<cmath>
inline int read(){
    char c; while(c=getchar(),c<0 || c>9); int x=c-0;
    while(c=getchar(),c>=0 && c<=9) x=x*10+c-0; return x;
}
inline int max(int x,int y){return x>y? x:y;}
int m,d,cnt,t,f[200001][18];
int main(){
    for(m=read(),d=read();m;m--){
        char c; while(c=getchar(),c!=A && c!=Q);
        if(c==A){
            f[++cnt][0]=(long long)(read()+t)%d; 
            for(int i=1;(1<<i)<=cnt;i+=1)
                f[cnt-(1<<i)+1][i]=max(f[cnt-(1<<i)+1][i-1],f[cnt-(1<<i-1)+1][i-1]);
        }else {
            int k=read(),x=log(k)/log(2);
            printf("%d\n",t=max(f[cnt-k+1][x],f[cnt-(1<<x)+1][x]));
        }
    }
    return 0;
}

  单调栈+二分

#include<cstdio>
inline int read(){
    char c; while(c=getchar(),c<0 || c>9); int x=c-0;
    while(c=getchar(),c>=0 && c<=9) x=x*10+c-0; return x;
}
struct num{
    int x,y;
}stack[200001];
int pre=0,MOD;
inline int seek(int l,int r,int x){
    while(l<=r){
        int mid=l+r>>1;
        if(stack[mid].y<x) l=mid+1; else r=mid-1;
    }return l;
}
int main(){
    int n=read(),size=0; MOD=read();
    int m=0;
    for(int i=1;i<=n;i+=1){
        char c; while(c=getchar(),c!=Q && c!=A);
        int x=read();
        if(c==A){
            x=((long long)x+pre)%MOD; ++m;
            while(size && x>stack[size].x) size--;
            stack[++size].x=x; stack[size].y=m;
        }else{
            pre=stack[seek(1,size,m-x+1)].x,printf("%d\n",pre);
        }
    }
}

 

bzoj1012 [JSOI2008]最大数maxnumber