1549：最大数

  • 向序列后添加一个数，序列长度变成 n+1
  • 单点修改，把n+1这个位置上的点（初始化为0）修改为添加那个数的值
  • 询问操作：询问这个序列中最后 L 个数中最大的数是多少
  • 区间查询[n - L + 1,n],维护一个属性最大值v

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

const int N = 2e5 + 10;

int m,p;
int n;

struct Node{
    int l,r;
    int v;
}tr[N * 4];

void pushup(int u){
    tr[u].v = max(tr[u << 1].v,tr[u << 1 | 1].v);
}

void build(int u,int l,int r){
    tr[u] = {l,r};
    if(l == r) return ;
    int mid = l + r >> 1;
    build(u << 1,l,mid);
    build(u << 1 | 1,mid + 1,r);
}

int query(int u,int l,int r){
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;

    int mid = (tr[u].l + tr[u].r) >> 1;
    int v = 0;
    if(l <= mid) v = query(u << 1,l,r);
    if(r > mid) v = max(v,query(u << 1 | 1,l,r));

    return v;
}

void modify(int u,int x,int v){
    if(tr[u].l == x && tr[u].r == x) tr[u].v = v;
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid) modify(u << 1,x,v);
        else modify(u << 1 | 1,x,v);
        pushup(u);
    }
}

int main() {
    scanf("%d%d",&m,&p);
    build(1,1,m);
    char op[2];
    int a = 0,last = 0;
    while(m -- ){
        scanf("%s%d",op,&a);
        if(*op == 'Q'){
            last = query(1,n - a + 1,n);
            printf("%d\n",last);
        }else{
            modify(1,n + 1,(a + last) % p);
            n ++; 
        }
    }    
    return 0;
}