KOI 2018 고등부 3번 조화로운 행렬

boj 15977

이 문제의 해결 방법에 대한 아이디어 및 코드 출처(koosaga님), 설명은

2020/01/24 - [분류 전체보기] - dp와 분할정복으로 LIS 해결

에서 충분히 하였다.

 

본 문제를 다시 설명하면

$m=2$일 때는 첫 째 행에 대해 정렬시켰을 때 두 번째 행에 대한 lis를 구하는 문제이므로 간단하다.

 

$m=3$일 때가 중요한데...

마찬가지로 같은 아이디어를 적용하면 첫 째 행에 대해 정렬시켰을 때 pair에 대한 lis를 구하는 문제로 바뀐다.

그리고 이 문제에 대한 핵심 아이디어 dp와 divide&conquer 풀이법은 이전글에서 설명하였다.

항이 하나 늘어나기는 했으나 핵심은 같다.

단, 원소의 범위가 $1$~$10^9$ 이므로 좌표 압축을 해야 한다.

따라서 코드로 설명을 대체한다.

 

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<queue>
#include<utility>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<cmath>
#include<time.h>
using namespace std;

/*koosaga님의 풀이를 보고 공부했음
아이디어: https://codeforces.com/blog/entry/43319
의 koosaga님의 댓글
*/
typedef pair<int,int> P;
int m,n;
/*dp[i]: i번째 pair까지 써서 만들 수 있는 lis 길이*/
int dp[200010];

/*BIT*/
int fen[200010];
vector<P> v;

struct S{
	int xx,yy,z;
	bool operator< (const S &tmp)const{
		return xx<tmp.xx;
	}
};

void add(int pos,int val){
	pos++;
	while(pos<200010){
		fen[pos]=max(fen[pos],val);
		pos+=(pos&-pos);
	}
}
void erase(int pos){
	pos++;
	while(pos<200010){
		fen[pos]=0;
		pos+=(pos&-pos);
	}
}
int query(int pos){
	int ret=0;
	pos++;
	while(pos>0){
		ret=max(ret,fen[pos]);
		pos-=(pos&-pos);
	}
	return ret;
}
//분할 정복
void solve(int s,int e){
	if(s==e) {dp[s]++;return;}
	int mid=(s+e)/2;
	solve(s,mid);
	
	vector<S> l,r;
	for(int i=s;i<=mid;i++) l.push_back((S){v[i].first,v[i].second,dp[i]});
	for(int i=mid+1;i<=e;i++) r.push_back((S){v[i].first,v[i].second,i});
	sort(l.begin(),l.end());
	sort(r.begin(),r.end());
	int ptr=0;
	int len=l.size();
	for(S here:r){
		while(ptr<len && l[ptr].xx<here.xx){
			add(l[ptr].yy,l[ptr].z);
			ptr++;
		}
		dp[here.z]=max(dp[here.z],query(here.yy-1));
	}
	for(int i=0;i<ptr;i++) erase(l[i].yy);
	
	solve(mid+1,e);
}

int main(){
	cin>>m>>n;
	/*이 경우는 첫째 행에 대한 lis구하는 것과 동일하다*/
	if(m==2){
		vector<P> v1(n);
		for(int i=0;i<n;i++) scanf("%d",&v1[i].first);
		for(int i=0;i<n;i++) scanf("%d",&v1[i].second);
		sort(v1.begin(),v1.end());
		//이제 lis 길이를 구하자
		vector<int> ans;
		for(int i=0;i<n;i++){
			if(ans.empty()) ans.push_back(v1[i].second);
			else{
				vector<int>::iterator it=lower_bound(ans.begin(),ans.end(),v1[i].second);
				if(it==ans.end()) ans.push_back(v1[i].second);
				else *it=v1[i].second;
			}
		}
		cout<<ans.size();
	}
	/*이 경우는 첫째 행에 대한 pair에 대한 lis를 구하는 것과 동일하다*/
	else{
		vector<pair<int,P> > d(n);
		for(int i=0;i<n;i++) scanf("%d",&d[i].first);
		for(int i=0;i<n;i++) scanf("%d",&(d[i].second).first);
		for(int i=0;i<n;i++) scanf("%d",&(d[i].second).second);
		sort(d.begin(),d.end());
		/*compress*/
		vector<int> x,y;
		for(int i=0;i<n;i++) x.push_back((d[i].second).first);
		for(int i=0;i<n;i++) y.push_back((d[i].second).second);
		sort(x.begin(),x.end());
		sort(y.begin(),y.end());
		for(int i=0;i<n;i++){
			int a,b;
			a=lower_bound(x.begin(),x.end(),d[i].second.first)-x.begin();
			b=lower_bound(y.begin(),y.end(),d[i].second.second)-y.begin();
			v.push_back(P(a,b));
		}
		//이제 pair로 이루어진 v의 lis를 구하면 된다.
		solve(0,n-1);
		cout<< *max_element(dp,dp+n);
	}
	return 0;
}