题目传送门:http://acm.split.hdu.edu.cn/showproblem.php?pid=1754
中文题面:http://blog.csdn.net/scnu_jiechao/article/details/8574166
其实我是来水BIT的
#include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #define LL long long #define abs(x) ((x)>0?(x):-(x)) using namespace std; const int N = 200000+9; const int INF = 1000000000; int n,m; char pat[10]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); return ret*f; } namespace Fenwick_Tree{ #define BIT Fenwick_Tree #define lowbit(x) ((x)&(-(x))) int MX[N],arr[N]; inline void init(){ for (int i=1;i<=n;i++) MX[i] = -INF; } inline void modify(int pos, int val){ int pre = arr[pos]; arr[pos] = val; if (val >= pre) { for (int i=pos;i<=n;i+=lowbit(i)) MX[i] = max(MX[i],val); } else { for (int i=pos;i<=n;i+=lowbit(i)) { MX[i] = arr[i]; for (int j=lowbit(i)/2;j;j>>=1) MX[i] = max(MX[i],MX[i-j]); } } } inline int query(int l, int r) { int ret = -INF; while (r >= l) { if (r-lowbit(r)+1 >= l) ret = max(ret, MX[r]), r -= lowbit(r); else ret = max(ret, arr[r]), r--; } return ret; } }; int main(){ while (~scanf("%d%d",&n,&m)) { BIT::init(); for (int i=1;i<=n;i++) BIT::modify(i,read()); for (int i=1,l,r;i<=m;i++) { scanf("%s",pat+1); if (pat[1] == 'Q') l = read(), r = read(), printf("%d\n",BIT::query(l,r)); else l = read(), r = read(), BIT::modify(l, r); } } return 0; }