codeforces356A Knight Tournament 并查集或线段树成端更新

Hooray! Berl II, the king of Berland is making a knight tournament. The king has already sent the message to all knights in the kingdom and they in turn agreed to participate in this grand event.

As for you, you're just a simple peasant. There's no surprise that you slept in this morning and were late for the tournament (it was a weekend, after all). Now you are really curious about the results of the tournament. This time the tournament in Berland went as follows:

There are n knights participating in the tournament. Each knight was assigned his unique number — an integer from 1 to n.
The tournament consisted of m fights, in the i-th fight the knights that were still in the game with numbers at least li and at most rihave fought for the right to continue taking part in the tournament.
After the i-th fight among all participants of the fight only one knight won — the knight number xi, he continued participating in the tournament. Other knights left the tournament.
The winner of the last (the m-th) fight (the knight number xm) became the winner of the tournament.

You fished out all the information about the fights from your friends. Now for each knight you want to know the name of the knight he was conquered by. We think that the knight number b was conquered by the knight number a, if there was a fight with both of these knights present and the winner was the knight number a.

Write the code that calculates for each knight, the name of the knight that beat him.

Input

The first line contains two integers n, m (2 ≤ n ≤ 3·105; 1 ≤ m ≤ 3·105) — the number of knights and the number of fights. Each of the following m lines contains three integers li, ri, xi (1 ≤ li < ri ≤ n; li ≤ xi ≤ ri) — the description of the i-th fight.

It is guaranteed that the input is correct and matches the problem statement. It is guaranteed that at least two knights took part in each battle.

Output

Print n integers. If the i-th knight lost, then the i-th number should equal the number of the knight that beat the knight number i. If the i-th knight is the winner, then the i-th number must equal 0.

Sample test(s)input

output

3 1 4 0

input

output

0 8 4 6 4 8 6 1

Note

Consider the first test case. Knights 1 and 2 fought the first fight and knight 1 won. Knights 1 and 3 fought the second fight and knight 3 won. The last fight was between knights 3 and 4, knight 4 won.

题意：n个骑士，m场战斗，每场战斗给定l,r,x,表示骑士[l,r]都被x打败，询问打败每个骑士的骑士编号，最后的胜利者输出0。

解法1：

其实我们一开始一定会想到最朴素的O(n^2)的询问，但是可能大部分的询问都是重复无意义的的,那么就需要我们通过某些操作跳过已经访问过的点，举个例子假设：某次战斗区间为[l,r]，假如又有一次战斗[l',r']，其中l<l'<r,r'>r,因为[l',r]均已访问，那么我们可以直接让l'跳到r+1,即原区间[l,r]被缩成一点，那么可以用并查集完成跳点的操作。详见代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=300000+100;
int p[MAXN],c[MAXN];
int findset(int x)
{
    return p[x]==x?x:p[x]=findset(p[x]);
}
void Union(int l,int r,int x)
{
    while(l<=r)
    {
        int f=findset(l);
        if(f==l)
        {
             p[l]=l+1;
             c[l]=x;
        }
        l=p[l];
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+1;i++)
        p[i]=i;
    memset(c,0,sizeof(c));
    while(m--)
    {
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        Union(l,x-1,x); Union(x+1,r,x);
    }
    for(int i=1;i<=n;i++)
        printf("%d ",c[i]);
    printf("\n");
    return 0;
}

解法二：

线段树成段更新，将m次l,r,x先存下来，倒过来update，最后n次query,么什么好说的，详见代码。

有个比较坑爹的地方，线段树MAXN<<2会RE。。求大神解释= =

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=300000+100;
struct node
{
    int lazy,col;
    int l,r;
}segtree[MAXN<<3];
struct Node
{
    int x;
    int l,r;
}f[MAXN];
void build(int rt,int l,int r)
{
    segtree[rt].lazy=-1;segtree[rt].col=0;
    segtree[rt].l=l;segtree[rt].r=r;
    if(l==r)
        return ;
    int m=(l+r)>>1;
    build(rt<<1,l,m); build(rt<<1|1,m+1,r);
}
void pushdown(int rt)
{
    if(segtree[rt].lazy==-1)
        return ;
    segtree[rt<<1].col=segtree[rt<<1|1].col=segtree[rt].lazy;
    segtree[rt<<1].lazy=segtree[rt<<1|1].lazy=segtree[rt].lazy;
    segtree[rt].lazy=-1;
}
void update(int rt,int l,int r,int x)
{
    if(r<l)
        return ;
    pushdown(rt);
    if(l<=segtree[rt].l && r>=segtree[rt].r)
    {
        segtree[rt].lazy=segtree[rt].col=x;
        return ;
    }

    int m=(segtree[rt].l+segtree[rt].r)>>1;
    if(l<=m)
        update(rt<<1,l,r,x);
    if(r>m)
        update(rt<<1|1,l,r,x);
}
int query(int rt,int x)
{
    if(segtree[rt].lazy!=-1)
        return segtree[rt].lazy;
    if(segtree[rt].l==segtree[rt].r)
        return segtree[rt].col;
    int m=(segtree[rt].l+segtree[rt].r)>>1;
    if(x<=m)
        return query(rt<<1,x);
    else
        return query(rt<<1|1,x);
}
int main()
{
    //freopen("text.txt","r",stdin);
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&f[i].l,&f[i].r,&f[i].x);
    for(int i=m;i>=1;i--)
    {
        if(f[i].x==f[i].l)
            f[i].l++;
        else if(f[i].x==f[i].r)
            --f[i].r;
        else if(f[i].x>f[i].l&&f[i].x<f[i].r)
           update(1,f[i].x+1,f[i].r,f[i].x),f[i].r=f[i].x-1;
       update(1,f[i].l,f[i].r,f[i].x);
    }
    for(int i=1;i<=n;i++)
        printf("%d ",query(1,i));
    printf("\n");
    return 0;
}

秒客网

codeforces356A Knight Tournament 并查集或线段树成端更新

相关文章