hdu 1754-白红宇

hdu 1754

阅读量：7001 次

发布时间：2019-06-27

本文共 2349 字，大约阅读时间需要 7 分钟。

/*ID:billat11LANG:CTASK:namenum*/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=200005;struct Node{ int left; int right; int maxScore; int score;}allNode[4*N];int data[N+5];inline int max(int a,int b){ //加了inline速度快了好多，orz～～～ return a>b?a:b;}void build(int l,int r,int n){ if(l==r)//leaf node { allNode[n].left=l; allNode[n].right=r; allNode[n].maxScore=allNode[n].score=data[l]; } else//not leaf node { int mid=(l+r)>>1; allNode[n].left=l; allNode[n].right=r; build(l,mid,2*n); build(mid+1,r,2*n+1); allNode[n].maxScore=max(allNode[2*n].maxScore,allNode[2*n+1].maxScore); }}void print(int l,int r,int n){ if(l==r) { printf("left:%d right:%d max:%d\n",l,r,allNode[n].maxScore); } else { int mid=(l+r)>>1; print(l,mid,2*n); print(mid+1,r,2*n+1); printf("left:%d right:%d max:%d\n",l,r,allNode[n].maxScore); }}int query(int l,int r,int n){ int mid=(allNode[n].left+allNode[n].right)>>1; if((allNode[n].left==l)&&(allNode[n].right==r)) return allNode[n].maxScore; else { if((r<=mid)&&(l>=allNode[n].left)) return query(l,r,2*n); else if((l>mid)&&(r<=allNode[n].right)) return query(l,r,2*n+1); else if((l<=mid)&&(r>mid)) return max(query(l,mid,2*n),query(mid+1,r,2*n+1)); }}void update(int n,int d,int alln){ int mid=(allNode[alln].left+allNode[alln].right)>>1; if((allNode[alln].left==n)&&(allNode[alln].right==n)) { allNode[alln].maxScore=d; int newn=alln>>1; while(newn>=1) { allNode[newn].maxScore=max(allNode[2*newn].maxScore,allNode[2*newn+1].maxScore); newn=newn>>1; } } else { if(n<=mid) update(n,d,2*alln); else if(n>mid) update(n,d,2*alln+1); } /* if(allNode[alln].left==allNode[alln].right) { allNode[alln].maxScore=d; } else { if(n<=mid) update(n,d,2*alln); else if(n>mid) update(n,d,2*alln+1); allNode[alln].maxScore=max(allNode[2*alln].maxScore,allNode[2*alln+1].maxScore); } * */}int main(){ int n,m; char op; while(scanf("%d %d",&n,&m)==2) { for(int i=1;i<=n;i++) scanf("%d",&data[i]); build(1,n,1); //print(1,n,1); for(int i=1;i<=m;i++) { int l,r; scanf("\n%c%d%d",&op,&l,&r); if(op=='Q') { int ans=query(l,r,1); printf("%d\n",ans); } else if(op=='U') { update(l,r,1); } } } //system("pause"); return 0;}