Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
2 / 2 / 1
Регистрация: 21.04.2013
Сообщений: 205

Написать программу, которая реализует дерево отрезков - где ошибка?

19.04.2014, 23:03. Показов 1897. Ответов 4
Метки нет (Все метки)

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

сама задача:
Напишите программу, которая реализует дерево отрезков. В первой строке входа даны два числа n и m (1≤n,m≤10^5), во второй строке — n целых чисел, задающих начальные значения массива. Далее даны m строк вида Set I X, где I — номер позиции, а X — новое значение, или Min L R, где L и R — левая и правая границы отрезка. Для каждой операции Min программа должна вывести минимальное значение на отрезке от L до R. Позиции нумеруются от единицы до n, все значения — натуральные числа, не превышающие 10^9.

Sample Input:
5 7
1 2 3 4 5
Min 1 5
Set 1 8
Min 1 5
Min 1 1
Min 1 3
Set 3 1
Min 2 4
Sample Output:
1
2
8
2
1
Memory Limit: 256 MB
Time Limit: 5 seconds

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <stdio.h>
#include <string.h>
 
 
int n,m;
unsigned long int a[100000];  //исходный массив
char command[100000][4];   //массив с командами
unsigned long int val[100000][2];  //массив под значения команд
unsigned long int *t;    //дерево
 
//построение дерева
void build (unsigned long int v, unsigned long int tl,unsigned long int tr) {
 
    if (tl == tr)
    {
        t[v] = a[tl];
    }
    else {
        int tm = (tl + tr) / 2;
        build (v*2, tl, tm);
        build (v*2+1, tm+1, tr);
 
            t[v] =std::min( t[v*2], t[v*2+1]);
    }
}
//минимум на отрезке
int mini (unsigned long int v, unsigned long int L, unsigned long int R, unsigned long int l, unsigned long int r) {
    if(l<L){l=L;}
    if(r>R){r=R;}
    
    if (l>r || l>R || r<L){return 1e9;}
    
        if ((l == L) && (r == R))
        {
            return t[v];
        }
        else {
                unsigned long int tm = (L + R) / 2;             
                return std::min (mini (v*2, L, tm, l, std::min(r,tm)), mini (v*2+1, tm+1, R, std::max(l,tm+1), r));
            }
    
}
//замена элемента
void seti (unsigned long int v,unsigned long  int tl,unsigned long  int tr,unsigned long  int pos,unsigned long  int new_val)
{
        if (tl==tr && pos == tl)
        {           
            t[v] = new_val;
            return;
        }
        else {
                unsigned long int tm = (tl + tr) / 2;
                if (pos <= tm)
                {
                    seti (v*2, tl, tm, pos, new_val);
                }
                else
                {
                    seti (v*2+1, tm+1, tr, pos, new_val);
                }
        
                t[v] = std::min( t[v*2], t[v*2+1]);
            }
    
}
 
int main()
{       
    scanf ("%d%d",&n,&m); 
    
    for (int i=1; i<=n; i++)
    {
        scanf ("%d",&a[i]);
    }
 
        for (int i=1; i<=m; i++)
    {
        scanf ("%s%d%d",command[i],&val[i][0],&val[i][1]);
    }
        
    //дополнение дерева до степени двойки
        int p = 0;
        int s=n;
        while((1<<p) < n) p ++;
        n = (1<<p);
        for (int i=s+1; i<=n; i++)
        {
            a[i] = 1e9;
        }
 
        t = new unsigned long int[4*n]; 
 
    build(1,1,n);
 
    
        char minimum [4] = "Min"; 
        char set [4] = "Set";
 
        for (int i=1; i<=m; i++)
    {
        if (strcmp(command[i],minimum) == 0)
        {
            std::cout<<mini(1, 1, n, val[i][0], val[i][1])<<std::endl;
        } 
        else if (strcmp(command[i],set) == 0)
        {   
            seti(1, 1,n, val[i][0], val[i][1]); 
        }
    }
 
       delete t;
    return 0;}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
19.04.2014, 23:03
Ответы с готовыми решениями:

Написать программу, которая реализует алгоритм
Написать программу, которая реализует такой алгоритм: 1) Выводит на экран меню: 1. Ввод данных 2. Вычисление функции 3....

Написать программу, которая реализует связный список
Написать программу, которая реализует связный список. Операции, которые должна выполнять программа: 1) Создание списка из входного файла....

Написать программу, которая реализует диалог с пользователем
Заранее благодарю всех, кто помог

4
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
167 / 167 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
20.04.2014, 18:03
mhg, могу вот кинуть свой исходник дерева отрезков.Может поможет:
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
/*Одна особенность: в функции get_min() при нахождении максимума нужно возвращать в первом условии -INF, а при нахождении
максимума INF.Пр нахождении суммы возвращать 0 */
 
 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
 
using namespace std;
 
const int INF=10000;
int a[11]={0,1,2,3,4,5,6,7,8,9,10},t[4*11+1];
 
void build(int v,int tl,int tr)
{
    if(tl==tr)
        t[v]=a[tl];
    else
    {
        int tm=tl+((tr-tl)>>1);
        build(v<<1,tl,tm);
        build((v<<1)+1,tm+1,tr);
        t[v]=min(t[v<<1],t[(v<<1)+1]);
    }
}
 
 
int get_min(int v,int tl,int tr,int l,int r)
{
    if(l>r)
        return INF;
    if(l==tl && r==tr)
        return t[v];
    else
    {
        int tm=tl+((tr-tl)>>1);
        return min(get_min(v<<1,tl,tm,l,min(r,tm)),
               get_min((v<<1)+1,tm+1,tr,max(l,tm+1),r));
    }
}
 
void update(int v,int tl,int tr,int pos,int val)
{
    if(tl==tr)
        t[v]=val;
    else
    {
        int tm=tl+((tr-tl)>>1);
        if(pos<=tm)
            update(v<<1,tl,tm,pos,val);
        else
            update((v<<1)+1,tm+1,tr,pos,val);
        t[v]=min(t[v<<1],t[(v<<1)+1]);
    }
}
 
 
 
int main()
{
    build(1,1,10);
    int n,m,pos,val;
    cin>>n>>m;
    cout<<get_min(1,1,10,n,m)<<endl;
    cin>>pos>>val;
    update(1,1,10,pos,val);
    cout<<get_min(1,1,10,n,m)<<endl;
    system("pause");
}
1
835 / 643 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
25.04.2014, 12:49
Хм.. Рекурсивное... В некоторых случаях может быть удобно, но я предпочитаю другой вариант - с поднятием от листьев при помощи циклов. В случае отсутствия апдейтов на отрезке - очень хороший вариант. Да и пишется проще и короче. И работает быстрее, кстати (при спуске логарифм от размера дерева, а при подъёме - от длины отрезка).
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
25.04.2014, 17:28
Цитата Сообщение от Qwertiy Посмотреть сообщение
И работает быстрее, кстати (при спуске логарифм от размера дерева, а при подъёме - от длины отрезка).
как-то странно это. по-вашему выходит, что операция с листом за константу выполняется, а с корнем за логарифм...
0
835 / 643 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
25.04.2014, 19:29
Цитата Сообщение от salam Посмотреть сообщение
по-вашему выходит, что операция с листом за константу выполняется, а с корнем за логарифм...
А что подразумевается под операцией с корнем? Есть операции с отрезком, соответственно, если подниматься из листьев наверх, то операция будет выполнена за логарифм длины отрезка. В таком случае да, если отрезок затрагивает только один лист, то операция выполнится сразу, а если покрывает всё дерево, то за логарифм размера дерева. Всё логочно, по-моему.

Добавлено через 13 минут
Поясню способ реализации дерева, пожалуй. А то он отличается от приведённых тут.

Пусть есть константа MAXN, обязательно являющаяся степенью 2. Это максимальное число элементов массива. Заведём массив под дерево размером TSIZE = MAXN*2 (на 2, не на 4, 4 нужно для вариантов, где размер не фиксированный). Массив будем рассматривать в 0-индексации, т. е. от 0 до MAXN невключительно, а дерево в 1-индексации, т. е. tree[1] - это корень дерева, а tree[0] не используется. Сам массив поместим во вторую половину дерева, т. е. tree[MAXN] - это нулевой элемент массива.

Пусть есть два индекса массива l и r (отрезок - концы включительно оба). Для того, чтобы получить значение на отрезке синхронно поднимаемся от них вверх. При этом, если левый конец является правым ребёнком, берём из него значение и смещаемся вправо. Если правый конец является левым ребёнком, берём из него значение и смещаемся влево. Т. е. вершины l и r, в которых мы находимся всегда покрывают подотрезок исходного и не выходят за его пределы. Возможно, на самом деле не совсем так, поскольку здесь я подразумеваю покрытие для лучей r to -INF и l to +INF в отдельности, но это не важно. Когда условие l<r стало ложным, прекращаем подъём. При этом, если выполняется l==r, то используем так же значение из этой вершины, в противном случае игнорируем их.

Возвращаем результат для отрезка.

Добавлено через 2 минуты
Да, внесения изменения в вершину - это подъём от неё до корня с апдейтами проходимых вершин - один цикл с делением индекса на 2. Построение дерева - один цикл MAXN-1 to 1 c вычислением значения данной вершины. Никаких дополнительных параметров о покрытии в методы передавать не нужно.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
25.04.2014, 19:29
Помогаю со студенческими работами здесь

Написать программу, которая реализует телефонный справочник
Написать программу, которая реализует телефонный справочник. В справочнике содержится следующая информация о каждом абонента: имя и...

Написать программу, которая реализует круговой список
Добры

Написать программу которая реализует алгоритмы массивов
Использовать два одномерных массива - массив целых чисел и массив действительных чисел. Прочитать 15 действительных чисел и записать их в...

Написать программу, которая реализует диалог с пользователем
Помогите, пожалуйста, кто чем может) Спасибо!!

Написать программу, которая реализует телефонную книгу с функциями
Написать программу, которая реализует телефонную книгу с функциями: добавления абонента -, редактирования абонента удаление абонента ...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
YAFU@home — распределённые вычисления для математики. На CPU
Programma_Boinc 20.01.2026
YAFU@home — распределённые вычисления для математики. На CPU YAFU@home — это BOINC-проект, который занимается факторизацией больших чисел и исследованием aliquot-последовательностей. Звучит. . .
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru