#10127. 「一本通 4.3 练习 1」最大数

2019-01-28 13:27:41


10127. 「一本通 4.3 练习 1」最大数

题意

给定一个正整数数列 $a_1, a_2, a_3, \cdots , a_n$ ,每一个数都在 $0\sim p–1$ 之间。可以对这列数进行两种操作:

  • 添加操作:向序列后添加一个数,序列长度变成 $n + 1$ ;

  • 询问操作:询问这个序列中最后 $L$ 个数中最大的数是多少。

程序运行的最开始,整数序列为空。写一个程序,读入操作的序列,并输出询问操作的答案。

思路

模板题呀。

#include<bits/stdc++.h>
#define ll long long
#define MAXNUM 200000*4+10
using namespace std;
struct node{
    ll l,r,lef,rig,c;
}tree[MAXNUM];
ll n,m,q,len,las;
void build(ll l,ll r){
    ll root=++len;
    tree[root].l=l;tree[root].r=r;tree[root].lef=tree[root].rig=-1;
    if(l<r){
        ll mid=(l+r)/2;
        tree[root].lef=len+1;build(l,mid);
        tree[root].rig=len+1;build(mid+1,r);
    }
}
void update(ll root,ll x,ll k){
    if(tree[root].l==tree[root].r){tree[root].c=k;return ;}
    ll lef=tree[root].lef,rig=tree[root].rig;
    ll mid=(tree[root].l+tree[root].r)/2;
    if(x<=mid) update(lef,x,k);
    else update(rig,x,k);
    tree[root].c=max(tree[lef].c,tree[rig].c);
}
ll query(ll root,ll l,ll r){
    if(tree[root].l>=l&&tree[root].r<=r) return tree[root].c;
    ll lef=tree[root].lef,rig=tree[root].rig;
    ll mid=(tree[root].l+tree[root].r)/2;
    if(r<=mid) return query(lef,l,r);
    else if(mid<l) return query(rig,l,r);
    else return max(query(lef,l,mid),query(rig,mid+1,r));
}
int main(){
    scanf("%lld%lld",&m,&q);
    build(1,m);
    while(m--){
        char s;cin>>s;
        if(s=='A'){
            ll x;scanf("%lld",&x);n++;
            update(1,n,(x+las)%q);
        }else{
            ll x;scanf("%lld",&x);
            las=query(1,n-x+1,n);
            printf("%lld\n",las);
        }
    }
}