1156ms
#include<iostream>
using namespace std;
#define N 200010
#define MIN -0xFFFFFFF
struct Node{
int a,b,cover;
int lc,rc;
}Tree[2*N];
int Len;
int MAX;
void build(int left,int right){
Len++;
int Now=Len;
Tree[Now].a=left; Tree[Now].b=right;
Tree[Now].cover=MIN;
Tree[Now].lc=-1;
Tree[Now].rc=-1;
if(right-left>1){
int mid=(left+right)>>1;
Tree[Now].lc=Len+1;
build(left,mid);
Tree[Now].rc=Len+1;
build(mid,right);
}
}
void insert(int Num,int left,int right,int col){
if(left==Tree[Num].a&&right==Tree[Num].b){
Tree[Num].cover=col;
return ;
}
int mid=(Tree[Num].a+Tree[Num].b)>>1,tmp;
if(right<=mid)
{
insert(Tree[Num].lc,left,right,col);
if(Tree[Tree[Num].lc].cover>Tree[Num].cover)
Tree[Num].cover=Tree[Tree[Num].lc].cover;
}
else if(left>=mid)
{
insert(Tree[Num].rc,left,right,col);
if(Tree[Tree[Num].rc].cover>Tree[Num].cover)
Tree[Num].cover=Tree[Tree[Num].rc].cover;
}
else{
insert(Tree[Num].lc,left,mid,col);
insert(Tree[Num].rc,mid,right,col);
if(Tree[Tree[Num].lc].cover>Tree[Tree[Num].rc].cover)
tmp=Tree[Tree[Num].lc].cover;
else
tmp=Tree[Tree[Num].rc].cover;
if(Tree[Num].cover<tmp)
Tree[Num].cover=tmp;
}
}
void query(int Num,int left,int right){
if(left<=Tree[Num].a&&right>=Tree[Num].b){
if(Tree[Num].cover>MAX)
MAX=Tree[Num].cover;
return;
}
int mid=(Tree[Num].a+Tree[Num].b)>>1;
if(right<=mid) query(Tree[Num].lc,left,right);
else if(left>=mid) query(Tree[Num].rc,left,right);
else{
query(Tree[Num].lc,left,mid);
query(Tree[Num].rc,mid,right);
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
Len=0;
build(0,n);
int a,b;
char c;
for(int i=1;i<=n;++i){
scanf("%d",&a);
insert(1,i-1,i,a);
}
getchar();
for(int i=0;i<m;++i){
scanf("%c%d%d",&c,&a,&b);getchar();
if(c=='Q'){
MAX=MIN;
query(1,a-1,b);
printf("%d\n",MAX);
}
else insert(1,a-1,a,b);
}
}
return 0;
}
453ms
#include<cstdio>
int Tree[1100000],A[210000];
int Z;
inline int max(int a,int b){ //加了inline速度快了好多，orz～～～
return a>b?a:b;
}
int build(int N,int l,int r){
if(r-l==1){
Tree[N]=A[r];
return Tree[N];
}
int mid=(l+r)>>1;
Tree[N]=max(build(N<<1,l,mid),build((N<<1)+1,mid,r));
return Tree[N];
}
int insert(int N,int l,int r,int a,int b){
if(l==a&&r==b){
Tree[N]=Z;
return Tree[N];
}
int mid=(l+r)>>1;
if(b<=mid)
Tree[N]=max(Tree[(N<<1)+1],insert(N<<1,l,mid,a,b));
else if(a>=mid)
Tree[N]=max(Tree[N<<1],insert((N<<1)+1,mid,r,a,b));
else
Tree[N]=max(insert(N<<1,l,mid,a,mid),insert((N<<1)+1,mid,r,mid,b));
return Tree[N];
}
int query(int N,int l,int r,int a,int b){
if(l==a&&r==b)
return Tree[N];
int mid=(l+r)>>1;
if(b<=mid)
return query(N<<1,l,mid,a,b);
else if(a>=mid)
return query((N<<1)+1,mid,r,a,b);
else
return max(query(N<<1,l,mid,a,mid),query((N<<1)+1,mid,r,mid,b));
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;++i)
scanf("%d",&A[i]);
getchar();
build(1,0,n);
int a,b;
char c;
for(int i=1;i<=m;++i){
scanf("%c %d %d",&c,&a,&b);
getchar();
if(c=='U'){
Z=b;
insert(1,0,n,a-1,a);
}
else
printf("%d\n",query(1,0,n,a-1,b));
}
}
return 0;
}
posted on 2009-04-24 00:58
xfstart07 阅读(646)
评论(0) 编辑 收藏 引用 所属分类:
代码库