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\nc = %d\n",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\n",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("\n");
    }
    return 0;
}