题意:给n(1<=n<=200000)个人的初始成绩,现在要实时更新修改某一个人的成绩,查询[l , r]区间内成绩的最大值。
具体参看:http://www.cnblogs.com/ambition/archive/2011/04/06/bit_rmq.html
Sure原创,转载请注明出处
#include <iostream> #include <cstdio> #include <memory.h> #define MAX(a , b) ((a) > (b) ? (a) : (b)) using namespace std; const int maxn = 200002; int num[maxn],maxval[maxn]; //maxval[i] 表示 [i-lowbit(i)+1 , i]区间内的最大值 int m,n; void read() { for(int i=1;i<=n;i++) { scanf("%d",&num[i]); } return; } inline int lowbit(int x) { return x & (-x); } void init() //初始化maxval[] < nlogn { for(int i=1;i<=n;i++) { maxval[i] = num[i]; for(int j=1;j<lowbit(i);j <<= 1) { maxval[i] = MAX(maxval[i] , maxval[i-j]); } } return; } void update(int pos,int val) //把pos位值更新为val logn { num[pos] = val; for(int i=pos;i<=n;i+=lowbit(i)) { maxval[i] = val; for(int j=1;j<lowbit(i);j <<= 1) { maxval[i] = MAX(maxval[i] , maxval[i-j]); } } return; } int query(int l,int r) //询问[l,r]区间最大值 logn { int ans = num[r]; while(true) { ans = MAX(ans , num[r]); if(l == r) break; for(r -= 1;r-l >= lowbit(r);r -= lowbit(r)) { ans = MAX(ans , maxval[r]); } } return ans; } void solve() { char str[3]; int x,y; while(m--) { scanf("%s %d %d",str,&x,&y); if(str[0] == 'U') update(x,y); else printf("%d\n",query(x,y)); } return; } int main() { while(~scanf("%d %d",&n,&m)) { read(); init(); solve(); } return 0; }