[CF 1187C] Vasya And Array

[CF 1187C] Vasya And Array - 1800

문제 설명 : 

n개의 수로 이루어진 수열이 있다. 이 수열에 대해 설명하는 m개의 정보로 수열을 추청해야 하는데 정보는 다음과 같다. t=0일 때는 구간 [l,r]에 해당하는 수가 non decreasing(같거나 오름차순)이고, t=1일 때는  not non decreasing이다. 

풀이 :

테스트 케이스를 직접 손으로 쓰면서 계산해보면 솔루션은 쉽게 나온다. t=1일 때 나온 구간[l,r]들의 합집합을 구해서 t=0일 때의 구간이 이 합집합에 완전히 포함되지 않기만 하면 된다. 문제는 이를 어떻게 구현하느냐이다. 나도 이 문제를 풀 때 여기서 애를 먹었다.

예를 들어 구간[2,3]가 합집합이고 [1,4]가 t=0일 때의 구간이라고 하자. 단순히 배열을 만들어서 arr[i]를 [i,i+1]을 커버하도록 하면 문제가 생길 수 있다. 합집합이 [1,2],[3,4]인 경우와 [1,4]인 경우를 구분하지 못하기 때문이다. 따라서 우리는 구간의 정보를 저장할 더 나은 방법이 필요하다. 여기서 나오는 힌트는 union-find에서 find연산을 떠올리면 된다. find연산에서는 해당 노드의 부모가 누구인지 저장하는 parent배열(줄여서 p[])를 사용한다. 이 문제에서 p배열을 해당 지점의 시작 지점을 저장하는 용도로 사용할 것이다. 예를 들어 방금 위에서 언급한 합집합인 [1,2],[3,4]인 경우에는 p[1]=p[2]=1, p[3]=p[4]=3이 될 것이고, [1,4]인 경우에는 p[1]=p[2]=p[3]=p[4]=1이므로 확실한 차이가 있다. 그러므로 1~4를 보면서 p[]값이 중간에 바뀐다면 단절이 어디선가 되었으리라고 추측할 수 있다. 이 문제를 풀 때도 set에 p[]값을 넣고 set의 size가 1인지 아닌지로 판별을 하는 원리이다. size가 1이면 t=0인 구간이 합집합에 완벽하게 포개지는 것이기 때문에 불가능하다고 하면 된다.

주의할 점 : 

위에서 언급했다시피 수직선 상에서 구간 정보를 나타낼 때 단순 배열로 표현하려고 하면 문제가 생길 수 있다. 그럴 때는 반드시 find연산을 이용하자.

배울 점 : 

-

코드 :

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
priority_queue<int,vector<int>,greater<int>> mpq;
const int SPACE=0,NL=1;  string exm;
inline void showAll(vector<int> &v,int sep){ //0=space,1="\n"
    for(int &here:v) printf("%d%c",here,(sep)?'\n':' '); }
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
inline vector<int> int_seperation(int N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 1009;
 
int arr[SIZE],p[SIZE];
 
vector<pii> q[2];
 
int find(int a){
    if(p[a]==a) return a;
    return p[a]=find(p[a]);
}
 
int main(){
    int n,m;    scanf("%d %d",&n,&m);
    
    exm="NO";
    for(int i=1 ; i<=n ; i++){
        arr[i]=10000;
        p[i]=i;
    }
 
    while(m--){
        int t,l,r;  scanf("%d %d %d",&t,&l,&r);
        q[t].push_back({l,r});
    }
 
    for(int i=0 ; i<q[1].size() ; i++){
        int l=q[1][i].first, r=q[1][i].second;
 
        for(int j=l ; j<=r ; j++){
            p[j]=find(l);
        }
    }
 
    for(int i=0 ; i<q[0].size() ; i++){
        int l=q[0][i].first,r=q[0][i].second;
 
        set<int> si;
        for(int j=l ; j<=r ; j++)
            si.insert(find(j));
 
        if(si.size()==1) exf();        
    }
 
    printf("YES\n");
    for(int i=2 ; i<=n ; i++){
        if(find(i)!=find(i-1)) arr[i]=arr[i-1]-1;
        else arr[i]=arr[i-1];
    }
 
    for(int i=1 ; i<=n ; i++)
        printf("%d ",arr[i]);
 
    return 0;
}