hdoj 1754 【线段树】

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define LS(x) (x<<1)
#define RS(x) (x<<1|1)
#define
P(x) (x>>1)
#define MAXLEN 200005
#define PAUSE system("pause")
using namespace std;
int a[MAXLEN<<2];
int n;
void buildTree(int l, int r, int pos)
{
if(l == r)
{
scanf("%d", &a[pos]);
return;
}
int mid = (l+r)>>1;
buildTree(l,
mid, LS(pos));
buildTree(mid+1, r, RS(pos));
a[pos] = max(a[LS(pos)], a[RS(pos)]);
}
int updata(int p, int l, int r, int v, int pos)
{
int mid;
do{
mid = (l+r)>>1;
if(mid >= p)	{	r = mid;	pos = LS(pos);	}
else
{	l = mid+1;	pos = RS(pos);	}
}while(l != r);
a[pos] = v;
do{
pos = P(pos);
a[pos] = max(a[LS(pos)], a[RS(pos)]);
}while(pos != 1);
}
int L, R;
int query(int l, int r, int pos)
{
if(L <= l && r <= R)	return a[pos];
int amax = 0;
int mid = (l+r)>>1;
if(L <= mid)	amax = max(amax, query(l,
mid, LS(pos)));
if(R >
mid)	amax = max(amax, query(mid+1, r, RS(pos)));
return amax;
}
int main()
{
int q;
while(scanf("%d%d", &n, &q) != EOF)
{
buildTree(1, n, 1);
int a, b;
char ch;
while(q--)
{
scanf(" %c%d%d", &ch, &a, &b);
if(ch == 'Q')
{
L = a;
R = b;
printf("%dn", query(1, n, 1));
}
else if(ch == 'U')
updata(a, 1, n, b, 1);
}
}
return 0;
}

最后

以上就是悦耳糖豆为你收集整理的hdoj 1754 【线段树】的全部内容，希望文章能够帮你解决hdoj 1754 【线段树】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。