[백준-10800] 컬러볼

20만의 입력값에 대응하기 위해 nlogn 또는 n의 복잡도로 문제를 풀어야 한다.

이를 위해 누적합을 통해 문제를 풀 수 있다. 다만 전체 합에 대한 누적합과 각 색상에 대한 누적합을 따로 구하여 해당 값을 처리해주면 된다. 이를 2가지 방법으로 구현하였다.

1. 각 색상에 대한 누적합을 구해놓고, 각각의 답을 구할 시에 이분탐색을 돌린다.
2. 모든 명령어를 정렬한 뒤 색에 대한 누적합과 전체에 대한 누적합을 동시에 진행해준다.

#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

LL input;
LL arr[2001];
LL all_sum[2001];
vector<vector<LL>> v(200001);
vector<vector<LL>> col_sum(200001);

// 입력값이 100만 -> nlogn 으로 끝내야 한다.
int main() {
	int n;
	scanf("%d", &n);

	LL a, b;
	queue<pii> q;
	
	for (int i = 0; i < n; i++) {
		scanf("%lld %lld", &a, &b);
		v[a].push_back(b);
		arr[b] += 1;
		q.push({ a,b });
	}
	
	// 전체 합 구하기
	for (LL i = 1; i <= 2000; i++) 
		all_sum[i] = i * arr[i] + all_sum[i - 1];

	// color 별 합 메모
	for (int i = 1; i <= n; i++) {
		if (v[i].empty()) continue;
		sort(v[i].begin(), v[i].end());
		for (int j = 0; j < v[i].size(); j++) {
			if (j == 0) {
				col_sum[i].push_back(v[i][j]);
				continue;
			}
			col_sum[i].push_back(col_sum[i].back() + v[i][j]);
		}
	}
	

	pii cur;
	while (!q.empty()) {
		cur = q.front();
		q.pop();
		LL sum = 0;
		int idx = lower_bound(v[cur.first].begin(), v[cur.first].end(), cur.second) - v[cur.first].begin();
		if (idx == 0) 
			sum = 0;
		else 
			sum = col_sum[cur.first][idx - 1];
		LL ans = all_sum[cur.second - 1] - sum;
		printf("%lld\n", (ans < 0) ? 0 : ans);
	}
	
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string.h>
#include <math.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

LL input;
LL col_sum[200001];
LL size_sum[2001];

struct Ball {
	int idx;
	LL col, val;
	LL ret;
};

bool cmp(Ball &a, Ball &b) {
	if (a.val == b.val) {
		return a.col < b.col;
	}
	return a.val < b.val;
}
bool cmp1(Ball& a, Ball& b) {
	return a.idx < b.idx;
}
// 입력값이 100만 -> nlogn 으로 끝내야 한다.
int main() {
	int n, a, b;
	scanf("%d", &n);
	vector<Ball> all_arr(n);

	for (int i = 0; i < n; i++) {
		scanf("%lld %lld", &all_arr[i].col, &all_arr[i].val);
		all_arr[i].idx = i;
	}
	
	sort(all_arr.begin(), all_arr.end(), cmp);

	LL sum = 0;
	for (int i = 0; i < n; i++) {
		LL col = all_arr[i].col;
		LL val = all_arr[i].val;

		// 해당 색의 현재 누적합
		col_sum[col] += val;
		
		// 같은 크기의 누적합
		size_sum[val] += val;

		// 전체의 현재 누적합
		sum += val;

		all_arr[i].ret = sum - col_sum[col] - size_sum[val] + val;
		if (i != 0 && col == all_arr[i - 1].col && val == all_arr[i - 1].val) {
			all_arr[i].ret = all_arr[i - 1].ret;
		}
	}
	sort(all_arr.begin(), all_arr.end(), cmp1);

	for (int i = 0; i < n; i++) {
		printf("%lld\n", all_arr[i].ret);
	}

	return 0;
}

https://www.acmicpc.net/problem/10800

10800번: 컬러볼