题解
多次单点修改加上多次区间查询
线段树
code
#include<bits/stdc++.h>
using namespace std;
int tree[800005]={0};
int a[200005]={0};
void build(int node,int l,int r)
{
if(l==r)
{
tree[node]=a[l];
return;
}
int mid=(l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
void update(int node,int l,int r,int x,int y,int val)
{
if(l>y||r<x)return;
if(l==x&&r==y)
{
tree[node]=max(tree[node],val);
return;
}
int mid=(l+r)/2;
update(node*2,l,mid,x,y,val);
update(node*2+1,mid+1,r,x,y,val);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
int query(int node,int l,int r,int x,int y)
{
if(l>y||r<x)return 0;
if(l>=x&&r<=y) return tree[node];
int mid=(l+r)/2;
return max(query(node*2,l,mid,x,y),query(node*2+1,mid+1,r,x,y));
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(m--)
{
char op;
int x,y;
cin>>op>>x>>y;
if(op=='U') update(1,1,n,x,x,y);
else cout<<query(1,1,n,x,y)<<endl;
}
return 0;
}
标签:node,P1531,int,tree,mid,build,Hate,op
From: https://www.cnblogs.com/pure4knowledge/p/18024087