13215 - Fish

step 1

N개의 세그먼트가 있다고 해봅시다. 저희가 이미 어떤 방법을 통해서 [1, N/2], [N/2+1, N] 영역에 대해 답을 구했다고 해봅시다. 그럼 이 두 영역에 모두 걸쳐있는 영역에 대해 답을 구하면 문제를 해결할 수 있습니다.

step 2

[1, N/2] 영역에서 오른쪽 부분합과 [N/2+1, N] 영역의 왼쪽 부분합을 구합니다. 오른쪽 부분합은 영역의 오른쪽 부터 왼쪽으로 쭉 진행하면서 나온 값들을 쭉 더해온 값입니다. 왼쪽 부분합은 왼쪽부터 진행한 것입니다.

 

이 부분합들을 각각 정렬합니다. 그리고 투포인터를 이용하면 두 영역에 모두 걸쳐있는 영역의 답을 구할 수 있습니다.

분할정복으로 두 영역에 대해 답을 구하고 투포인터로 합쳐주면 됩니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
using namespace std;
long long int r[300000], l[300000],cnt=0,mm,sum[300000];
void find(long long int s, long long int e) {
	if (s == e) {
		if (r[s] >= mm) cnt++;
		return;
	}
	find(s, (s + e) / 2);
	find((s + e) / 2 + 1, e);
	long long int m = (s + e) / 2 + 1, i, tar = m;
	for (i = m;i <= e;i++) {
		while (1) {
			if (tar == s) break;
			if (l[i] + r[tar - 1] >= mm) tar--; else break;
		}
		cnt += m - tar;
	}
	for (i = m;i <= e;i++)l[i] += sum[m - 1] - sum[s - 1];
	for (i = s;i < m;i++) r[i] += sum[e] - sum[m - 1];
	sort(r + s, r + e + 1);
	sort(l + s, l + e + 1);
}
int main() {
	long long int n, i, j;
	scanf("%lld%lld", &n, &mm);
	for (i = 1;i <= n;i++) {
		long long int x;
		scanf("%lld", &x);
		l[i] = x;
		r[i] = x;
		sum[i] = sum[i - 1] + x;
	}
	find(1, n);
	printf("%lld", cnt);
	return 0;
}