#include<iostream>
#include<stdio.h>
using namespace std;
const int maxa=200005;
int val[maxa];
struct tree{int max, left, right;
}tree[maxa*3];
int create(int root,int left,int right) //root的*2和*2+1分别存root的前后部分
{
tree[root].left=left;
tree[root].right=right;
if(left==right)
return tree[root].max=val[left];
int a,b,mid=(left+right)/2;
a=create(root*2,left,mid);
b=create(root*2+1,mid+1,right);
return tree[root].max=max(a,b);
}
int change(int root,int pos,int vall) //当root代表的是改变的点时直接改变tree[root].max,其他与建树部分相同
{
if(pos<tree[root].left||tree[root].right<pos)
return tree[root].max;
if(pos==tree[root].right&&pos==tree[root].left)
return tree[root].max=vall;
int a,b;
a=change(root*2,pos,vall);
b=change(root*2+1,pos,vall);
return tree[root].max=max(a,b);
}
int query(int root,int left,int right)
{
if(tree[root].left>right||tree[root].right<left) //root范围与查询范围没有任何交集时return 0;
return 0;
if(tree[root].left>=left&&tree[root].right<=right) //root范围完全在查询范围时return tree[root].max;
return tree[root].max;
int a,b; //其他与建树部分相同
a=query(root*2,left,right);
b=query(root*2+1,left,right);
return max(a,b);
}
int main()
{
//freopen("input.cpp","r",stdin);
int n,m;
char a;
int x,y;
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&val[i]);
}
create(1,1,n);
while(m--)
{
scanf("\n%c",&a);
scanf("%d%d",&x,&y);
if(a=='Q')
{
printf("%d\n",query(1,x,y));
}
else
change(1,x,y);
}
}
}
相关文章
- 10-06leetcode [102. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
- 10-06CF 120F Spider 树的直径 简单题
- 10-06Beautiful选择器/遍历文档树Day3-7
- 10-06[原]HDU-1598-find the most comfortable road(暴力枚举+Kruskal最小生成树)
- 10-06[HDU4348]To the moon(主席树+标记永久化)
- 10-06梯度提升决策树GBDT
- 10-06cf 383C Propagating tree - dfs序 + 线段树
- 10-06【bzoj5072】[Lydsy十月月赛]小A的树 树形背包dp
- 10-06按之字形顺序打印二叉树 牛客网 剑指Offer
- 10-06树链剖分