CF - Div2 - 207 - C 문제 + 선분 트 리

단순 선분 나무...
구간 업데이트
/*
   +    +    
update      ab    c
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<math.h>
typedef long long ll;
//typedef __int64 int64;
const int maxn = 300005;
const int maxm = 1005;
const int inf = 0x7FFFFFFF;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
#define LEFT( x ) (x<<1)
#define RIGHT( x ) ((x<<1)+1)
struct node{
    int l,r,win;
    int flag;
}tree[ maxn<<2 ];

struct QQ{
    int x,y;
    int win;
}a[ maxn ];

void pushdown( int n ){
    if( tree[ n ].flag!=0 ){
        tree[ LEFT( n ) ].flag = tree[ RIGHT( n ) ].flag = tree[ n ].flag;
        tree[ LEFT( n ) ].win =  tree[ n ].win;//tree[ n ].flag*((m+1)/2);
        tree[ RIGHT( n ) ].win = tree[ n ].win;//tree[ n ].flag*( m-(m+1)/2 );
        tree[ n ].flag = 0;
    }
    return;
}
void build( int l,int r,int n ){
    if( l==r ){
        tree[ n ].win = 0;
        tree[ n ].flag = 0;
        tree[ n ].l=tree[ n ].r = l;
        return ;
    }
    tree[ n ].win = 0;
    tree[ n ].flag = 0;
    tree[ n ].l = l;
    tree[ n ].r = r;
    int mid;
    mid = (l+r)>>1;
    build( l,mid,LEFT( n ) );
    build( mid+1,r,RIGHT( n ) );
    return;
}
void update( int a,int b,int c,int l,int r,int n ){
    if( a==l&&b==r ){
        tree[ n ].flag = 1;
        tree[ n ].win = c;
        //printf("l = %d,r = %d
c = %d
",l,r,c); return ; } pushdown( n ); int mid; mid = (l+r)>>1; if( mid>=b ) update( a,b,c,l,mid,LEFT( n ) ); else if( mid<a ) update( a,b,c,mid+1,r,RIGHT( n )); else { update( a,mid,c,l,mid,LEFT( n ) ); update( mid+1,b,c,mid+1,r,RIGHT( n ) ); } return ; } int query( int a,int b,int l,int r,int n ){ if( a==l&&b==r ){ //printf("l = %d, r = %d,c = %d
",l,r,tree[n].win); return tree[ n ].win; } pushdown( n ); int mid; mid = (l+r)>>1; if( mid>=b ) return query( a,b,l,mid,LEFT( n ) ); else if( mid<a ) return query( a,b,mid+1,r,RIGHT( n )); else return query( a,mid,l,mid,LEFT( n ) )+query( mid+1,b,mid+1,r,RIGHT( n )); } int main(){ int n,m; while( scanf("%d%d",&n,&m)==2 ){ for( int i=1;i<=m;i++ ){ scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].win); } build( 1,n,1 ); for( int i=m;i>=1;i-- ){ if( a[i].win-1>=a[i].x ) update( a[i].x,a[i].win-1,a[i].win,1,n,1 ); if( a[i].y>=a[i].win+1 )update( a[i].win+1,a[i].y,a[i].win,1,n,1 ); } int f = -1; for( int i=1;i<=n;i++ ){ int ans = query( i,i,1,n,1 ); if( ans==i ) { if(f==-1)printf("0"),f++; else printf(" 0"); } else { if( f==-1 ) printf("%d",ans),f++; else printf(" %d",ans); } } printf("
"); } return 0; }

좋은 웹페이지 즐겨찾기