信息学奥赛一本通 1549：最大数 | 洛谷 P1198 [JSOI2008] 最大数

【题目链接】

ybt 1549：最大数
洛谷 P1198 [JSOI2008] 最大数

【题目考点】

1. 线段树：单点修改 区间查询

知识点讲解见：洛谷 P3374 【模板】树状数组 1（线段树解法）

【解题思路】

本题为设线段树维护区间最值，进行单点修改，区间查询。
每次操作可以是查询末尾L个数的最大值，或者在末尾添加一个数，一共进行m次操作，那么添加数的数量不超过m。
可以设初始存在一个长为m的序列，初值都为0。对该长为m的序列构建线段树，维护区间最大值。
已经实际添加是数的个数设为n，初值为0。

• 如果要查询末尾l个数的最大值，则使用线段树查询区间$[n-l+1,n]$中的最大值，结果保存在变量t，并将t输出。
• 如果要添加数据，设输入为"A n"，使用变量a保存输入的’n’的值。那么要插入的数值为输入的值a，加上上一次查询到的值t，再对d取模，为(a+t)%d。由于输入的值a以及上次查询的值都可能接近$2\ast 10^9$，因此需要将a与t转为long long类型相加，而后再对d取模。
  先将n增加1，此时序列第n元素为初值0。而后就需要让序列的第n元素增加(a+t)%d，使用线段树进行单点修改。

【题解代码】

• 解法1：线段树

#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define INF 0x3f3f3f3f
struct Node
{int val, l, r, m;
} tree[4*N];
void pushUp(int i)
{tree[i].val = max(tree[2*i].val, tree[2*i+1].val);
}
void build(int i, int l, int r)
{tree[i].l = l, tree[i].r = r, tree[i].m = l+r>>1;if(l == r)//tree[i].val = 0return;build(2*i, l, tree[i].m);build(2*i+1, tree[i].m+1, r);pushUp(i);
}
void update(int i, int x, int v)//a[x] += v
{if(tree[i].l == tree[i].r){tree[i].val += v;return;}if(x <= tree[i].m)update(2*i, x, v);elseupdate(2*i+1, x, v);pushUp(i);
}
int query(int i, int l, int r)
{if(tree[i].l > r || tree[i].r < l)return -INF;if(l <= tree[i].l && tree[i].r <= r)return tree[i].val;return max(query(2*i, l, r), query(2*i+1, l, r));
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n = 0, t = 0, a, m, d, l;char c;cin >> m >> d;build(1, 1, m);while(m--){cin >> c;if(c == 'Q'){cin >> l;t = query(1, n-l+1, n);cout << t << '\n';}else //c == 'A'{cin >> a;update(1, ++n, ((long long)t+a)%d);//t+a可能超过int范围 }}return 0;
}