백준 25606 장마

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

25606번: 장마

 

풀이 

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

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

1689번: 겹치는 선분

imos알고리즘에 대해서 공부해봅시다. 별로 어려운 개념이 아닙니다.

 

 

1. 핵심 아이디어

 

t번째 날까지의 총 증발한 물의 양을 SumE[t]라고하자.

t번째 날까지의 a_i의 합을 Sum[t]라고하면

t번째날에 양동이에 남은 물의 양은 Sum[t] - SumE[t]라고 생각할 수 있다.

 

Sum[t]는 a_i을 누적합을 이용하여 쉽게 구할 수 있다. 

생각하기 어려운건 SumE[t]다.

 

일단 그림을 그려보겠다.

 

문제 예시1의 데이터를 토대로만들어진 표다.

날짜별 각 양동이에서 증발되는 물의 양을 표로 표현한 것이다.

위의 표를 보면 양동이에 물이 증발되는 날짜를 하나의 구간처럼 생각할 수 있다.

 

위의 표에서 특정 날짜에 겹치는 구간의 수는 해당 날에 증발되고 있는 양동이의 수이다!!

 

날짜마다 구간에 (들어갈때 겹치는 구간+1, 나갈때 겹치는구간수 -1) 이런식으로 처리하면

날짜별 겹치는 구간의 수를 구할 수 있고

겹치는 구간의 수는 증발되고 있는 양동이의 수 이므로 해당 날짜에 증발되는 물의 수를 구할 수 있다!!

 

단 구간의 마지막 날짜에서는 양동이에 남은 물만큼만 증발하므로 끝 부분에서 예외처리해야된다.

 

 

쿼리 데이터는 잠시 모아두었다가.

날짜별 정답을 모두 구한뒤 처리한다.(오프라인 쿼리)

 

자세한건 코드를 참고

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

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

const int INF = 999999999999999;
const int Dic[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
//////////////////////////////////////////////////////////////////////// 

int N,M,Q;
int Arr[200002];
vector<int> Arr2[200002];
vector<pair<int,int>> Query;

int QAns[3][200002];
int Sum[200002];
int SumE[200002];

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

	std::cin >> N >> M >> Q;
	for (int i = 1; i <= N; i++)
	{
		std::cin >> Arr[i];

		//누적합을 입력하면서 미리 구해준다.
		Sum[i] = Sum[i - 1] + Arr[i];
	}

	for (int i = 0; i < Q; i++)
	{
		//쿼리를 저장 데이터를 저장후
		//나중에 정답데이터를 구하면 그때처리하자.
		int a, b;
		std::cin >> a >> b;
		Query.emplace_back(a, b);
	}

	for (int i = 1; i <= N; i++)
	{
		int b = i + 1;
		int c = i + 1 + (Arr[i] / M);
		Arr2[b].push_back(i); //구간 시작
		Arr2[c].push_back(-i); //구간 끝
	}

	int cnt = 0; //겹치는 구간수

	for (int i = 1; i <= N; i++)
	{
		int RemainValue = 0; //끝부분 예외처리
		for (int j = 0; j < Arr2[i].size(); j++)
		{
			if (Arr2[i][j] > 0)
			{
				//구간 진입
				cnt++;
			}
			else
			{
				//구간 탈출
				cnt--;

				//구간 끝부분의 값을 더해준다.
				RemainValue += Arr[-Arr2[i][j]] % M;
			}
		}

		//해당 날짜에 증발한 물의 양
		int nowE = cnt * M + RemainValue;

		SumE[i] = SumE[i-1] + nowE;

		//쿼리데이터 처리
		QAns[2][i] = nowE;
		QAns[1][i] = Sum[i] - SumE[i];
	}

	for (int i = 0; i < Q; i++)
	{
		//쿼리에 해당하는 답을 출력
		int a = Query[i].first;
		int b = Query[i].second;
		cout << QAns[a][b] << endl;
	}
}