hdu1754(线段数维护区间最大值) - c++编程基础

题意：给定1-n(n<=200000)个数，然后动态改变一些值，并动态询问区间最大值。

解法：裸的线段树，赛前默写模版回忆下线段树代码。仍然要注意：线段树节点数组一定要开到节点数的三倍长度。

代码：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=300000*3; const int INF=1000000007; struct node { node* pleft,*pright; int l,r; int ma; } nodes[Max]; int num[Max]; int tot=0; void buildtree(node* p,int left,int right) { p->l=left; p->r=right; if(left==right) return; int mid=(left+right)/2; tot++; p->pleft=nodes+tot; buildtree(p->pleft,left,mid); tot++; p->pright=nodes+tot; buildtree(p->pright,mid+1,right); } int n,m; int update(node* p,int add,int value) { if(p->l==p->r) { p->ma=value; return value; } int mid=(p->l+p->r)/2; if(add<=mid) update(p->pleft,add,value); else update(p->pright,add,value); return p->ma=max(p->pleft->ma,p->pright->ma); } int query(node* p,int left,int right) { if(p->l==left&&p->r==right) return p->ma; int mid=(p->l+p->r)/2; if(right<=mid) return query(p->pleft,left,right); if(left>=mid+1) return query(p->pright,left,right); return max(query(p->pleft,left,mid),query(p->pright,mid+1,right)); } int main() { while(scanf("%d%d",&n,&m)==2) { tot=0; buildtree(nodes,1,n+1); for(int i=1; i<=n; i++) { scanf("%d",num+i); update(nodes,i,num[i]); } for(int i=0;i
              
               >c; if(c=='Q') { int l,r;scanf("%d%d",&l,&r); printf("%d\n",query(nodes,l,r)); } else { int l,r;scanf("%d%d",&l,&r); update(nodes,l,r); } } } return 0; }