Нахождение количества удовлетворяющих условию подотрезков

Общая идея

Насчитываем префиксные суммы. Перебираем правую границу. Смотрим для этой правой границы количество подходящих левых.

Задача 10727

Условие

По каналу связи передаётся последовательность целых чисел. Определите количество непрерывных подпоследовательностей чисел, в которых количество отрицательных чисел равняется количеству положительных чисел.

Разбор

Создадим массив в котором b[i] = -1, если a[i] < 0; b[i]=1, если a[i]> 0. pref[i] - сумма b[j] таких что j <= i, то есть сумма на префиксе длины i + 1 (у нас индексация с нуля). Теперь не трудно заметить, что в получившемся массиве b нужно найти количество подотрезков, у которых сумма равна 0. Для этого переберем правую границу нашего отрезка и найдем количество подходящих левых. Для фиксированной границы right нужно найти количество i < right, таких что pref[right]=pref[i]. Для этого будем поддерживать массив cnt, где cnt[pref[j]] - сколько раз встречается pref[j], для j < i. Чтобы числа были больше нуля прибавим n ко всем pref[i].

Код 


        

        

            

        

        
        

            
  Похожие задачи:  

        

    


    

        
 Задача 9555 

        

            
 Условие 

            
                Серия показаний характеризуется числом X. Х – количество последовательностей показаний, длиной не меньше K, сумма
                элементов которых делится на 111 без остатка.
                Определите, значение X для предложенных файлов.
            
        

        

            
 Разбор 

            
                Cоздадим массив pref, где pref[i] - сумма на префиксе длины i.
                Теперь нам необходимо посчитать количество пар (l, r), таких что их длина не менее k, а сумма кратна 111.
                В контексте нашей задачи это означает выполнение двух условий r - l + 1 >= k, и (pref[r] - pref[l - 1]) % 111 == 0, есть
                pref[r] % 111 == pref[l - 1] % 111.
                Создадим массив cnt, в нем cnt[i] - количество pref[l] % 111, таких что r - l + 1 >= k.

            
        

    
        
 Код 

        

            

        
  
        

            

        

        
        

            
  Похожие задачи:  

        

    


    

        
 Задача 2901 

        

            
 Условие 

            
                Дана последовательность натуральных чисел. Необходимо определить количество её непрерывных подпоследовательностей, сумма
                элементов которых кратна 666.
            
        

        

            
 Разбор 

            
                Создадим массив pref, где pref[i] - сумма на префиксе длины i.
                Теперь нам необходимо посчитать количество пар (l, r), таких что их длина не менее k, а сумма кратна 666.
                В контексте нашей задачи это означает выполнение условия (pref[r] - pref[l - 1]) % 666 == 0, то есть pref[r] % 666 ==
                pref[l - 1] % 666.
                В массиве cnt, cnt[i] - количество pref[l] % 666, таких что l < r Переберем правую границу нашего отрезка и прибавим
                    количество l таких что l < r и pref[l] % 666==pref[r] % 666.
            
        

    
        
 Код 

        

            

        

        

            

        

        
        

            
  Похожие задачи:  2906