Блог пользователя Karaev_Marik

Автор Karaev_Marik, история, 9 лет назад, По-русски

Привет Codeforces! Я попытался реализовать дерево отрезков для минимума... Вроде все компилируется, но при запуске программа аварийно завершается (например, при таком тесте n=6, l=3,r=6, a{1,2,3,4,5,6,7,8,9,10})... Помогите разобраться в чем проблема?... Ниже мой код

#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("input.txt");
ofstream fout("output.txt");

const int INF=(int)10e4;
const int Nmax=1000;
int a[Nmax],t[4*Nmax];
int n;


void build(int v,int l, int r){
	
	if(l==r)
		t[v]=a[l];
	else{
		
		int m=(l+r)/2;
		build(v*2,l,m);
		build(v*2+1,m+1,r);
		t[v]=min(t[2*v],t[2*v+1]);
	}	
}


int getmin(int v,int l,int r,int i,int j){
	
	if(l>r)
		return INF;
	if(l==i && j==r)
		return t[v];
	int m=(l+r)/2;
	int m1=getmin(2*v,l,m,i,min(j,m));
	int m2=getmin(2*v+1,m+1,r,max(m+1,i),j);
	return min(m1,m2);		
}

int main(){
	
	int l,r;
	fin >> n >> l >> r;
	for(int i=0;i<n;++i)
		fin >> a[i];
	
	build(1,0,n-1);
	
	fout << getmin(1,0,n-1,l,r);
	return 0;
	
}
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

у вас же массив на 6 элементов, а вы хотите найти значение на [3..6] в 0-индексации, то есть [4..7] в 1-индексации (при n = 6)

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Если уж есть тест, на котором не работает, то в чем проблема? Отладчик в руки — и вперед!

1) В дереве отрезков все 1-индексированное, поэтому надо передавать не (0,n — 1), а (1, n)

2) Неверно проставлены терминальные условия рекурсии в getMin. Должно быть что-то типа

if (r<i || l>j)
		return INF;
	if (l >= i && j <= r)
		return t[v];
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

потому что не if (l > r) return inf; а if(i > j) return inf;