解決する間隔ツリーについて質問があり、基本的にアルゴリズムは知っていますが、関数がメインに値を返すときにコードに問題があります。
私が抱えている問題は、特定のインデックス間の最大値を見つけて、配列内の値を更新することです。したがって、n 個の数値と m 個の演算を含む初期配列があります。操作が 0 で始まる場合は、 index 間の最大値を調べる必要がありますx。操作が 1 で始まる場合、x初期ベクトルのインデックスの値を で更新する必要がありますy。
問題は、質問によっては正しい答えをファイルから取得することもあれば、単に「乱数」を与えることもあります。
答えを監視できるようにコード中にいくつかのprintfを実行しましたが、最後に関数で値を返す前に完全に正しいことがわかり、関数の直後にメインでチェックすると結果が得られます先ほども言いました。
これは私がテストしている入力です:
5 5
4 3 5 6 1
0 1 3
1 3 2
0 2 3
1 4 2
0 1 5
コード：
#include <stdio.h>
FILE *fin, *fout;
int pos, val, m, n, *arb;
bool f;
int max(int a, int b);
void pun(int nod, int st1, int dr1);
int interogare(int nod, int st1, int dr1, int st2, int dr2);
int main()
{
fin = fopen("arbori.in", "r");
fout = fopen("arbori.out", "w");
fscanf(fin, "%d%d", &n, &m);
arb = new int[2*n];
for(int i = 1; i<= 2*n - 1; i++) arb[i] = 0;
for(int i =1; i<= n; i++)
{
pos = i;
fscanf(fin, "%d", &val);
pun(1, 1, n);
}
for(int i =1; i<= m; i++)
{
fscanf(fin, "%d", &f);
if(f == 1)
{
fscanf(fin, "%d%d", &pos, &val);
pun(1, 1, n);
}
else
{
fscanf(fin, "%d%d", &pos, &val);
fprintf(fout, "%d\n", interogare(1, 1, n, pos, val));//if i check it here it's not good
}
}
return 0;
}
int max(int a, int b)
{
return (a> b)?a:b;
}
void pun(int nod, int st1, int dr1)//update function - working properly
{
if(st1 == dr1)
{
arb[nod] = val;
return ;
}
int mij = (st1 + dr1)/2;
if(pos <= mij) pun(2*nod, st1, mij);
else pun(2*nod+1, mij +1, dr1);
arb[nod] = max(arb[2*nod + 1], arb[2*nod]);
return ;
}
int interogare(int nod, int st1, int dr1, int st2, int dr2)//interogation function
{
if(st1 == st2 && dr1 == dr2) return arb[nod];//if i check my result here it is the expected one
int mij = (st1 + dr1)/2;
if(st2 > mij) interogare(2*nod+1, mij+1, dr1, st2, dr2);
if(dr2 <= mij) interogare(2*nod, st1, mij, st2, dr2);
if(st2 <= mij && dr2 > mij) return max(interogare(2*nod, st1, mij, st2, mij),interogare(2*nod+1, mij + 1, dr1, mij + 1, dr2));
}
長い投稿と長いコードで申し訳ありません。何かを省略した場合は、思い出してください。
前もって感謝します！