P1198 [JSOI2008]最大数 （逆ST）

题目传送门

思路：建立一个逆ST表,从右到左的区间查询, 每次插入一个数就更新一次区间最值,然后区间查询用RMQ实现就行.

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,id;
typedef long long ll;
ll mod,a[N],pre,f[N][20];
ll que(int len){ //ST区间查询.(query)
	int k=0,l=id-len+1;
	while((1<<k)*2<len) k++;
	return max(f[id][k],f[l+(1<<k)-1][k]);
}
void upd(int n){ //更新区间最值.(update) O(logn) 
	f[n][0]=a[n];
	for(int i=1;(1<<i)<=n;i++)
		f[n][i]=max(f[n][i-1],f[n-(1<<(i-1))][i-1]);
}
int main(){
	scanf("%d%lld",&t,&mod);
	while(t--){
		char c;
		cin>>c;
		if(c=='A'){
			ll tmp;
			cin>>tmp;
			a[++id]=(tmp+pre)%mod;
			upd(id);
		}
		else {
			ll x;
			cin>>x;
			pre=que(x);
			printf("%lld\n",pre);
		}
	}
	return 0; 
}