Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.93/15: Рейтинг темы: голосов - 15, средняя оценка - 4.93
0 / 0 / 1
Регистрация: 02.08.2015
Сообщений: 10

Дерево отрезков. Максимум

11.02.2016, 21:29. Показов 3049. Ответов 4
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Набрал дерево отрезков, помогите найти ошибку.
Задача: http://www.e-olymp.com/ru/problems/4473
Набирает 17 из 100 баллов.

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
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
const int MAXN = (int)1e5;
 
int n, t[4*MAXN];
 
void build (vector<int> & a, int v, int tl, int tr) {
    if (tl == tr)
        t[v] = a[tl];
    else {
        int tm = (tl + tr) / 2;
        build (a, v*2, tl, tm);
        build (a, v*2+1, tm+1, tr);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}
 
int sum (int v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return max(sum (v*2, tl, tm, l, min(r,tm))
        , sum (v*2+1, tm+1, tr, max(l,tm+1), r));
}
 
 
 
int main() {
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    build(a, 1, 0, n - 1);
    int nQ;
    cin >> nQ;
    for (int i = 0; i < nQ; i++) {
        int left, right;
        cin >> left >> right;
        left--;
        right--;
        if (left > right) {
            swap(left, right);
        }
        cout << sum(1, 0, n - 1, left, right) << "\n";
    }
    return 0;
}
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
11.02.2016, 21:29
Ответы с готовыми решениями:

Зачем дополнять дерево отрезков до степени двойки?
Разбирая работу ДОшки без дополнения n до степени двойки, можно сказать, что в худшем случае будет кушать больше памяти в 2 раза (если тупо...

Двумерное дерево отрезков или фенвика + сканирующая прямая
Интересно было бы порешать задачи на эту тему, киньте что-нибудь

Написать программу, которая реализует дерево отрезков - где ошибка?
делаю задачу на реализацию дерева отрезков. Все вроде работает и ответы верные(на моих тестах), но проверяющей системе не нравится - выдает...

4
 Аватар для ProgJ
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
12.02.2016, 15:04
Выглядит правильно
Может быть по времени не проходит? или по памяти
0
0 / 0 / 1
Регистрация: 02.08.2015
Сообщений: 10
14.02.2016, 11:37  [ТС]
Нет, везде неправильный ответ.
0
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
14.02.2016, 14:13
Лучший ответ Сообщение было отмечено dertuner как решение

Решение

Добавлено через 25 секунд
dertuner,


видимо надо в функции sum вместо
C++ (Qt)
1
if(l > r) return 0;
написать

C++ (Qt)
1
if(l > r) return -2e9;
2
0 / 0 / 1
Регистрация: 02.08.2015
Сообщений: 10
15.02.2016, 23:20  [ТС]
Большое спасибо, просто дерево отрезков из суммы переделывал и не учел это.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
15.02.2016, 23:20
Помогаю со студенческими работами здесь

Найдите максимум произведения длин отрезков
Дана трапеция ABCD(AB=BC=CD=2). O – точка пересечения диагоналей AC и BD. Окружность, описанная вокруг треугольника ABO, пересекает...

Дерево отрезков
Реализуйте структуру данных, которая на данном массиве из N целых чисел позволяет узнать максимальное значение на этом массиве и индекс...

Дерево отрезков
Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность...

Дерево отрезков, задача
Не получается создать структуру дерева отрезков, а следовательно и решить задачу. Пусть задан целочисленный интервал от 1 до n....

Медленное дерево отрезков
Приветствую. Пишу дерево отрезков для задачи нахождения сумм на отрезках. Оно работает, даже вроде правильно, но при массиве 105 и...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image
8Observer8 27.01.2026
Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru