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

Дерево отрезков, редактирование куска и поиск суммы - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Подключение библиотеки audiere C++ Code Blocks http://www.cyberforum.ru/cpp-beginners/thread906938.html
Скачала архив (приложила его). Распаковала. Что делать дальше? Куда и что надо распихать? Заранее спасибо.
C++ Написать программу с использованием функции cctype Программа, которая читает клавиатурный ввод до символа @ и повторяет его, за исключением десятичных цифр, преобразуя каждую букву верхнего регистра в букву нижнего регистра и наоборот. http://www.cyberforum.ru/cpp-beginners/thread906936.html
C++ В массиве y(20), сформированном случайным образом, найти среднее арифметическое модулей всех ненулевых элементов
вот задание: В массиве y(20), сформированном случайным образом, найти среднее арифметическое модулей всех ненулевых элементов. Заранее спасибо.
Замена указанного массива информации на массив информации C++
Написать программу производящую замену указанного массива информации с позиции A до позиции B в файле на массив информации находящийся в этом же файле c позиции A+C до позиции B+C.
C++ Переделать програму http://www.cyberforum.ru/cpp-beginners/thread906875.html
#include <iostream> using namespace std; char Bykvi(int i) { return static_cast<char>('a'-1+i); } void main() {
C++ Двухсторонняя очередь, relocate Привет, есть код. Знаю что в нем много косяков, не могу сам справиться. Нужно прицепить метод relocate, который будет сдвигать очередь к центру, если она ни с одной из сторон не заполнена#include <iostream> #include <cstdlib> #include <conio.h> #include <math.h> using namespace std; #define length 8 class dequeue { int s; int bottom, top; private: int g; подробнее

Показать сообщение отдельно
Nebel
1 / 1 / 0
Регистрация: 06.05.2012
Сообщений: 12

Дерево отрезков, редактирование куска и поиск суммы - C++

19.06.2013, 19:49. Просмотров 1230. Ответов 2
Метки (Все метки)

Добрый вечер.
Пишу алгоритм нахождения суммы элементов на отрезке и редактирования элементов на отрезке.
Вводится N - число элементов в массиве, K - кол - во операций.
Далее на вход программе дается 2 различные команды
A l r x - присвоить элементам с позиции l до r значение х
Q l r - найти сумму элементов на отрезке от l до r
Изначально массив заполнен нулями.
(1 <= N <= 100 000), (0 <= K <= 100 000).

Пример:
IN
5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5

OUT
3
2
3
4
2
7

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
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <cstring>
 
using namespace std;
 
int a[100000], N;
long long t[1000000];
 
void push(int x)
{
     if (t[x] != -1)
     {     
           t[2 * x] = t[2 * x + 1] = t[x];
           t[x] = -1;
     }
}
 
void update(int x, int l, int r, int L, int R, int c)
{
     if ((l > r) || (l > R) || (r < L))
        return;
        
     if ((L <= l) && (r <= R))
            t[x] = c;
     else
     {   
         push(x);
        // BUG         
        int mid = (l + r) / 2;   
        update(x * 2, l, mid, L, R, c);
        update(x * 2 + 1, mid + 1, r, L, R, c);
     }
}
 
long long sum(int x, int l, int r, int L, int R)
{
    if ((l > r) || (l > R) || (r < L))
       return 0;
       
    if ((L <= l) && (r <= R))
       return t[x];
    
    push(x);   
    int mid = (l + r) / 2;
    return sum(2 * x, l, mid, L, R) + sum(2 * x + 1, mid + 1, r, L, R);    
}
 
int main(void)
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    int N = 1, n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
            cin >> a[i];
            
    while (N < n)
          N *= 2;
      
    for(int i = 0; i < n; i++)
            t[N + i] = a[i];
    
    for(int i = n; i < N; i++)
            t[N + i] = 0;
               
    for(int i = N - 1; i >= 1; i--)
            t[i] = t[i * 2] + t[i * 2 + 1];
                         
    int x, y, z;
    char ss;
 
    for(int i = 0; i < k; i++)
    {       
            scanf ("%c", &ss);
            if (ss == 'A')
            {
                scanf("%d %d %d", &x, &y, &z);
                update(1, 1, N, x, y, z);  
            }
            else
            {
                scanf("%d %d", &x, &y);
                cout << sum(1, 1, N, x, y) << endl;
            }
    }       
    
    for(int i = 0; i < n; i++)
            cout << t[i] << " ";       
       
    fclose(stdin);
    fclose(stdout);
    return 0;
}
Не могу найти ошибку, пожалуйста помогите!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 14:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru