线段树模板

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e5+5;
struct node{
	int val;
	int l, r;
}tr[N * 4];
int m, p, n, a;
void build(int x, int l, int r){
	tr[x].l = l, tr[x].r = r;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(x << 1, l, mid);  //建立左边的树
	build(x << 1 | 1, mid + 1, r);  //建立右边的树
}

//想插入第x个数字k
void update(int rt, int x, int k){
	if(tr[rt].l == tr[rt].r){  //当前结点就是第x个叶节点
		tr[rt].val = k;
		return;
	}
	int mid = (tr[rt].l + tr[rt].r) >> 1;  
	if(x <= mid) update(rt << 1, x, k);  //想要插入的位置在左边
	else update(rt << 1 | 1, x, k);   //想要插入的位置在右边
	tr[rt].val = max(tr[rt << 1].val, tr[rt << 1 | 1].val);  //向上更新最大值
}

int query(int rt, int l, int r){
	//查询的范围完全包含了tr结点的管辖范围
	if(tr[rt].l >= l && tr[rt].r <= r) return tr[rt].val;
	int ans = 0;
	int mid = (tr[rt].l + tr[rt].r) >> 1;
	if(l <= mid) ans = max(ans, query(rt << 1, l, r));
	if(r > mid) ans = max(ans, query(rt << 1 | 1, l, r));
	return ans;
}
signed main(){
	cin >> m >> p;
	//建树
	build(1, 1, m);  //根，根的左边范围，根的右边范围
	//m次操作
	while(m--){
		char s;
		int l;
		cin >> s >> l;
		if(s == 'A'){
			//更新树:根节点是1，插入第n个数字，插入的数字是(l+a)%p
			update(1, ++n, (l + a) % p);
		}
		else{
			//查询最后l个数字的最大值,查询范围就是[n-l+1, n]
			a = query(1, n-l+1, n);
			cout << a << endl;
		}
	}
	return 0;
}