bzoj 1012: [JSOI2008]最大数maxnumber (线段树）

2022-10-27 10:59:15

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 13081 Solved: 5654
[Submit][Status][Discuss]

Description

　　现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：Q L 功能：查询当前数列中末尾L
个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作。语法：A n 功能：将n加
上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取
模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个
数。

Input

　　第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来
M行，查询操作或者插入操作。

Output

　　对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。

Sample Input

5 100
A 96
Q 1
A 97
Q 1
Q 2

Sample Output

96
93
96

思路：

水题

实现代码:

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define mid ll m = (l + r) >> 1

const ll M = 2e5+;

const ll inf = 2e5+;

ll sum[M<<],n;

ll m;

void pushup(ll rt){

    sum[rt] = max(sum[rt<<],sum[rt<<|]);

}

void build(ll l,ll r,ll rt){

    if(l == r){

        sum[rt] = ;

        return ;

    }

    mid;

    build(lson);

    build(rson);

    pushup(rt);

}

void update(ll p,ll c,ll l,ll r,ll rt){

    if(l == r){

        sum[rt] = c;

        return ;

    }

    mid;

    if(p <= m) update(p,c,lson);

    else update(p,c,rson);

    pushup(rt);

}

ll query(ll L,ll R,ll l,ll r,ll rt){

    if(L <= l&&R >= r){

        return sum[rt];

    }

    mid;

    ll ret = ;

    if(L <= m) ret = max(ret,query(L,R,lson));

    if(R > m) ret = max(ret,query(L,R,rson));

    return ret ;

}

int main(){

    scanf("%lld%lld",&n,&m);

    ll len = ,t = ;

    build(,inf,);

    char c[]; ll x;

    while(n--){

        scanf("%s",c);

        scanf("%lld",&x);

        if(c[]=='A'){

            len++;

            update(len,(t+x)%m,,inf,);

        }

        else{

            t = query(len-x+,len,,inf,);

            printf("%lld\n",t);

        }

    }

}

码农公寓