P1198 [JSOI2008] 最大数

XichenOC · 2024-10-15 10:18:27 · 题解

P1198 [JSOI2008] 最大数

题目翻译：

有两个操作，一个是查找L到末尾的最大值，另个是将n+t,t为上一次查找的结果对D取模后加到末尾。

方法：

用线段树维护区间最大值，将初始线段树大小设为M，因为最多加入M个点。每一次保留上一次查询的结果。在进行单点修改即可

注意：

需开long long否则Subtask数据过不了！！

完整代码：

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define int long long
using namespace std;
const int N=2e5+5;
int tr[N*4];
void update(int p,int l,int r,int num,int add){
    if(l==r){
        tr[p]+=add;
        return;
    }
    int mid=(l+r)>>1;
    if(num<=mid)update(lc,l,mid,num,add);
    if(num>mid)update(rc,mid+1,r,num,add);
    tr[p]=max(tr[lc],tr[rc]);
}
int query(int p,int l,int r,int ll,int rr){
    if(ll<=l && r<=rr)return tr[p];
    int mid=(l+r)>>1;
    int res=-2e9;
    if(ll<=mid)res=max(res,query(lc,l,mid,ll,rr));
    if(mid<rr)res=max(res,query(rc,mid+1,r,ll,rr));
    return res;
}
signed main(){
    int m,d,t=0,res=0;
    cin>>m>>d;
    for(int i=1;i<=m;i++){
        char opt;
        cin>>opt;
        if(opt=='Q'){
            int l;
            cin>>l;
            t=query(1,1,m,res-l+1,res);
            cout<<t<<endl;
        }
        if(opt=='A'){
            int n;
            res++;
            cin>>n;
            update(1,1,m,res,(n+t)%d);
        }
    }
}

线段树讲解