poj 3264 Balanced Lineup(RMQ 선분 트 리)
제목:n 개 수 를 입력 하고 m 개의 질문 이 있 습 니 다.각 질문 은 l,r 를 입력 하고 구간[l,r]사이 의 최대 수 와 최소 수의 차 이 를 구 합 니 다.
생각:
내 가 사용 하 는 선분 트 리 는 노드 에 두 개의 도 메 인 을 추가 하여 이 구간 의 최대 치 와 최소 치 를 각각 기록 합 니 다.그리고 전역 변수 maxh 와 minh 동적 유지보수 구간[l,r]의 최대 값 과 최소 값 을 설정 합 니 다.
하지만 선분 수 는 시간 이 보통 느 리 지 않 아 요.3s+...
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 50005;
struct line
{
int l;
int r;
int minh;
int maxh;
}tree[maxn<<2];
int a[maxn];
int maxh;
int minh;
void build(int v, int l, int r)
{
tree[v].l = l;
tree[v].r = r;
if(l == r)
{
tree[v].maxh = a[l];
tree[v].minh = a[l];
return;
}
int mid = (l+r)>>1;
build(v*2,l,mid);
build(v*2+1,mid+1,r);
tree[v].maxh = max(tree[v*2].maxh,tree[v*2+1].maxh);
tree[v].minh = min(tree[v*2].minh,tree[v*2+1].minh);
}
void query(int v, int l, int r)
{
if(tree[v].l == l && tree[v].r == r)
{
maxh = max(maxh,tree[v].maxh); //maxh，minh
minh = min(minh,tree[v].minh);
return;
}
int mid = (tree[v].l+tree[v].r)>>1;
if(r <= mid)
query(v*2,l,r);
else
{
if(l > mid)
query(v*2+1,l,r);
else
{
query(v*2,l,mid);
query(v*2+1,mid+1,r);
}
}
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
build(1,1,n);
int l,r;
while(m--)
{
scanf("%d %d",&l,&r);
maxh = 0;
minh = INF; //
query(1,l,r);
printf("%d
",maxh-minh);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU - 1166 - 적병 포진 (나무형 수조 또는 선분 수)C 국 의 앙 숙 A 국 은 그동안 군사훈련 을 하고 있 었 기 때문에 C 국 간첩 두목 인 데 릭 과 그의 수하 인 티 디 는 또 바 빠 지기 시작 했다.A 국 가 는 해안선 을 따라 직선 으로 N 개 공병 캠프 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
