CF 356A Knight Tournament（并查集）

#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
using namespace std ;  
  
const int maxn = 300003 ;  
int fa[maxn] , col[maxn] ;  
  
int find ( int a ) {  
    return ( fa[a] == a ? a : fa[a] = find ( fa[a] ) ) ;  
}  
  
void jion ( int l , int r , int c ) {  
    while ( l <= r ) {  
        int x = find ( l ) ;  
        if ( x == l ) {  
            col[l] = c ;  
            fa[l] = l + 1 ;  
        }  
        l = fa[l] ;  
    }  
}  
  
int main () {  
    int n , i , m ;  
    scanf ( "%d%d" , &n , &m ) ;  
    for ( i = 1 ; i <= n + 1 ; i ++ ) fa[i] = i ;  
    while ( m -- ) {  
        int l , r , x ;  
        scanf ( "%d%d%d" , &l , &r , &x ) ;  
        jion ( l , x - 1 , x ) ;  
        jion ( x + 1 , r , x ) ;  
    }  
        for ( i = 1 ; i <= n ; i ++ )  
            printf ( "%d " , col[i] ) ;  
        puts ( "" ) ;  
    return 0 ;  
}