洛谷P1198 [JSOI2008]最大数（单点修改，区间查询）

洛谷P1198 [JSOI2008]最大数

简单的线段树单点问题。

问题：读入A和Q时，按照读入一个字符会MLE，换成读入字符串就可以了。

#include<bits/stdc++.h>

using namespace std;

#define lson l, mid, root << 1

#define rson mid + 1, r, root << 1 | 1

const int maxn = 200005;

long long MAX[maxn << 2], D, t, xx;

int M, len;

char c[5];

inline void pushDown(int root){

    MAX[root] = max(MAX[root << 1], MAX[root << 1 | 1]);

}

void update(int l, int r, int root, int pos, long long x)

{

    if(l == r){

        MAX[root] = x; return;

    }

    int mid = (l + r) >> 1;

    if(pos <= mid) update(lson, pos, x);

    else update(rson, pos, x);

    pushDown(root);

}

long long query(int l, int r, int root, int L, int R)

{

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

        return MAX[root];

    }

    int mid = (l + r) >> 1;

    if(R <= mid) return query(lson, L, R);

    else if(L >= mid + 1) return query(rson, L, R);

    else return max(query(lson, L, mid), query(rson, mid + 1, R));

}

int main()

{

    scanf("%d%lld", &M, &D);

    for(int i = 1; i <= M; i++){

        scanf("%s%lld", c, &xx);

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

            xx = (t * 1LL + xx) % D;

            len++;

            update(1, M, 1, len, xx);

        }

        else{

            t = query(1, M, 1, (int)(len - xx + 1), len) % D;

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

        }

    }

    return 0;

}

巴特西

洛谷P1198 [JSOI2008]最大数（单点修改，区间查询）

最新文章

热门文章