TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4404
  • Problem
  • P4404骑士比武
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 时间限制3s,空间限制256m
    Description

    有n名骑士参加比武,编号1到n。
    比武总共进行m场,每场比武中,被打败的骑士自动离场(阵亡)。
    比武是群殴的方式,其中参加第i场比武的是编号在[Li,Ri]这段区间中还健在的骑士。第i场比武结束后,除了获胜的那位骑士(编号为Xi),其他人都离场。我们认为离场的人都是被Xi打败的。
    最后一场(第m场)比武的获胜者Xm,将会成为比武的总冠军。
     

    现在告诉你每场比赛的信息,请你计算出每个骑士是被谁打败的。

    Input Format

    第一行,两个整数n和m (2 ≤ n ≤ 3*10^5; 1 ≤ m ≤3* 10^5)
    接下来m行,每行三个整数:Li,Ri,Xi表示一场比武的信息,比武在编号区间[Li,Ri]中开展,其中获胜的是Xi号骑士。 (1 ≤ li < ri ≤ nli ≤ xi ≤ ri)
    数据保证,每场比赛开始前,对应区间至少有两名骑士健在。

    Output Format

    一行,n个整数,其中第i个数字表示打败第i号骑士的骑士的编号。如果i号骑士是冠军,输出0。

    Sample Input 1

    4 3
    1 2 1
    1 3 3
    1 4 4

    Sample Output 1

    3 1 4 0 

    Sample Input 2

    8 4
    3 5 4
    3 7 6
    2 8 8
    1 8 1

    Sample Output 2

    0 8 4 6 4 8 6 1 

    Sample Input 3

    11 6
    1 2 2
    7 8 7
    3 4 4
    6 9 6
    5 10 10
    2 11 11

    Sample Output 3

    2 11 4 11 10 10 6 7 6 11 0


    Source  CodeForces 356A