说起来这还是蒟蒻AC的第一道省选线段树呢。

这道题和其他线段树最大的不同就是在于本题数组一直在增大。

寻常的线段树蒟蒻习惯用如下的结构体储存，然而对于此题就不行了：

struct node{
int l, r;
int val;
} tree[maxn << ];

这是因为这道题没有用建树，因此l, r就不存在啊！

那么解决方法就是用朴实的tree数组储存val, l和r则手动传入函数！！

所以根据这个原理，稍微修改一下模板就可以得出全新的两个函数！！

void Update(ll l, ll r, ll index, ll value, ll pos) {
if(l == r) {
tree[pos] = value;
return ;
}
ll mid = (l + r) >> ;
if(mid >= index) Update(l, mid, index, value, pos << );
if(mid < index) Update(mid + , r, index, value, pos << | );
tree[pos] = max(tree[pos << ], tree[pos << | ]);
}

ll Query(ll L, ll R, ll l, ll r, ll pos) {
if(L >= l && R <= r) return tree[pos]; ll mid = (L + R) >> ;
ll ans = ;
if(mid >= l) ans = max(ans, Query(L, mid, l, r, pos << ));
if(mid < r) ans = max(ans, Query(mid + , R, l, r, pos << | ));
return ans;
}

注明：第二个函数中，L,R表示当前区间，l,r表示寻找的区间。

完整AC代码献上：

#include
#include
#include
using namespace std;

typedef long long ll;
const int maxn = ;

ll tree[maxn << ];

ll m, d, t = , len = , x;
char op;

void Update(ll l, ll r, ll index, ll value, ll pos) {
if(l == r) {
tree[pos] = value;
return ;
}
ll mid = (l + r) >> ;
if(mid >= index) Update(l, mid, index, value, pos << );
if(mid < index) Update(mid + , r, index, value, pos << | );
tree[pos] = max(tree[pos << ], tree[pos << | ]);
}

ll Query(ll L, ll R, ll l, ll r, ll pos) {
if(L >= l && R <= r) return tree[pos]; ll mid = (L + R) >> ;
ll ans = ;
if(mid >= l) ans = max(ans, Query(L, mid, l, r, pos << ));
if(mid < r) ans = max(ans, Query(mid + , R, l, r, pos << | ));
return ans;
}

int main() {
cin >> m >> d;
for(ll i = ; i < m; i++){ cin >> op >> x;
if(op == 'Q') {
if(x == ) {
t = ;
cout << t << endl;
} else {
t = Query(, m, len - x + , len, );
cout << t << endl;
}
} else {
len++;
Update(, m, len, (x + t) % d, );
}
}
}

---

本代码1776ms， 氧化后1276ms。

比较玄学的一件事就是用cin过了，用scanf和快读却TLE了。【滑稽】