Codeforces Round 780 (Div. 3) |
---|
Закончено |
Это сложная версия задачи F. Единственное различие между простой и сложной версиями заключается в ограничениях.
Будем называть непустую строку сбалансированной, если она содержит одинаковое количество знаков плюс и минус. Например: строки «+--+» и «++-+--» являются сбалансированными, а строки «+--», «--» и «» не являются сбалансированными.
Будем называть строку перспективной, если строку можно сделать сбалансированной при помощи нескольких(возможно нуля) применений следующей операции:
В частности, всякая сбалансированная строка является перспективной. Однако обратное неверно: не всякая перспективная строка — сбалансирована.
Например: строка «-+---» является перспективной, так как можно заменить два соседних минуса на плюс и получить сбалансированную строку «-++-», либо получить другую сбалансированную строку «-+-+».
Сколько непустых подстрок данной строки $$$s$$$ являются перспективными? Каждая непустая перспективная подстрока должна быть учтена в ответе столько раз, сколько раз она встречается в строке $$$s$$$.
Напомним, что подстрока — это последовательность подряд идущих символов строки. Например, для строки «+-+» её подстроками являются строки «+-», «-+», «+», «+-+» (строка является подстрокой самой себя) и некоторые другие. Но следующие строки её подстроками не являются: «--», «++», «-++».
В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.
Далее следуют описания наборов входных данных.
Каждый набор входных данных состоит из двух строк. В первой строке дано число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина строки $$$s$$$.
Во второй строке набора дана строка $$$s$$$ длины $$$n$$$, состоящая только из знаков «+» и «-».
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите единственное число — количество непустых перспективных подстрок строки $$$s$$$. Каждая непустая перспективная подстрока должна быть учтена в ответе столько раз, сколько раз она встречается в строке $$$s$$$.
5 3 +-+ 5 -+--- 4 ---- 7 --+---+ 6 +++---
2 4 2 7 4
Ниже перечислены перспективные подстроки для первых трёх наборов входных данных примера:
Название |
---|