参考例题:http://acm.split.hdu.edu.cn/showproblem.php?pid=1754
参考代码:
#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; }
Hello! Do you use Twitter? I’d like to follow you if that would be ok. I’m absolutely enjoying your blog and look forward to new posts.
Great line up. We will be linking to this great article on our site. Keep up the good writing.