AcWing 1275. 最大数

线段树不是一个算法，而是一个对区间进行修改、维护的工具。

AcWing 1275. 最大数

题目大意：

有两种操作，添加和询问。

1. 添加操作：向序列后添加一个数，序列长度变成 $n+1$；
2. 询问操作：询问这个序列中最后 $L$ 个数中最大的数是多少。

思路：

线段树板子题，维护区间最大值。

Code:

struct node{
	int l,r;
	int v;
}tr[N*4];

void build(int u,int l,int r){
	//赋值端点
	tr[u] = {l,r};
	//l == r时为叶子结点
	if (l == r)	return;
	
	int mid = l + r >> 1;
	//继续向下建树
	build(u << 1,l,mid);
	build(u << 1 | 1,mid + 1,r);
}

void pushup(int u){
	//区间最大值
	tr[u].v = max(tr[u << 1].v,tr[u << 1|1].v);
}

int query(int u,int l,int r){
	//如果包含在这个区间
	if (tr[u].l >= l && tr[u].r <= r)	return tr[u].v;
	
	int mid = (tr[u].l + tr[u].r) >> 1;
	int v = 0;
	if (l <= mid)	v = query(u << 1,l,r);
	if (r > mid)	v = max(v,query(u << 1|1,l,r));
	return v;
}

void modify(int u,int x,int v){
	if (tr[u].l == x && tr[u].r == x)	tr[u].v = v;
	else{
		int mid = tr[u].l + tr[u].r >> 1;
		if (x <= mid)	modify(u << 1,x,v);
		else modify(u << 1|1,x,v);
		pushup(u);
	}
}

void solve()
{
	cin >> m >> p;
	build(1,1,m);
	int last = 0,n = 0;
	while(m --){
		char ch;
		int x;
		cin >> ch >> x;
		if (ch == 'A')	modify(1,++n,(x + last) % p);
		else{
			last = query(1,n - x + 1,n);
			cout << last << endl;
		}
	} 
}