题解

我又十分不友好的复制题面了(懒)~~

附个链接

题目描述

现在请求你维护一个数列,要求提供以下两种操作:

1、 查询操作。

语法:Q L

功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。

限制:LL不超过当前数列的长度。(L > 0)(L>0)

2、 插入操作。

语法:A n

功能:将nn加上tt,其中tt是最近一次查询操作的答案(如果还未执行过查询操作,则t=0t=0),并将所得结果对一个固定的常数DD取模,将所得答案插入到数列的末尾。

限制:nn是整数(可能为负数)并且在长整范围内。

注意:初始时数列是空的,没有一个数。

输入输出格式

输入格式:

 

第一行两个整数,MM和DD,其中MM表示操作的个数(M \le 200,000)(M≤200,000),DD如上文中所述,满足(0<D<2,000,000,000)(0<D<2,000,000,000)

接下来的MM行,每行一个字符串,描述一个具体的操作。语法如上文所述。

 

输出格式:

 

对于每一个查询操作,你应该按照顺序依次输出结果,每个结果占一行。

 

输入输出样例

输入样例#1: 

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

输出样例#1: 

96
93
96
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define int long long 
const int maxnn = 200200 ;
#define inf -0x3ffffff
using namespace std ;
struct dy{
    int lc , rc , maxn ;
}tree[maxnn<<2];
int m , mod , tmp , t = 1 , ans = inf , k , q , tail ;
int a[maxnn] ;
char opt ;
void pushup(int u){
    tree[u].maxn = max(tree[tree[u].lc].maxn,tree[tree[u].rc].maxn) % mod ;
}
void build(int u , int l , int r){//建树
    tree[u].maxn = -inf ;
    if(l == r){
        return ;
    }
    int mid = (l+r) >> 1 ;
    tree[u].lc = ++t ;
    build(tree[u].lc,l,mid) ;
    tree[u].rc = ++t ;
    build(tree[u].rc,mid+1,r) ;
    pushup(u) ;
}
void updata(int u , int l ,int r , int x , int w){//区间修改
    if(r == x && l == x){
        tree[u].maxn = w ;
        return ;
    }
    int mid = (l+r) >> 1 ;
    if(x <= mid) updata(tree[u].lc ,l,mid,x,w) ;
    else
    if(x > mid) updata(tree[u].rc,mid+1,r,x,w) ;
    pushup(u) ;
}
void query(int u,int l,int r,int ll,int rr){//查找区间最大值
    if(l == ll && r == rr){
        ans=max(ans,tree[u].maxn) ; 
        return ;
    }
    int mid = (l+r) >> 1 ;
    if(rr <= mid) query(tree[u].lc,l,mid,ll,rr) ;
    else if(ll > mid) query(tree[u].rc,mid+1,r,ll,rr) ;
    else{
        query(tree[u].lc,l,mid,ll,mid) ;
        query(tree[u].rc,mid+1,r,mid+1,rr) ;
    }
}
signed main(){
    cin >> m >> mod ;
    build(1,1,m) ;
    for(int i = 1 ; i <= m ; i ++){
        cin >> opt ;
        if(opt == 'A'){
            cin >> k ;
            k = (k+tmp) % mod ;
            tail ++ ;
            updata(1,1,m,tail,k) ;
        }
        if(opt == 'Q'){
            ans = inf;
            scanf("%lld",&q);
            if(!q)  tmp = 0;
            else{
                int l,r ;
                r = tail ;
                l = tail-q+1 ;
                query(1,1,m,l,r);
                tmp = ans;
            }
            printf("%lld\n",tmp);
        }
    }
    return 0 ;
}

return 0 ;