洛谷P1198.最大数
洛谷P1198.最大数
-
转化成ST表的题
- 每次加入数都去更新被影响的数
-
#include<bits/stdc++.h>using namespace std;const int N = 200010;typedef long long LL;int m,cnt;LL D,t;int f[N][20],a[N],lg[N];int main(){cin>>m>>D;lg[1] = 0;for(int i=2;i<=N;i++) lg[i] = lg[(i>>1)] + 1;while(m--){char c;LL x;cin>>c>>x;if(c == 'A'){a[++cnt] = (x + t) % D;f[cnt][0] = a[cnt];for(int u=1;u<=lg[cnt];u++)for(int i=cnt-(1<<u);i<=cnt-(1<<u)+1;i++){//如果够不到cnt 那么一定不会被更新if(i + (1<<u) < cnt) continue;f[i][u] = max(f[i][u-1],f[i+(1<<(u-1))][u-1]);}}else{int l = cnt - x + 1;int r = cnt;int w = lg[r - l + 1];t = max(f[l][w],f[r-(1<<w)+1][w]);cout<<t<<endl;}}}