最甜的苹果
蒜头君有很多苹果, 每个苹果都有对应的甜度值.
蒜头君现在想快速知道从第 i 个苹果到第 j 个苹果中, 最甜的甜度值是多少.
因为存放时间久了, 有的苹果会变甜, 有的苹果会因为腐烂而变得不甜, 所以蒜头君有时候还需要修改第 i 个苹果的甜度值. 输入格式
第一行输入两个正整数 N,M(0<N≤200000,0<M<5000), 分别代表苹果的个数和蒜头君要进行的操作的数目.
每个苹果从 1 到 N 进行编号.
接下来一行共有 N 个整数, 分别代表这 N 个苹果的初始甜度值.
接下来 M 行. 每一行有一个字符 C, 和两个正整数 X,Y.
当 C 为 Q 的时候, 你需要输出从 X 到 Y(包括 X,Y) 的苹果当中, 甜度值最高的苹果的甜度值.
当 C 为 u 的时候, 你需要把苹果 X 的甜度值更改为 Y.
思路: 线段树, 维护区间最大值. 查询, 动态修改功能.
代码:
- #include<bits/stdc++.h>
- using namespace std;
- const int MAX_N = 200000;
- int n,m;
- int s[MAX_N * 4];
- // 父节点的值 等于: 合并左右子节点的值 取最大值
- void up(int p){
- s[p] = max(s[p<<1] , s[(p<<1) + 1]);
- }
- //p 当前结点 L 边界 r 右边界 x 要更新的下标 v 要更新为的值
- void modify(int p,int l,int r,int x,int v){
- if(l == r){
- s[p] = v; // 更新
- return;
- }
- int mid = l + (r - l)/2;
- if(x <= mid){
- modify(p<<1, l, mid, x, v); // 左子树 左区间更新
- }else{
- modify((p<<1) + 1, mid + 1, r, x, v);
- }
- up(p); // 父节点合并 两个子节点
- }
- // 查询
- int query(int p,int l,int r,int x,int y){
- if(x <=l && r <=y){
- return s[p];
- }
- int mid = l + (r - l)/2,res = 0;
- if(x<=mid){
- res = max(res,query(p<<1,l,mid,x,y));
- }
- if(y>mid){
- res = max(res,query((p<<1) +1,mid+1,r,x,y));
- }
- return res;
- }
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++){
- int d;
- scanf("%d",&d);
- modify(1,1,n,i,d);
- }
- while(m--){
- char c;
- int x,y;
- scanf("%c %d %d",&c,&x,&y);
- if(c=='Q'){
- printf("%d\n",query(1,1,n,x,y));
- }else{
- modify(1,1,n,x,y);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2950748.html