【模板库】Fenwick Tree RMQ version

参考例题: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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注