【JSOI2008】【bzoj1012】最大数maxnumber

            

题面

维护一个数列,提供以下两种操作:
1、 查询操作:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。
2、 插入操作:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾。

题解

1、思路:维护一颗叶节点数为m的线段树(就算m次操作都是插入也只有m个元素),区间查询即可。复杂度O(<span class="MathJax" id="MathJax-Element-16-Frame" tabindex="0" data-mathml="

mlog2m

" role="presentation" style="position: relative;">

mlog2m

)。
2、数据有毒。。。bzojAC的code洛谷MLE,洛谷AC的bzojTLE。

BZOJAC[洛谷MLE,不知道为什么]

//#include
#include
#include
using namespace std;
const int maxn = 200005;

int sgt[maxn<<2];
void change(int p, int l, int r, int x, int v){
    if(l == r){
        sgt[p] = v;
        return ;
    }
    int m = (l+r)/2;
    if(x <= m)change(p*2,l,m,x,v);
    if(x > m)change(p*2+1,m+1,r,x,v);
    sgt[p] = max(sgt[p*2],sgt[p*2+1]);
}
int query(int p, int l, int r, int L, int R){
    if(L <= l && r <= R)return sgt[p];
    int m = (l+r)/2, ans = 0;
    if(L <= m)ans = max(ans, query(p*2,l,m,L,R));
    if(R > m)ans = max(ans, query(p*2+1,m+1,r,L,R));
    return ans;
}

int main(){
    //ios::sync_with_stdio(false);
    int n=0, m, mod, t=0;
    scanf("%d %d",&m, &mod);//cin>>m>>mod;
    for(int i = 1; i <= m; i++){
        char op[2];  int x;  //cin>>op>>x;
        scanf("%s%d", op, &x);
        if(op[0] == 'Q'){
            printf("%d\n", t=query(1,1,m,n-x+1,n));
            //cout<<(t = query(1,1,m,n-x+1,n))<<"\n";
        }else{
            change(1,1,m,++n,(x+t)%mod);
        }
    }
    return 0;
}

luoguAC[bzojTLE,好像是scanf的锅]

#include
#include
using namespace std;
const int maxn = 200010;
typedef long long LL;

struct node{
    int l, r;
    LL val, addmark;
}sgt[maxn<<2];
void build(int p, int l, int r){
    sgt[p].l = l, sgt[p].r = r;
    if(l == r){
        //sgt[p].val = a[l];
    }else{
        int m = (l+r)/2;
        build(p*2,l,m);
        build(p*2+1,m+1,r);
        sgt[p].val = max(sgt[p*2].val,sgt[p*2+1].val);
    }
}
void change(int p, int x, int v){
    if(sgt[p].l == sgt[p].r){
        sgt[p].val = v;
        return ;
    }
    int m = (sgt[p].l+sgt[p].r)/2;
    if(x <= m)change(p*2,x,v);
    if(x > m)change(p*2+1,x,v);
    sgt[p].val = max(sgt[p*2].val,sgt[p*2+1].val);
}
LL query(int p, int l, int r){
    if(l <= sgt[p].l && sgt[p].r <= r)return sgt[p].val;
    LL m = (sgt[p].l+sgt[p].r)/2, ans = 0;
    if(l <= m)ans = max(ans, query(p*2,l,r));
    if(r > m)ans = max(ans, query(p*2+1,l,r));
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    LL n=0, m, mod, t=0;
    cin>>m>>mod;
    build(1,1,m);
    for(int i = 1; i <= m; i++){
        char op;  LL x;  cin>>op>>x;
        if(op == 'Q'){
            cout<<(t = query(1,n-x+1,n))<<"\n";
        }else{
            change(1,++n,(x+t)%mod);
        }
    }
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像