#pragma comment(linker, "/STACK:102400000,102400000")//#include#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair pii;typedef vector vi;const double eps &＃61; 1e-8; const int INF &＃61; 1e9&＃43;7; const ll inf &＃61;(1LL<<62) ;const int MOD &＃61; 1e9 &＃43; 7; const ll mod &＃61; (1LL<<32);const int N &＃61;1e6&＃43;6; const int M&＃61;100010;const int maxn&＃61;200010;#define mst(a) memset(a, 0, sizeof(a))#define M_P(x,y) make_pair(x,y)#define in freopen("in.txt","r",stdin) #define rep(i,j,k) for (int i &＃61; j; i <&＃61; k; i&＃43;&＃43;) #define per(i,j,k) for (int i &＃61; j; i >&＃61; k; i--) #define lson l , mid , rt <<1 #define rson mid &＃43; 1 , r , rt <<1 | 1 const int lowbit(int x) { return x&-x; }//const int lowbit(int x) { return ((x)&((x)^((x)-1))); } int read(){ int v &＃61; 0, f &＃61; 1;char c &＃61;getchar();while( c <48 || 57 while(48 <&＃61; c && c <&＃61; 57) v &＃61; v*10&＃43;c-48, c &＃61; getchar();return v*f;}int MAX[maxn<<2];void pushup(int rt) //把当前结点的信息更新到父结点{//线段树是用数组来模拟树形结构//对于每一个节点rt,左子节点为 2*rt (一般写作rt<<1)右子节点为 2*rt&＃43;1&＃xff08;一般写作rt<<1|1&＃xff09; MAX[rt] &＃61; max(MAX[rt<<1] , MAX[rt<<1|1]); }void build(int l,int r,int rt){if(l&＃61;&＃61;r){scanf("%d",&MAX[rt]); return;}int mid&＃61;(l&＃43;r)>>1;build(lson);//递归构造左子树build(rson);//递归构造右子树pushup(rt); //更新求和 }void update(int p, int change, int l, int r, int rt)//单点替换 {if(l&＃61;&＃61;r){MAX[rt] &＃61; change; return ;}int mid&＃61;(l&＃43;r) >> 1;if(p<&＃61;mid) update(p,change,lson);else update(p,change,rson);pushup(rt);}int query(int L,int R,int l,int r,int rt) //区间最值 {if(L <&＃61; l && r <&＃61; R){return MAX[rt];}int mid &＃61; (l&＃43;r)>>1;int ans &＃61; 0;if(L <&＃61; mid) ans&＃61;max(ans,query(L,R,lson));if(R > mid) ans&＃61;max(ans,query(L,R,rson));return ans; }int main(){int n,m;while(~scanf("%d%d",&n,&m)){build(1,n,1);while(m--){char op[3];int a,b;scanf("%s%d%d",op,&a,&b);if(op[0]&＃61;&＃61;&＃39;Q&＃39;)printf("%d\n",query(a,b,1,n,1));else update(a,b,1,n,1);}}return 0;}
京公网安备 11010802041100号