구간 최소 값(2)(선분 수 갱신 구간)2015 년 JXNUACS 알고리즘 그룹 여름방학 첫 주 경기
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 26 Accepted Submission(s) : 9
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
숫자 시퀀스 와 일부 조작 을 지정 하고 주어진 구간 내 숫자의 최소 값 을 조회 합 니 다.
Input
여러 조 의 테스트 데 이 터 를 포함 하여 최대 5 조 를 입력 하 십시오.
여러 그룹의 테스트 용례 를 포함 하 는 것 을 입력 하 십시오.각 그룹의 테스트 용례 의 시작 은 하나의 정수 n(1<=n<=100000)이 고 디지털 서열 의 길 이 를 대표 합 니 다.
다음 줄 은 n 개의 숫자 를 주 고 숫자 서열 을 나타 낸다.숫자 는 int 범위 내 에 있다.
다음 행동 의 정수 t(1<=t<=10000)는 조작 횟수 를 나타 낸다.
마지막 으로 t 줄 은 줄 마다 하나의 조작 을 제공 합 니 다.1 l r 는 조회 구간[l,r]의 최소 값 을 대표 합 니 다.0 l r c 는 구간[l r]의 값 을 모두 c(1<=l<=r<=n)로 바 꾸 고 c 는 성형 범위 내 에 있 습 니 다.
Output
모든 조회 에 대해 출력 구간[l,r]내의 최소 값 입 니 다.
Sample Input
5
1 2 3 4 5
7
1 1 5
0 1 3 6
1 1 4
1 2 3
0 2 2 0
1 1 2
1 3 5
Sample Output
1
4
6
0
4
Author
오 영
Statistic | Submit | Back
5 분 늦 어서 야 했 어 요.맞 는 것 같 애.제출 은 못 했 지만
하루 종일 찾 았 는데TM 나 는 마침내 어떻게 하 는 지 찾 았 다.오전 에는 사실 구간 을 어떻게 갱신 하 는 지 알 고 있 었 는데,단지 한 곳 에서 잘못 썼 을 뿐이다.
결 과 를 잘못 만 들 고 포기 했다.
오늘 오후 에 그렇게 많이 시 도 했 는데o()^)o.
<pre name="code" class="cpp">#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int num[100005];
struct node
{
int left,right,val;
}c[100005*4];
void build_tree(int l,int r,int root)
{
c[root].left=l;
c[root].right=r;
if(l==r)
{
c[root].val=num[l];
return ;
}
int mid=(l+r)/2;
build_tree(l,mid,root*2);
build_tree(mid+1,r,root*2+1);
c[root].val=min(c[root*2].val,c[root*2+1].val);
}
void find_tree(int l,int r,int &min1,int root)
{
if(c[root].left==l&&c[root].right==r)
{
min1=c[root].val;
return ;
}
int mid=(c[root].left+c[root].right)/2;
if(mid<l)
find_tree(l,r,min1,root*2+1);
else if(mid>=r)
find_tree(l,r,min1,root*2);
else
{
int min2;
find_tree(l,mid,min1,root*2);
find_tree(mid+1,r,min2,root*2+1);
min1=min(min1,min2);
}
}
void update_tree(int l,int r,int x,int root)
{
if(c[root].left==c[root].right)
{
c[root].val=x;
return ;
}
int mid=(c[root].left+c[root].right)/2;
if(mid<l)
update_tree(l,r,x,root*2+1);
else if(mid>=r)
update_tree(l,r,x,root*2);
else
{
update_tree(l,mid,x,root*2);
update_tree(mid+1,r,x,root*2+1);
}
c[root].val=min(c[root*2].val,c[root*2+1].val);
}
int main()
{
int n,k;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
build_tree(1,n,1);
scanf("%d",&k);
while(k--)
{
int a,b,min1,flag;
scanf("%d",&flag);
if(flag)
{
scanf("%d %d",&a,&b);
find_tree(a,b,min1,1);
printf("%d
",min1);
}
else
{
int x;
scanf("%d %d %d",&a,&b,&x);
update_tree(a,b,x,1);
//for(int i=1;i<=9;i++)
//printf("[%d %d] %d
",c[i].left,c[i].right,c[i].val);// 。。
}
}
}
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에 따라 라이센스가 부여됩니다.