# P1198 [jsoi2008] maximum number (inverse st)

2021-08-10 08:05:16

## 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.
```

https://chowdera.com/2021/08/20210810080205632q.html