当前位置:网站首页>P1198 [jsoi2008] maximum number (inverse st)

P1198 [jsoi2008] maximum number (inverse st)

2021-08-10 08:05:16 wx6110fa547fd20

P1198 [JSOI2008] The maximum number ( The inverse ST)

  Subject portal

Ideas : Establish an inverse ST surface , Right to left interval query , The interval maximum value is updated every time a number is inserted , Then the interval query uses RMQ Just make it happen .

AC Code :

#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 Interval query .(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 interval maximum .(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://chowdera.com/2021/08/20210810080205632q.html

随机推荐