POJ - 3264 Balanced Lineup [세그먼트 트리 최대치 최소치 차이
구간 내의 최대치와 최소치의 차이를 구하다
코드:
#include "iostream"
#include "cstring"
#include "cstdio"
#define maxx 50005
using namespace std;
int a[maxx<<2],sum[maxx<<2],sub[maxx<<2];
void pushup(int rt){
sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
sub[rt]=min(sub[rt<<1],sub[rt<<1|1]);
}
void Build(int l,int r,int rt){
if(l==r){
scanf("%d",&a[rt]);
sum[rt]=a[rt];
sub[rt]=a[rt];
return ;
}
int m=(l+r)>>1;
Build(l,m,rt<<1);
Build(m+1,r,rt<<1|1);
pushup(rt);
}
int sumQuery(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return sum[rt];
}
int m=(l+r)>>1;
int sumn=0;
if(L<=m)
sumn=max(sumn,sumQuery(L,R,l,m,rt<<1));
if(R>m)
sumn=max(sumn,sumQuery(L,R,m+1,r,rt<<1|1));
return sumn;
}
int subQuery(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return sub[rt];
}
int m=(l+r)>>1;
int ans=1000010;
if(L<=m)
ans=min(ans,subQuery(L,R,l,m,rt<<1));
if(R>m)
ans=min(ans,subQuery(L,R,m+1,r,rt<<1|1));
return ans;
}
int main(){
int N,M,c,d;
scanf("%d%d",&N,&M);
Build(1,N,1);
while(M--){
scanf("%d%d",&c,&d);
int summ=sumQuery(c,d,1,N,1);
int subb=subQuery(c,d,1,N,1);
// cout<이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #510 (Div. 2) D. Petya and Array 좌압과 세그먼트 트리문제는 바꿔 말하면, 구간 $[l, r)$의 부분합이 $t$ 미만의 부분합이 되는, $l,r$의 수를 요구하고 싶다. 즉, $a_0$에서 있는 $a_i$까지의 합을 index로, 출현 횟수를 값으로 하는 세그먼트 트...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
