Привет 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;
}
у вас же массив на 6 элементов, а вы хотите найти значение на [3..6] в 0-индексации, то есть [4..7] в 1-индексации (при n = 6)
Если уж есть тест, на котором не работает, то в чем проблема? Отладчик в руки — и вперед!
1) В дереве отрезков все 1-индексированное, поэтому надо передавать не (0,n — 1), а (1, n)
2) Неверно проставлены терминальные условия рекурсии в getMin. Должно быть что-то типа
потому что не if (l > r) return inf; а if(i > j) return inf;