Префиксная сумма или что-то иное

@sergeypast · Регистрация: 27.03.2016

Студворк — интернет-сервис помощи студентам

Не все числа одинаково полезны. Если, например, вам потребуется насобирать сумму
как можно больше, то вам ни к чему использовать отрицательные числа. Но может
получиться так, что и выбора не останется и придется их использовать. Да и вообще
воспользуемся модулем, чтобы уровнять положительный и отрицательные числа. И совсем
не требуется насобирать максимальную сумму, достаточно чтобы модуль суммы был
больше M. Требуется найти количество способов выбрать подотрезок в последовательности
с заданным свойством.

Входные данные:
В первой строке задаются числа N M — количество чисел в последовательности и нижний
предел модуля суммы (1 ≤ N ≤ 105, 1 ≤ M ≤ 109).
В следующей строке задается N чисел Ai — числа последовательности (|Ai| ≤ 104).
Выходные данные:
В единственной строке выведите искомое количество подотрезков.

Пример
ввод
10 8
-2 9 3 6 3 8 -1 10 -6 7
вывод
42

Почему не может вложиться в 1 секунду?
Использовал идею префиксных сумм.
Возможно ли ошибка в том что использую 2 цикла?

код

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
int main() {
    int n;
    long int m;
    int a[100000];
    long int pref[100000];
    scanf("%d%ld", &n, &m);
    long int ans = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (a[i] > m || -a[i] > m) ans++;
    }
    pref[0] = a[0];
    for (int i = 1; i < n; i++) {
        pref[i] = pref[i - 1] + a[i];
    }
    long int number;
    int k = 1;
    do
    {
        number = pref[k++];
        if(number > m || -number> m) ans++;
    } while (k<n);
    for (int i = 1; i < n - 1; i++)
    {
        for (int j = i+1; j < n;j++)
        {
            number= pref[j] - pref[i - 1];
            if (number > m || -number> m) ans++;
        }
    }
    printf("%ld", ans);
}

@Shamil1 · 27.03.2016, 17:01

Сообщение от sergeypast

Почему не может вложиться в 1 секунду?

А должно укладываться? В условии 1 ≤ N ≤ 105, а у Вас N = 100 000.

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

@sergeypast · 27.03.2016, 17:52 **[ТС]**

там 10^5 степени , как и m 10^9 степени и Ai 10^4

@Shamil1 · 27.03.2016, 23:31

Значит, нужно использовать более быстрый алгоритм.
Вот набросок:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static long Solve(int[] a, int m)
{
    var sums = new List<int>();
    long res = 0;
    int sum = 0;
    for (int i = 0; i < a.Length; i++)
    {
        sums.Add(sum);
        sum += a[i];
        res += sums.Where(x => sum - x > m).Count();
        res += sums.Where(x => x - sum > m).Count();
    }
    return res;
}

Только вместо вектора (List<int>) нужно использовать бинарное дерево. В каждом узле дерева хранить значение частичной суммы и общее количество элементов в этом поддереве. Тогда операции в стоках 10, 11, 12 будут занимать O(logN).

10: количество в дереве чисел больше заданного sum - m
11: количество в дереве чисел больше заданного m - sum
08: добавление в дерево элемента

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

@salam · 02.04.2016, 21:15

расскажи, пожалуйста, откуда задача. если есть ссылка - вообще круто будет.

@Shamil1 · 03.04.2016, 02:00

Сообщение от salam

расскажи, пожалуйста, откуда задача. если есть ссылка - вообще круто будет.

Вбейте в гугле "Не все числа одинаково полезны." (включая кавычки)

з.ы. Написал дерево. На случайных числах укладываюсь в 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
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
void Main()
{
    int n = 100000, m = 5000;
    var a = GetRandomNumbers(n, -1000, 1000);
    var sw = new Stopwatch();
    sw.Start();
    var r = Solve(a, m);
    sw.Stop();
    Console.WriteLine($"res = {r}, time = {sw.ElapsedMilliseconds}");
}
 
public static long Solve(int[] a, int m)
{
    SimpleBinTree[] sums = new SimpleBinTree[a.Length];
    long res = 0;
    int sum = 0;
    for (int i = 0, count = 0; i < a.Length; i++)
    {
        count = SimpleBinTree.Add(sums, count, sum);
        sum += a[i];
        res += SimpleBinTree.CountValues(sums, 0, CountMode.LS, sum - m);
        res += SimpleBinTree.CountValues(sums, 0, CountMode.GT, sum + m);
    }
    return res;
}
 
public enum CountMode
{
    GT = 0,
    GE = 1,
    LS = 2,
    LE = 3,
}
 
public struct SimpleBinTree
{
    public int Value;
    public int Count;
    public int Left;
    public int Right;
 
    public static int Add(SimpleBinTree[] sums, int index, int value)
    {
        int parent = 0;
        while (parent != index)
        {
            sums[parent].Count++;
            if (value < sums[parent].Value)
            {
                if (sums[parent].Left == -1)
                {
                    sums[parent].Left = index;
                }
                parent = sums[parent].Left;
            }
            else if (value > sums[parent].Value)
            {
                if (sums[parent].Right == -1)
                {
                    sums[parent].Right = index;
                }
                parent = sums[parent].Right;
            }
            else
                return index;
        }
        sums[index++] = new SimpleBinTree { Value = value, Count = 1, Left = -1, Right = -1 };
        return index;
    }
 
    public static int CountValues(SimpleBinTree[] sums, int node, CountMode mode, int value)
    {
        int count = 0;
        int coef = 1;
        while (node != -1)
        {
            switch (mode)
            {
                case CountMode.GT:
                    if (sums[node].Value <= value)
                    {
                        node = sums[node].Right;
                    }
                    else
                    {
                        count += coef * sums[node].Count;
                        coef *= -1;
                        mode = CountMode.LE;
                        node = sums[node].Left;
                    }
                    break;
                case CountMode.GE:
                    if (sums[node].Value < value)
                    {
                        node = sums[node].Right;
                    }
                    else
                    {
                        count += coef * sums[node].Count;
                        coef *= -1;
                        mode = CountMode.LS;
                        node = sums[node].Left;
                    }
                    break;
                case CountMode.LE:
                    if (sums[node].Value <= value)
                    {
                        count += coef * sums[node].Count;
                        coef *= -1;
                        mode = CountMode.GT;
                        node = sums[node].Right;
                    }
                    else
                    {
                        node = sums[node].Left;
                    }
                    break;
                case CountMode.LS:
                    if (sums[node].Value < value)
                    {
                        count += coef * sums[node].Count;
                        coef *= -1;
                        mode = CountMode.GE;
                        node = sums[node].Right;
                    }
                    else
                    {
                        node = sums[node].Left;
                    }
                    break;
            }
        }
        return count;
    }
}
 
public static int[] GetRandomNumbers(int size, int min, int max)
{
    Random rnd = new Random();
    int[] a = new int[size];
    for (int i = 0; i < a.Length; i++)
        a[i] = rnd.Next(min, max);
    return a;
}

@salam · 25.04.2016, 18:09

ну да. возьмем массив {1, 1, 1, 1, 1, ...} и получим дерево высоты n. я не знаю, на чем ты умеешь писать, кроме шарпа. плюсы или java подошли бы. там есть std::set и TreeSet соответственно.

@Shamil1 · 25.04.2016, 19:07

Сообщение от salam

плюсы или java подошли бы. там есть std::set и TreeSet соответственно

Подошли бы для быстрого ответа на вопрос "сколько в коллекции чисел больше заданного?"?

@salam · 25.04.2016, 20:27

Сообщение от Shamil1

Подошли бы для быстрого ответа на вопрос "сколько в коллекции чисел больше заданного?"?

что-то я поспешил.) ну строго говоря, set можно научить хранить размеры поддеревьев, только для этого нужно лезть ему во внутренности, и выглядит все это очень не естественно.
ну тогда можно два варианта предложить: написать все же руками какое-нибудь сбалансированное BST или отвечать на эти запросы деревом отрезков.

@Shamil1 · 25.04.2016, 21:13

Сообщение от salam

написать все же руками какое-нибудь сбалансированное BST

мне лень
задача простая, но нудная
если ТС нужно, он сделает сам или найдёт готовое

@Cuellius · 09.05.2016, 16:41

Давно решал.
Идея:
Считаем префиксные суммы(pref) для исходного массива.
Перебираем начало отрезка суммирования(i)
Пусть sum_left = i ? pref[i - 1] : 0;
Пусть j - подходящий конец отрезка суммирования, тогда:
Тогда должно выполняться неравенство:
|pref[j] - sum_left| > M =>
pref[j] - sum_left > M или pref[j] - sum_left < -M
pref[j] > M + sum_left или pref[j] < -M + sum_left
Тогда ответ для некоторого начало отрезка суммирования(i): число чисел в массиве префиксных сумм, больших M + sum_left и плюс число чисел в массиве префиксных сумм, меньших -M + sum_left - эти запросы можно вычислять за O((log(n))^2) с помощью дерева отрезков.
Поскольку мы перебираем i от 0 до n - 1, а также строим дерево отрезков, то итоговая сложность
O(n * (log(n)^2)).

Код:

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
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
 
#define MAXN 100007
#define all(X) (X).begin(), (X).end()
 
struct Node
{
    int l, r;
    Node *L, *R;
    std::vector<int> val;
 
    Node(int l, int r, int a[]) : l(l), r(r)
    {
        if (l == r)
        {
            L = R = NULL;
            val = { a[l] };
        }
        else
        {
            int tm = (l + r) >> 1;
            L = new Node(l, tm, a);
            R = new Node(tm + 1, r, a);
            val.resize(r - l + 1);
            std::merge(all(L->val), all(R->val), val.begin());
        }
    }
 
    // # if elements < x
    int Get(int lq, int rq, int x)
    {
        if (lq <= l && rq >= r) return std::lower_bound(all(val), x) - val.begin();
        if (rq < l || lq > r) return 0;
        return L->Get(lq, rq, x) + R->Get(lq, rq, x);
    }
};
 
int a[MAXN], sum[MAXN], n, m;
 
int main()
{
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
   
    scanf("%d%d", &n, &m);
   
    for(int i = 0; i < n; i++) scanf("%d", a + i);
    sum[0] = a[0];
    for(int i = 1; i < n; i++) sum[i] = sum[i - 1] + a[i];
   
    Node *t = new Node(0, n - 1, sum);
    long long ans = 0;
    for(int i = 0; i < n; i++)
    {
        int left_sum = i ? sum[i - 1] : 0;
        //r - l = sum => r - l < -m or r - l > m
        //              r < -m + l or r > m + l
       
        ans += t->Get(i, n - 1, -m + left_sum);
        ans += ((n - i) - t->Get(i, n - 1, m + left_sum + 1));
    }
   
    std::cout << ans << std::endl;
   
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@sergeypast 0 / 0 / 0 Регистрация: 27.03.2016 Сообщений: 2
	27.03.2016, 17:52 [ТС]
	там 10^5 степени , как и m 10^9 степени и Ai 10^4 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	02.04.2016, 21:15
	расскажи, пожалуйста, откуда задача. если есть ссылка - вообще круто будет. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	25.04.2016, 18:09
	ну да. возьмем массив {1, 1, 1, 1, 1, ...} и получим дерево высоты n. я не знаю, на чем ты умеешь писать, кроме шарпа. плюсы или java подошли бы. там есть std::set и TreeSet соответственно. 0