[JSOI 2008] 最大数

知识点

线段树、在线查询、取模运算

解题思路

使用线段树按追加位置保存数值。插入时用128位计算(n+t)的模，规范为0到D-1；查询区间为[len-L+1,len]，结果写回t。

正确性说明

线段树每节点保存覆盖区间最大值，点修改后逐层重算，区间查询按不交区间划分并取最大，归纳保持正确。每次插入严格使用最近一次查询t，按操作顺序处理即符合在线语义。

易错点

不能预先将所有插入值固定；查询L不能理解成起点；n可能为负且达long long极值，先转128位再加t；D=1时全部为0。

复杂度

每次操作O(log M)，空间O(M)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int M;long long D;cin>>M>>D;int N=1;while(N<M)N<<=1;vector<long long>tr(2*N);int len=0;long long t=0;for(int i=0;i<M;i++){char op;long long x;cin>>op>>x;if(op=='A'){__int128 z=(__int128)x+t;long long v=(long long)(z%D);if(v<0)v+=D;int p=N+len++;tr[p]=v;for(p>>=1;p;p>>=1)tr[p]=max(tr[p<<1],tr[p<<1|1]);}else{int l=N+len-(int)x,r=N+len;long long ans=0;for(;l<r;l>>=1,r>>=1){if(l&1)ans=max(ans,tr[l++]);if(r&1)ans=max(ans,tr[--r]);}t=ans;cout<<ans<<'\n';}}}