最大数

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1413 字

维护一个序列，At在末尾追加%p，QL询问末

一本通
练习

正文

/*
原题：一本通 4.3 练习 1 最大数 (JSOI 2008)
题意：维护一个序列，A t 在末尾追加 (t+上次答案)%p，Q L 询问末尾 L 个数的最大值。
思路：序列总长不超过 m，建大小为 MAXM 的线段树维护区间最大值；追加即单点修改，询问即区间最值。
复杂度：时间 O(m log m)，空间 O(m)。
易错点：下标 1 基，用 len 维护当前长度；首次询问前 a=0；数值与 p 用 long long。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXM=200005;
ll mx[MAXM*4];
int len=0;
void modify(int node,int l,int r,int pos,ll v){
    if(l==r){
        mx[node]=v;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid){
        modify(node*2,l,mid,pos,v);
    }else{
        modify(node*2+1,mid+1,r,pos,v);
    }
    mx[node]=max(mx[node*2],mx[node*2+1]);
}
ll query(int node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return mx[node];
    }
    int mid=(l+r)/2;
    ll res=0;
    if(ql<=mid){
        res=max(res,query(node*2,l,mid,ql,qr));
    }
    if(qr>mid){
        res=max(res,query(node*2+1,mid+1,r,ql,qr));
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m;
    ll p;
    cin>>m>>p;
    ll last=0;
    for(int i=0;i<m;i++){
        char op;
        cin>>op;
        if(op=='A'){
            ll t;
            cin>>t;
            ll val=(t+last)%p;
            len++;
            modify(1,1,m,len,val);
        }else{
            int L;
            cin>>L;
            ll ans=query(1,1,m,len-L+1,len);
            last=ans;
            cout<<ans<<"\n";
        }
    }
    return 0;
}

最大数

正文

一本通·提高篇的其它内容