P1198 [JSOI2008]最大数 动态RMQ

题目链接：https://www.luogu.com.cn/problem/P1198
题目大意：


思路：每次修改都是在末尾，那么RMQ只会影响n结尾的区间，有logn个，直接修改就可以了。

#include <bits/stdc++.h>
using namespace std;

int dp[200005][22];

int main() {

    int m, d; scanf("%d%d", &m, &d);
    int t=0;
    int N=0;
    for(int i=1; i<=m; i++){
        char s[5]; int x; scanf("%s%d", s, &x);
        if(s[0]=='A'){
            x+=t; x%=d;
            dp[++N][0]=x;
            for(int i=1; (1<<i)<=N; i++){
                int pos=N-(1<<i)+1;
                dp[pos][i]=max(dp[pos][i-1], dp[pos+(1<<(i-1))][i-1]);
            }
        }
        else{
            int l=N-x+1, r=N;
            int len=log2(r-l+1);
            int mi=max(dp[l][len], dp[r-(1<<(len))+1][len]);
            t=mi;
            printf("%d\n", mi);
        }
    }

    return 0;
}