当前位置:网站首页>P1198 [JSOI2008]最大数 (逆ST)

P1198 [JSOI2008]最大数 (逆ST)

2021-08-10 08:02:47 wx6110fa547fd20

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; 
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15326986/3328283

随机推荐