//回憶系列..
1
//segment tree template
2#include <iostream>
3
4using namespace std;
5
struct 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
小果子 閱讀(375)
評論(0) 編輯 收藏 引用 所屬分類:
Acm