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;
}
查看20道真题和解析