글 읽기 - 15816 퀘스트 중인 모험가

Green55 5년 전 0

풀이의 흐름은 다음과 같습니다

초기 퀘스트의 목록과 쿼리의 목록을 미리 받아놓습니다.
1에서 등장한 모든 퀘스트들을 좌표 압축 시킵니다.
현재 깬 퀘스트 목록을 펜윅트리를 이용해 관리하고, 쿼리는 이분 탐색을 이용해 적절히 구해줍니다.

O(Mlog(N+M))이어서 맞을거라고 생각했는데 시간초과가 나네요. 어디를 고쳐야 할까요?

#include<bits/stdc++.h>
using namespace std;
const int MAX = 2000001, INF = 1123456789;
int n, m, cnt, tree[MAX+1], minQuest=INF, maxQuest=-INF;

//BIT 
int sum(int index){
	int ret = 0;
	while(index){
		ret += tree[index];
		index &= index-1;
	}
	return ret;
}
void add(int index, int value){
	while(index <= cnt){
		tree[index] += value;
		index += index & -index;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	vector<int> firstQuest; //초기에 주어지는 퀘스트 목록
	map<int,int> Quest; //좌표압축을 위한 퀘스트 목록
	vector<pair<int,int>> query; //쿼리 목록
	
	//초기 퀘스트 목록
	cin >> n;
	for(int i=0; i<n; ++i){
		int tmp; cin >> tmp;
		Quest.insert({tmp,0});
		firstQuest.push_back(tmp);
		minQuest = min(minQuest, tmp);
		maxQuest = max(maxQuest, tmp);
	}

	//쿼리 목록 - first == INF면 퀘스트 추가, 그렇지 않으면 개수 출력.
	cin >> m;
	for(int i=0; i<m; ++i){
		int a,b,c;
		cin >> a;
		if(a==1){
			cin >> b;
			Quest.insert({b,0});
			query.push_back({INF, b});
		}
		else{
			cin >> b >> c;
			query.push_back({b,c});
		}
	}

	//좌표 압축 - 제일 작은 퀘스트는 0, 제일 큰 퀘스트는 cnt-1
	//cnt에는 퀘스트의 총 개수가 저장된다.
	for(auto &P : Quest)
		P.second = cnt++;

	//초기 퀘스트 리스트를 BIT에 업데이트 해준다
	for(auto &i : firstQuest)
		add(Quest[i]+1, 1);

	for(auto &P : query){

		//퀘스트 추가
		if(P.first == INF){
			add(Quest[P.second]+1, 1);
			minQuest = min(minQuest, P.second);
			maxQuest = max(maxQuest, P.second);
		}

		//답하기
		else{
			//[L~R]에서 깨지 못한 퀘스트 목록을 답해야한다.
			int L = P.first, R = P.second;

			//현재까지 깬 퀘스트 중 [L~R]에 들어가는 것이 하나도 없으면
			if(R < minQuest|| maxQuest < L){
				cout << R-L+1 << '\n';
				continue;
			}

			//이분탐색으로 [L~R]안에 있으면서 L과 R에 제일 가까운 퀘스트를 찾아준다.
			auto Lit = Quest.lower_bound(L), Rit = Quest.upper_bound(R);

			// 구간의 길이 - 구간 내에서 깬 퀘스트의 개수
			cout << (R-L+1) - ( sum(Rit->second) - sum(Lit->second) ) << '\n';
		}
	}

}