1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4  5 using namespace std; 6  7 const int MAX = 200010 * 4; 8 int segment[MAX]; 9 //向上调整10 void pushUp(int root)11 {12     segment[root] = max(segment[root * 2], segment[root * 2 + 1]);13 }14 15 void buildTree(int root, int left, int right)16 {17     if(left == right)18     {19         scanf("%d", &segment[root]);20         return;21     }22     int mid = (left + right) / 2;23     buildTree(root * 2, left, mid);24     buildTree(root * 2 + 1, mid + 1, right);25     //要把跟他上面所有关联的节点都要更新26     pushUp(root);27 }28 //更新节点29 void update(int root, int pos, int update_num, int left, int right)30 {31     if(left == right)32     {33         segment[root] = update_num;34         return;35     }36     int mid = (left + right) / 2;37     if(pos <= mid)38     {39         update(root * 2, pos, update_num, left, mid);40     }41     else42     {43         update(root * 2 + 1, pos, update_num, mid + 1, right);44     }45     pushUp(root);46 }47 //left和right为要查找的区间，L和R为当前查到了哪个区间48 int getMax(int root, int left, int right, int L, int R)49 {50     if(L == left && R == right)51     {52         return segment[root];53     }54     int mid = (left + right) / 2;55     int Max_Num = 0;56     if(R <= mid)57     {58         Max_Num = getMax(root * 2, left, mid, L, R);59     }60     else if(L > mid)61     {62         Max_Num = getMax(root * 2 + 1, mid + 1, right, L, R);63     }64     else65     {66         Max_Num = getMax(root * 2, left, mid, L, mid);67         Max_Num = max(Max_Num, getMax(root * 2 + 1, mid + 1, right, mid + 1, R));68     }69     return Max_Num;70 }71 72 int main()73 {74     int N, M;75     while(~scanf("%d %d", &N, &M))76     {77         memset(segment, 0, sizeof(segment));78         buildTree(1, 1, N);79         char ch;80         int t1, t2;81         for(int i = 0; i < M; i++)82         {83             getchar();84             scanf("%c %d %d", &ch, &t1, &t2);85             if(ch == ‘U‘)86             {87                 update(1, t1, t2, 1, N);88             }89             else90             {91                 printf("%d\n", getMax(1, 1, N, t1, t2));92             }93         }94     }95     return 0;96 }