xiaoguozi's Blog
Pay it forword - 我并不觉的自豪,我所尝试的事情都失败了······习惯原本生活的人不容易改变,就算现状很糟,他们也很难改变,在过程中,他们还是放弃了······他们一放弃,大家就都是输家······让爱传出去,很困难,也无法预料,人们需要更细心的观察别人,要随时注意才能保护别人,因为他们未必知道自己要什么·····

//回忆系列..

  1//segment tree template
  2#include <iostream>
  3
  4using namespace std;
  5struct Tnode{
  6    //point left,right child
  7    Tnode *lc,*rc;
  8    //segment devide
  9    int left,right;
 10
 11    //extra
 12    int maxval;
 13
 14    //construct function
 15    Tnode(int data=0,int l=0,int r=0,Tnode*lp=0,Tnode*rp=0)
 16            :left(l),right(r),lc(lp),rc(rp){
 17                maxval=0;
 18    }
;
 19}
;
 20
 21//maxsize number of Tnode
 22const int N=200002;
 23int score[N];
 24
 25//static allocate memory for Tnode [a,b] node_size=2*(b-a)+1 for [i,i+1]
 26Tnode node[N<<1];
 27//count for usage Tnode array
 28int cnt=0;
 29
 30//make a new node ,return Tnode*
 31Tnode* new_node(){
 32    Tnode* p=&node[cnt++];
 33    memset(p,0,sizeof(Tnode));
 34    return p;
 35}

 36
 37//make tree ,return Tnode* which is root
 38//parament: [left,right]
 39Tnode* make_tree(int left,int right){
 40    //make a new Tnode 
 41    Tnode* root=new_node();
 42    //Initial the Tndoe
 43    root->left=left,root->right=right;
 44    
 45    if(left==right){//[i,i] 
 46        //root->data=score[left];//initial the Tnode data
 47        return root;
 48    }
else{
 49        int mid=(left+right)>>1;
 50        root->lc=make_tree(left,mid);
 51        root->rc=make_tree(mid+1,right);
 52        return root;
 53    }

 54}

 55Tnode* UpdateData(Tnode* root,int left,int right,int val){
 56    if(root->left==root->right){
 57        root->maxval=val;
 58        return root;
 59    }

 60    int mid=(root->left+root->right)>>1;
 61    Tnode *rc=0,*lc=0;
 62    if(mid>=right){
 63        lc=UpdateData(root->lc,left,right,val);
 64    }
else if(mid<left){
 65        rc=UpdateData(root->rc,left,right,val);
 66    }
else{
 67        lc=UpdateData(root->lc,left,mid,val);
 68        rc=UpdateData(root->rc,mid+1,right,val);
 69    }

 70
 71    int leftmax=0,rightmax=0;
 72    if(lc!=0)leftmax=lc->maxval;
 73    if(rc!=0)rightmax=rc->maxval;
 74
 75    int curmax=leftmax>rightmax?leftmax:rightmax;
 76    root->maxval=curmax>root->maxval?curmax:root->maxval;
 77
 78    return root;
 79}

 80int QueryMax(Tnode* root,int left,int right){
 81    if(root->left>=left&&root->right<=right){
 82        return root->maxval;
 83    }

 84    int mid=(root->left+root->right)>>1;
 85    int l=0,r=0;
 86    if(mid<left){
 87        r=QueryMax(root->rc,left,right);
 88    }
else if(mid>=right){
 89        l=QueryMax(root->lc,left,right);
 90    }
else{
 91        l=QueryMax(root->lc,left,mid);
 92        r=QueryMax(root->rc,mid+1,right);
 93    }

 94    return l>r?l:r;
 95}

 96
 97
 98int main()
 99{
100    int n,m;
101    while(scanf("%d%d",&n,&m)!=EOF){
102        cnt=0;
103        Tnode *root=make_tree(1,n);
104        for(int i=1;i<=n;i++){
105            scanf("%d",&score[i]);
106            UpdateData(root,i,i,score[i]);
107        }

108        char command;
109        int a,b;
110        getchar();
111        for(int i=0;i<m;i++){
112            scanf("%c %d %d",&command,&a,&b);
113            switch(command){
114                case 'Q':
115                    printf("%d\n",QueryMax(root,a,b));
116                    break;
117                case 'U':
118                    UpdateData(root,a,a,b);
119                    break;
120                default:
121                    break;
122            }
;
123            getchar();
124        }

125    }

126    return 0;
127}
posted on 2009-03-08 15:35 小果子 阅读(364) 评论(0)  编辑 收藏 引用 所属分类: Acm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理