HDU 1754 선분 트 리
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int dmax=4001000;
int c[dmax],a[dmax];
void create(int x,int l,int r){
int mid=(l+r)>>1;
if (l==r){
c[x]=a[mid];
return;
}
create(x*2,l,mid);
create(x*2+1,mid+1,r);
c[x]=max(c[x*2],c[x*2+1]);
}
void change(int x,int l,int r,int s,int t){
int mid=(l+r)>>1;
if (r<s || l>s)
return;
if (l==r){
c[x]=t;
return;
}
change(x*2,l,mid,s,t);
change(x*2+1,mid+1,r,s,t);
c[x]=max(c[x*2],c[x*2+1]);
}
int call(int x,int l,int r,int s,int t){
int mid=(l+r)>>1;
if (l==s && r==t)
return c[x];
if (t<=mid)
return call(x*2,l,mid,s,t);
else{
if (s>mid)
return call(x*2+1,mid+1,r,s,t);
else{
int p=call(x*2,l,mid,s,mid);
int q=call(x*2+1,mid+1,r,mid+1,t);
return max(p,q);
}
}
}
int main(){
int i,j,k,m,n,x,y;
char tmp;
while(scanf("%d%d",&n,&m)!=EOF){
memset(c,0,sizeof(c));
memset(c,0,sizeof(a));
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
getchar();
create(1,1,n);
for (i=1;i<=m;i++){
tmp=getchar();
if (tmp=='U'){
scanf("%d%d",&x,&y);
a[x]=y;
change(1,1,n,x,y);
}else{
scanf("%d%d",&x,&y);
printf("%d
",call(1,1,n,x,y));
}
getchar();
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
