백준 17274 카드 공장 (Large)

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

17274번: 카드 공장 (Large)

문제를 풀기전에 세그먼트트리와 머지소트트리를 공부해오는 걸 추천드립니다!!

 

풀이 

0. 문제를 풀기 앞서서 풀어야되는 문제

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

13537번: 수열과 쿼리 1

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

2357번: 최솟값과 최댓값

1. 핵심 아이디어

특정 카드의 앞면과 뒷면에 적힌 숫자를 a,b라고 하겠습니다. (a < b)

그리고 우리가 주목할 것은 공장장이 외치는 숫자(K)에 따라서 카드의 상태가 변한다는겁니다.

 

첫번째. 공장장이 (K < a)인 숫자를 외치는 경우

카드에 아무런 변화도 없을것입니다.

 

두전째. 공장장이 (a <= k < b)인 숫자를 외치는 경우

만약 a가 앞면인상태라면 b가 앞면인 상태로

b가 앞면인 상태라면 그대로 b인 상태가 됩니다.

즉 무조건 앞면이 b가 됩니다!!

 

세번째. 공장장이 (b < K)인 숫자를 외치는 경우

카드가 뒤집힙니다.

 

 

2. 아이디어를 활용하는 방법

모든 쿼리가 끝난후 카드가 앞면인지 아닌지 판별할 방법이 필요합니다.

바로 직관적인 방법으로 O(NM)의 방법이 떠오르지만 시간복잡도상으로 문제가 많아보입니다.

 

가만히 생각해보면 특정 카드에 대해서 마지막으로 나오는 두번째경우(a <= k < b)의 숫자를 외친이후 부터는

=> 첫번째(K < a)경우와 세번째(b < K)경우 숫자만 나올 것이고

=> 첫번째경우 숫자는 앞뒷면에 영향이 없으므로

=> 세번째경우 숫자로만 앞뒷면에 영향을 받는다는 것

=> 마지막으로 나오는 두번째경우 숫자 이후 나오는 세번째 경우 숫자의 갯수를 구하면

     앞뒷면 상태를 알 수 있다!!

<두번째 경우숫자가 등장하지않으면 전체 쿼리에서 세번째 경우 숫자의 갯수를 구하면됩니다.>

 

M을 크기순으로 정렬한후 마지막으로 

두번째경우에 해당하는 구간에서 가장 마지막으로 나오는 위치를 i라고 하겠습니다.

i는 위에 있는 최솟값과 최댓값 문제를 푸셨으면 쉽게 구하실 수 있습니다.

 

그 후 i에서부터 쿼리가 끝날때까지의 세번째 경우의 갯수를 구하면됩니다. 

이것도 수열과 쿼리 1을 선행해서 푸셨으면 구하실 수 있습니다.

 

코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

using namespace std;

int N, M;
vector<pair<int, int>> Card;
vector<pair<int, int>> Arr;
vector<int> Arr1;
vector<int> Arr2;
vector<int> Array;

vector<int> Tree[1000000];
void Init(int a, int l, int r)
{
	for (int i = l; i <= r; i++)
		Tree[a].push_back(Array[i]);

	if (l == r)
		return;

	sort(Tree[a].begin(), Tree[a].end());

	int m = (l + r) / 2;
	Init(a * 2, l, m);
	Init(a * 2 + 1, m + 1, r);
}

int Query(int a, int l, int r, int s, int e, int b)
{
	int res = 0;

	if (e < l || r < s)
		return 0;

	if (s <= l && r <= e)
	{
		int c = lower_bound(Tree[a].begin(), Tree[a].end(), b) - Tree[a].begin();
		if (0 <= c && c < Tree[a].size())
			return Tree[a].size() - c;
		else
			return 0;
	}

	int m = (l + r) / 2;
	res = Query(a * 2, l, m, s, e, b) + Query(a * 2 + 1, m + 1, r, s, e, b);

	return res;
}
int MaxSeg[1000000];
int InitMax(int a, int l, int r)
{
	if (l == r)
		return MaxSeg[a] = l;
	int m = (l + r) / 2;
	int aa = InitMax(a * 2, l, m);
	int bb = InitMax(a * 2 + 1, m + 1, r);
	
	if (Arr2[aa] > Arr2[bb])
		MaxSeg[a] = aa;
	else
		MaxSeg[a] = bb;

	return MaxSeg[a];
}
int QueryMax(int a, int l, int r, int s, int e)
{
	int res = 0;

	if (e < l || r < s)
		return -1;

	if (s <= l && r <= e)
		return MaxSeg[a];

	int m = (l + r) / 2;

	int aa = QueryMax(a * 2, l, m, s, e);
	int bb = QueryMax(a * 2 + 1, m + 1, r, s, e);

	if(aa < 0)
		res = bb;
	else if (bb < 0)
		res = aa;
	else
	{
		if (Arr2[aa] > Arr2[bb])
			res = aa;
		else
			res = bb;
	}
	return res;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	std::cout.tie(NULL);

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		Card.push_back({ a,b });
	}
	for (int i = 0; i < M; i++)
	{
		int a;
		cin >> a;
		Arr.push_back({ a,i });
		Array.push_back(a);
	}
	sort(Arr.begin(), Arr.end());

	for (int i = 0; i < M; i++)
	{
		Arr1.push_back(Arr[i].first);
		Arr2.push_back(Arr[i].second);
	}

	Init(1, 0, M - 1);
	InitMax(1, 0, M - 1);
	int ans = 0;

	for (int i = 0; i < N; i++)
	{
		int mMin = min(Card[i].first, Card[i].second);
		int mMax = max(Card[i].first, Card[i].second);
		int sp = (lower_bound(Arr1.begin(), Arr1.end(), mMin) - Arr1.begin());
		int ep = (lower_bound(Arr1.begin(), Arr1.end(), mMax) - Arr1.begin());
		int a = 0;

		if (sp < ep)
		{
			int start = QueryMax(1, 0, M - 1, sp, ep - 1);
			start = Arr2[start];
			a = Query(1, 0, M - 1, start+1, M - 1, mMax);
			ans += a % 2 == 0 ? mMax : mMin;
		}
		else
		{
			a = Query(1, 0, M - 1, 0, M - 1, mMax);
			ans += a % 2 == 0 ? Card[i].first : Card[i].second;
		}
	}

	cout << ans << endl;
}