Форум программистов, компьютерный форум CyberForum.ru

Не работает дерево отрезков для НСД - C++

Восстановить пароль Регистрация
 
denysd21012011
3 / 3 / 2
Регистрация: 29.03.2013
Сообщений: 133
22.01.2014, 18:49     Не работает дерево отрезков для НСД #1
Написал дерево отрезков для минимума/максимума - все работает. Как только меняю функции min и max на gcd... Выдает почти всегда 1..... Подскажите в чем ошибка?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <iomanip>
#include <cstring>
using namespace std;
#define Nmax 1000000
 
int n,k, len=0;
int a[Nmax+1],t[Nmax*4+1];
 
int gcd(int x, int y){
if (x*y==0) return (x+y); else
if (x>y) return (gcd(x % y, y)); else return (gcd(x, y % x));
}
 
void build(int v, int l, int r){
if (l==r) t[v]=a[l]; else
 {
     int m=(l+r)/2;
     build(2*v,l,m);
     build(2*v+1,m+1,r);
     t[v]=max(t[2*v],t[2*v+1]);
 }
 
}
 
int sum(int v, int tl, int tr, int l, int r){
if (l>r) return 17; else
if (l==tl && r==tr) return t[v];
int m=(tl+tr)/2;
int x1=sum(2*v,tl,m,l,min(m,r)), x2=sum(2*v+1,m+1,tr,max(l,m+1),r);
return max(x1, x2);
}
 
void update(int v, int l, int r, int pos, int new_val){
if (l==r) t[v]=new_val; else
   {
     int m=(l+r)/2;
     if (pos<=m) update(2*v,l,m,pos,new_val); else update(2*v+1,m+1,r,pos,new_val);
     t[v]=max(t[2*v],t[2*v+1]);
   }
}
 
 
int main(){
 freopen("input.txt","r",stdin);
 freopen("output.txt","w",stdout);
 
 cin >> n;
 for (int i=1; i<n+1; i++) {
     cin >> a[i];
     //if (i % 2==0) a[i]=-a[i];
 }
 cin >> k;
 build(1,1,n);
 for (int i=0; i<k; i++) 
 {
     int q;
     int l, r, x;
 
     cin >> q;
     cin >> l >> r;
     if (q==2) update(1,1,n,l,r); else cout << sum(1,1,n,l,r) << endl;
 }
 
 
 return 0;
}
Тест :
Код
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 5
Правильный ответ:
Код
2
2
5
1
Добавлено через 1 час 27 минут
Кажись я понял свою ошибку

Добавлено через 33 минуты
Ошибка исправлена. Тему можно удалить.

Извините за беспокойство.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.01.2014, 18:49     Не работает дерево отрезков для НСД
Посмотрите здесь:

Дерево отрезков C++
Дерево отрезков, редактирование куска и поиск суммы C++
C++ На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков
Построение таблицы значений для функции с разбиением отрезков C++
Дерево отрезков, проверьте код C++
Медленное дерево отрезков C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 00:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru