admin 管理员组

文章数量: 887021

海报

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 200002
#define ll __int64//线段树入门作,执行更改某个值,找到区间最大值的操作 
using namespace std;
ll num[maxn];
struct node
{ll max,l,r;
}tree[maxn*20];ll build(ll root,ll left,ll right)//建的时候就记录max 
{tree[root].l=left;tree[root].r=right;if(tree[root].l==tree[root].r){tree[root].max=num[left];//cout<<tree[root].max<<endl;return tree[root].max;}else{ll mid=(left+right)/2;ll a=build(root*2,left,mid);ll b=build(root*2+1,mid+1,right);tree[root].max=max(a,b); //cout<<max(a,b)<<endl;return max(a,b);}}ll find(ll root,ll left,ll right)//找的时候不能换left,right 
{//cout<<tree[root].l<<" "<<tree[root].r<<endl;//cout<<left<<" "<<right<<endl;if((tree[root].l>right)||(tree[root].r<left))return 0;if((left<=tree[root].l)&&(tree[root].r<=right)){//cout<<tree[root].max<<endl;return tree[root].max;}ll a=find(root*2,left,right);ll b=find(root*2+1,left,right);return max(a,b); 
}ll update(ll root,ll pos,ll val)//更新后还要更新以上区间的值,换pos点为val 
{if(tree[root].l==tree[root].r&&tree[root].l==pos)//考虑情况要全面 {tree[root].max=val;//cout<<tree[root].max<<" "<<tree[root].l<<endl;return tree[root].max;}if(tree[root].l>pos||tree[root].r<pos) return tree[root].max;ll a=update(root*2,pos,val);ll b=update(root*2+1,pos,val);tree[root].max=max(a,b);return tree[root].max;
}
int main()
{ll n,m;while(~scanf("%I64d%I64d",&n,&m)){for(int i=1;i<=n;i++)scanf("%I64d",&num[i]);build(1,1,n);//cout<<tree[1].max<<endl;char c;ll x,y; for(int i=1;i<=m;i++){getchar () ;  scanf ("%c%I64d%I64d", &c, &x, &y) ;  if (c == 'Q')  {  printf ("%d\n", find (1, x, y)) ;  }  else  {  num[x] = y ;  update (1, x, y) ;  }  }}} 

本文标签: 海报