HDU 1754(線分ツリーの問題)

I Hate It
Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4795    Accepted Submission(s): 1638
Problem Description
多くの学校では比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.
これは多くの学生に反感を抱かせた.
あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.
 
 
Input
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.
各試験の第1行には、2つの正の整数NおよびM(0学生ID番号はそれぞれ1編からNまでです.
2行目はN個の整数を含み、このN個の学生の初期成績を表し、i番目の数はIDがiの学生の成績を表す.
次はM行です.各行には1文字C('Q'または'U'のみ)と2つの正の整数A,Bがある.
Cが「Q」である場合、IDがAからB(A,Bを含む)までの学生の中で、成績が最も高いかを尋ねる質問操作であることを示す.
Cが「U」の場合、IDがAの学生の成績をBに変更する更新操作であることを示す.
 
 
Output
問合せ操作ごとに、1行に最高成績を出力します.
 
 
Sample Input

   
   
   
   

    
    
    
    5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
   
   
   
   

 
 
Sample Output

   
   
   
   

    
    
    
    5
6
5
9


    
    
    
    
 
     
 
      Hint 
     
Huge input,the C function scanf() will work better than cin 
    
    
    
    
     
   
   
   
   

 
 
Author
linle
 
 
Source
2007省大会合宿チーム練習試合(6)linleフィールド
 
 
Recommend
lcy
典型的な線分木問題~U成績を変える際はupdate関数,特に最高成績の更新に注意
#include using namespace std; #define max(a,b) a>b?a:b struct LineTree { int left,right; int highest; LineTree *lchild,*rchild; }; LineTree mem[400010]; int pos; int score[200010]; 自分で作っている間にメモリがずっと超えていて、これはネットで習ったもので、まだよく分からない{LineTree*s=&mem[pos+];returns;}LineTree*CreateTree(int a,int b)//線分木を作る{LineTree*root= NewTree();root-> left=a;root-> right=b;if(b-a>1){int mid;mid=(a+b)/2;root-> lchild=CreateTree(a,mid);root-> root->>; root-> root->>>; root-> right=b;if(a,mid);rchild=CreateTree(mid,b); root->highest=max(root->lchild->highest,root->rchild->highest); } else root->highest=max(score[root->left],score[root->right]); return root; } int search(LineTree *t,int a,int b) { if(t->left==a && t->right==b) return t->highest; int mid=(t->left+t->right)/2; if(b<=mid) return search(t->lchild,a,b); else if(mid<=a) return search(t->rchild,a,b); else { int s1,s2; s1=search(t->lchild,a,mid); s2=search(t->rchild,mid,b); return max(s1,s2); } } void update(LineTree *t,int a) { if(t->right-t->left==1) { t->highest=max(score[t->left],score[t->right]); return; } if(t->lchild->right>=a) update(t->lchild,a); if(t->rchild->left<=a) update(t->rchild,a); t->highest=max(t->lchild->highest、t->rchild->highest);return;}int main(){int n,m;LineTree*s;char ch;int a,b;while(scanf("%d%d",&n,&m)!=EOF){pos=0;///初期--!int i;int i;for(i=1;i<=n;i++)scanf("%d",&score[i]);s=CreateTree(1,n);getchar();whild();whild();whild->hild->hild->hild->hild->hild->hild->highese(m--){ch=getchar();scanf("%d%d",&a,&b);getchar();if(ch='Q'){if(a==b)printf("%d/n",score[a]); else printf("%d/n",search(s,a,b)); } else { score[a]=b; update(s,a); } } } return 0; }