관측 보정값이 맞는 구간

문제

한 천문대는 관측 장비의 상태를 확인하기 위해 일정한 간격으로 기준 신호를 측정한다. 각 측정 기록에는 기준보다 얼마나 높거나 낮게 측정되었는지를 나타내는 정수 보정값이 저장된다. 기준보다 높으면 양수, 낮으면 음수이며, 기준과 같으면 0이다. 이번 관측에서는 N개의 보정값을 얻었고, 기록에는 측정한 순서대로 1번부터 N번까지 번호가 붙어 있다. 분석 담당자는 일부 기록을 연속으로 골라 하나의 분석 구간을 만들려 한다. 분석 구간은 시작 번호 L과 끝 번호 R로 정하며, L번부터 R번까지의 모든 기록을 빠짐없이 포함한다. 반드시 1 ≤ L ≤ R ≤ N을 만족해야 하므로 기록을 하나도 포함하지 않는 빈 구간은 허용하지 않는다. 구간에 포함된 보정값을 모두 더한 결과가 목표 정수 K와 정확히 같으면, 그 구간을 점검 대상 구간으로 분류한다. 보정값은 부호를 그대로 유지하여 더하며 절댓값으로 바꾸지 않는다. 구하고자 하는 것은 점검 대상 구간의 개수이다. 시작 번호나 끝 번호 중 하나라도 다르면 서로 다른 구간으로 센다. 두 구간이 일부 기록을 공유하거나, 한 구간이 다른 구간에 완전히 포함되어 있어도 각각 조건을 만족하면 모두 센다. 여러 구간에 들어 있는 값의 나열이 우연히 같더라도 위치가 다르면 서로 다른 구간이다. 반대로 하나의 시작 번호와 끝 번호로 정해지는 구간을 여러 번 세어서는 안 된다. 관측 중에는 같은 보정값이 반복되거나 보정값이 0인 기록이 연속으로 나올 수 있다. 양수와 음수가 함께 존재하므로 구간을 늘렸을 때 합이 반드시 커지는 것은 아니다. 목표 K 역시 음수나 0일 수 있으며, 이때에도 구간을 고르는 규칙은 동일하다. 점검 대상 구간이 하나도 없으면 개수는 0이다. 주어진 전체 관측 기록에서 보정값의 합이 K인 모든 연속 구간의 개수를 구한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100,000, -900,000 ≤ K ≤ 900,000이다.
둘째 줄에 보정값을 나타내는 N개의 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대하여 -9 ≤ A_i ≤ 9이다.

출력

보정값의 합이 K인 비어 있지 않은 연속 구간의 개수를 정수로 한 줄에 출력한다. 조건을 만족하는 구간이 없으면 0을 출력한다.

5 2
2 -1 2 -2 1

3

4 0
0 0 0 0

10

3 7
1 -1 2

0

출처: Devin.KR 자체 제작