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

Дерево отрезков в определенной модификации - C++

Восстановить пароль Регистрация
 
denysd21012011
3 / 3 / 2
Регистрация: 29.03.2013
Сообщений: 133
22.06.2014, 17:50     Дерево отрезков в определенной модификации #1
Нужно уметь выполнять операции вида:
1) Присвоение на отрезке ( А l r x (от l до r сменить значения на x)
2) Сума на отрезке( Q l r (найти суму от l, r))

Помогите подправить мой код:
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
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <set>
#include <stdio.h>
#include <vector>
#include <map>
 
#define ull unsigned ll
#define ll long long
#define len length()
#define Nmax 111111
#define INF 1e18
using namespace std;
 
int n, m;
pii t[Nmax * 4];
ll a[Nmax];
int l, r, x;
char c;
//функция для запаздывающего обновления
void push(int v){
    if (t[v].sc != 0) {
        t[v * 2].sc = t[v * 2 + 1].sc = t[v].sc;
        t[v].sc = 0;
    }
}
 
ll get_sum(int v, int tl, int tr, int l, int r){
    if (l > r) return 0;
    if (tl == l && tr == r) return t[v].sc*(r-l+1);
    //push(v);
 
    int m = (tl + tr) / 2;
    return (get_sum(v * 2, tl, m, l, min(r, m)) +
            get_sum(v * 2 + 1, m + 1, tr, max(l, m + 1), r));
}
 
 
// обновление на отрезке
void update(int v, int tl, int tr, int l, int r, int add){
    if (l > r) return;
    if (tl == l && tr == r) t[v].sc = add; else
    {
        push(v);
        int m = (tl + tr) / 2;
        update(v * 2, tl, m, l, min(m, r), add);
        update(v * 2+1, m + 1, tr, max(m + 1, l), r, add);
    }
}
 
int main(){
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
 
    cin >> n >> m;
    memset(t, 0, sizeof(t));
    FORN(i, m)
    {
        cin >> c >> l >> r;
        if (c == 'A') {
            cin >> x;
            update(1, 1, n, l, r, x);
        }
        else cout << get_sum(1, 1, n, l, r) << endl;
    }
    
    
    return 0;
}
Не работает сума на отрезке. В чем проблема не знаю. Надеюсь на вашу помощь.

Теорию я изучил с сайта e-maxx.ru;
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.06.2014, 17:50     Дерево отрезков в определенной модификации
Посмотрите здесь:

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

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

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

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