[JSOI2008] 最大数 (ST表)

算法

观察到插入都在末尾进行
考虑逆向ST表

代码

#include <bits/stdc++.h>
const int MAXSIZE = 2e5 + 20;
#define int long longint Time, D;int t = 0;/*反向st表方便处理末尾的插入*/
class reverse_ST
{private:int Max[MAXSIZE][20];public:int NowSize;void init(){memset(Max, 0, sizeof(Max));NowSize = 0;}void insert(int x){Max[++NowSize][0] = x;for(int i = 1; NowSize - (1 << i) >= 0; i++){Max[NowSize][i] = std::max(Max[NowSize][i - 1], Max[NowSize - (1 << (i - 1))][i - 1]);}}int find(int L, int R) {int Length = R - L + 1;int k = log2(Length);return std::max(Max[R][k], Max[L + (1 << (k)) - 1][k]);}
}ST;void solve()
{char type;ST.init();while(Time--){std::cin >> type;if(type == 'A'){int x;scanf("%lld", &x);ST.insert((x + t) % D);}else{int L;scanf("%lld", &L);int ans = ST.find(ST.NowSize - L + 1, ST.NowSize);printf("%lld\n", ans);t = ans;}}
}signed main()
{scanf("%lld %lld", &Time, &D);solve();return 0;
}

总结

代码

注意ST表的查询方式为

int Length = R - L + 1;
int k = log2(Length);return std::max(Max[R][k], Max[L + (1 << (k)) - 1][k]);

思路

正难则反