[BOJ] 17163. 가희의 수열놀이 (Large)

문제

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

17163번: 가희의 수열놀이 (Large)

 

풀이

만약 mod가 query개수 보다 많다면 항상 불가능하므로, -1을 출력한다.

 

mod가 query개수보다 작은 경우에는 0~mod-1까지의 index를 가지는 stack을 만들어보자.

그리고 숫자가 새로 들어올때 마다, 해당하는 나머지를 index로 가지는 stack에 현재 arr의 원소의 개수를 넣어준다.

3 query가 들어왔을 때, 각 나머지 별로 stack의 top에 있는 숫자의 min값이 우리가 찾는 index가 되고, 전체 사이즈에서 찾은 값을 빼주면 답이 된다.

 

이 방식으로 구하면 $O(q\times mod)$의 시간복잡도가 걸리지만 segment tree를 이용하면 $O(mod+q log mod)$의 시간복잡도로 원하는 답을 구할 수 있다.

 

Time Complexity : $O(mod+q log mod)$

 

코드

#include<iostream>
#include<vector>
#include<stack>
#define N 1000000
#define INF 1<<30
using namespace std;

stack<int, vector<int> > S;
stack<int, vector<int> > rem[N];

int seg[1<<21];
int p, q, mod;

void update(int t)
{
	t+=p;
	while(t!=1)
	{
		t>>=1;
		seg[t] = min(seg[t<<1], seg[t<<1|1]);
	}
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cin>>q>>mod;
	for(p=mod;p^(-p&p);p+=(-p&p));

	if(mod>q)
	{
		while(q--)
		{
			int x;
			cin>>x;
			if(x==3) cout<<-1<<"\n";
			if(x==1) cin>>x;
		}
		return 0;
	}

	for(int i=p;i<p<<1;i++) seg[i]=i<p+mod?-1:INF;
	for(int i=p-1;i>0;i--) seg[i] = min(seg[i<<1],seg[i<<1|1]);
	while(q--)
	{
		int x;
		cin>>x;
		if(x==1)
		{
			cin>>x;
			int t=x%mod;
			S.push(t);
			rem[t].push(S.size());
			seg[p+t]=S.size();
			update(t);
		}
		else if(x==2)
		{
			if(S.empty())continue;
			int t = S.top();
			S.pop();
			rem[t].pop();
			seg[p+t]=rem[t].empty()?-1:rem[t].top();
			update(t);
		}
		else
		{
			if(seg[1]==-1) cout<<"-1\n";
			else cout<< S.size()-seg[1]+1<<"\n";
		}
	}
}