BOJ 17274(카드 공장 (Large))풀이

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

17274번: 카드 공장 (Large)

생각보다 어려웠던 문제였다

구현 자체는 오래 걸리지는 않았는데 생각하는데 오래 걸린 거 같다.

 

처음엔 앞면 기준 정렬된 순서로 앞면 머지 소트 트리와 뒷면 머지 소트 트리 이렇게 두 개의 트리를 만들고 구간을 다른 트리와 바꾸고 합치는 그런 방법을 생각했었는데 그럴 경우 한번 쿼리당 NlogN이라는 시복이 나와서 MNlogN으로 터지게 된다.

 

문제를 잘 생각해보면 M개의 입력 중에서 앞면과 뒷면 두 숫자보다 작다면 변경이 없고 두 숫자보다 크다면 계속 반대로 바뀐다. 또 두수 사이에 있다면 무조건 큰 값이 나오게 된다.

이걸 이용해 문제를 풀어 보겠다.

 

일단 두수 사이에 있는 값들 중 가장 마지막에 나온 값의 위치를 구한다 그 이유는 뒤에서 어떤 입력이 있든 두 수 사이에 들어온 입력이 뒤에 있다면 무조건 큰 수가 나오기 때문이다.

 

그러면 이제 그 위치 다음부터는 두수보다 작은 수 또는 큰 수만 남게 된다. 두 수보다 클 경우 짝수 개면 그대로, 홀수 개면 반대가 된다. 아까 구한 위치 다음부터는 무조건 작거나 큰 수만 있을 것이기 때문에 개수를 구해서 마지막까지 변경을 했을 때 무슨 카드인지 알 수 있다.

 

만약 두수 사이인 카드 없다면 당연히 전체 구간에서 큰 수의 개수일 것이다. 또 가장 마지막이라면 당연히 큰 값일 것이다.

 

 

이제 이걸 시간 안에 구현해주면 된다.

일단 입력을 받고 M개의 입력을 위치와 함께 저장한 뒤 정렬을 한다

그러고 정렬했을때 나오는 위치를 가지고 구간 max 코드와 머지 소트 트리를 만들어 준다.

 

그러고 나서 N번의 반복을 하면서 작은 수를 가지고 카드 값에 대한 lower_bound를 구해주고

큰 수를 가지고 카드 값에 대한 lower_bound를 구해준다.

 

만약 작은 수를 lower_bound를 했을 때 나온 위치의 값이 큰 수 보다 같거나 크다면 두 수 사이에는 값이 없다는 뜻이 되므로 m-작은 값 위치+1 개수가 짝수라면 앞면, 홀수라면 뒷면 값을 더해주면 되고

사이에 값이 있다면 그 사이에서 가장 위치가 나중인 위치를 구간 max 세그로 구해주고 그 위치부터 m까지 앞면, 뒷면 중 큰 수보다 큰 개수를 세준 뒤 짝수 일 경우 큰 값을, 홀수일 경우 작은 값을 더해주면 된다.

 

두수 사이 값이 있으니 두수 사이 값 중 가장 마지막인 값이 호출되었을 때도 무조건 큰 값이 되기 때문에 짝수일 경우 그대로 즉 큰 값을 더해주면 되는 것이다.

시복은 O(NLogM^2)이 된다.

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> nd;
ll n,m;
nd inp[201000];
nd st[201000];
vector<ll>tree(801000);
vector<ll>mst[801000];
ll max(ll a,ll b){
    if(a>b)return a;
    else return b;
}
ll min(ll a,ll b){
    if(a>b)return b;
    else return a;
}
ll build(ll n,ll s,ll e){
    //return 1;
    sort(mst[n].begin(),mst[n].end());
    //return 1;
    if(s==e)return tree[n]=st[s-1].y;
    ll mid=(s+e)/2;
    //return 1;
    return tree[n]=max(build(n*2,s,mid),build(n*2+1,mid+1,e));
}
ll check(ll n,ll s,ll e,ll left,ll right){
    if(right<s||left>e)return 0;
    if(left<=s&&e<=right)return tree[n];
    ll mid=(s+e)/2;
    return max(check(n*2,s,mid,left,right),check(n*2+1,mid+1,e,left,right));
}
void update(ll bucket,ll node,ll start,ll end,ll x){
	if(node<start||end<node)return;
	mst[bucket].push_back(x);
	if(start!=end){
		update(bucket*2,node,start,(start+end)/2,x);
		update(bucket*2+1,node,(start+end)/2+1,end,x);
	}
}
ll get(ll node,ll start,ll end,ll left,ll right,ll x){
	if(left>end||right<start)return 0;
	if(left<=start&&end<=right)return (end-start+1)-(lower_bound(mst[node].begin(),mst[node].end(),x)-mst[node].begin()+1)+1;
	ll mid=(start+end)>>1;
	return get(node*2,start,mid,left,right,x)+get(node*2+1,mid+1,end,left,right,x);
}
ll lb(ll v){
    ll start=0,end=m;
    while(end-start>0){
        ll mid=(start+end)/2;
        if(st[mid].x<v)start=mid+1;
        else end=mid;
    }
    return end+1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ll q,c,d,va,ans=0;
    cin >> n >> m;
    for(int i=0;i<n;i++)cin >> inp[i].x >> inp[i].y;
    for(int i=0;i<m;i++){cin >> st[i].x;st[i].y=i+1;}
    sort(st,st+m);
    for(int i=0;i<m;i++)update(1,i+1,1,m,st[i].y);
    build(1,1,m);
    // 작은 값에선 그냥 같거나 큰수, 작은 값에선 lower_boound 한 값-1
    for(int i=0;i<n;i++){
        ll mi=min(inp[i].x,inp[i].y);
        ll ma=inp[i].x+inp[i].y-mi;
        ll left=lb(mi),right=lb(ma)-1;
        //cout << left << ' ' << right << '\n';
        if(st[left-1].x>=ma){
            if((m-left+1)%2==0)ans+=inp[i].x;//cout << inp[i].x << '\n';
            else ans+=inp[i].y;//cout << inp[i].y << '\n';
        //}
        }else{
            ll mx=check(1,1,m,left,right);
            //cout << '# ' << mx << '\n';
            ll cnt=get(1,1,m,right+1,m,mx+1);
            if(cnt%2==0)ans+=ma;//cout << ma << '\n';
            else ans+=mi;//cout << mi << '\n';
        }
        
    }
    cout << ans;
        
    
    
    


}

return 1이 여기저기 출력이 보이는 이유는 디버깅 때문이다;

 

 

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

11934번: Fortune Telling 2

이문제와 100% 동일한 문제다