nyoj 856

本文主要是介绍nyoj 856，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.nyist.net/JudgeOnline/problem.php?pid=856

描述

有n个剑客（编号1~n）相约华山比剑，分 m 次决斗，为了节省时间，每次决斗 编号在[l,r]的剑客一起决斗，然后xi获胜。当进行下一次决斗，失败后的剑客可能再参与到决斗，m 次决斗后可能不止一位获胜者（没有失败过就视为获胜者）。

输入

多组测试数据。
对于每组测试数据，第一行输入n和m。接下来输入m行，每行输入l，r，xi。
2 ≤ n ≤ 3*10^5; 1 ≤ m ≤ 3*10^5，l ≤ xi ≤ r

输出

每组测试数据输出n个数字，数字间用空格隔开。第i个数子表示第一次击败i号剑客的剑客编号，若i号剑客是最后的获胜者，输出0；

样例输入

3 2
1 2 2
1 3 2

样例输出

2 0 2

来源

飘谊系列

上传者

TC_张友谊

训练时候的题目，看到区间更新，马上想到线段树，写完，然后悲催了，交了几次，WA了，调试几次没找出错误，最后手动搜的题解，都是泪。。。

话说对于线段树还是不够深入理解，看来得抽个时间写个线段树专题了，嗯。。。

回归主题：这道题看似区间更新，其实还是个点更新，但是不能够每次都搜到最底层去修改，因为题目要求只要是被打败了，就不必再更新了，所以，每次更新标记一下，当搜索到某个区间标记更新了的时候，就直接返回，没必要再更新，，同样，向上更新父节点时，也必须子节点全部更新，才能标记父节点更新。。。

#include <cstdio>
#include <cstring>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1int T[300005<<2];
int ans[300005];
int n,m;void update(int l,int r,int rt,int L,int R,int val){int mid;if(T[rt])return ;if(l==r){if(T[rt]==0&&l!=val&&L==l) {T[rt]=1;ans[l]=val;}return ;}mid=(l+r)>>1;if(R<=mid)update(lson,L,R,val);else if(L>mid)update(rson,L,R,val);else{update(lson,L,mid,val);update(rson,mid+1,R,val);}T[rt]=T[rt<<1]&&T[rt<<1|1];
}int main(){int i,j,l,r,w;while(~scanf("%d%d",&n,&m)){memset(T,0,sizeof(T));//多组数据记得初始化 memset(ans,0,sizeof(ans));for(i=0;i<m;i++){scanf("%d%d%d",&l,&r,&w);update(1,n,1,l,r,w);}for(i=1;i<=n;i++)printf(i==1?"%d":" %d",ans[i]);printf("\n");}return 0;
}

方才博客上看到了大神的另外一种解法，觉得好神奇，，并查集思想还可以这麽用

直接贴代码：

#include <cstdio>
#include <cstring>int T[300005];//T[i]存储从i开始往后的第一个未被打败的人的编号
int ans[300005];//存结果
int n,m;void init()
{int i;for(i=0;i<=n+1;i++){T[i]=i;//刚开始每个人都没有被打败ans[i]=0;}
}int find(int x)//查找未被打败的人，顺便路径压缩
{return T[x]==x?x:T[x]=find(T[x]);
}int main()
{int i,j,l,r,w;while(~scanf("%d%d",&n,&m)){init();for(i=0;i<m;i++){scanf("%d%d%d",&l,&r,&w);for(j=find(l);j<=r;j=find(j+1))//先找到l之后的第一个未被打败的人作为初始值，更新这个点，然后往后循环找（l+1......）{if(j==w)continue;ans[j]=w;if(j<w)//如果一个编号在胜利者的前面，则它后面第一个未被打败的人和此次胜利者存储相同。。注：这里可以写作T[j]=find(w);但是没必要T[j]=w;elseT[j]=r+1;//如果一个数在胜利者后面，则他应该存的第一个未被打败的人应该是和r+1相同。。此处可以写作：T[j]=T[r+1]或者T[j]=find(r+1);}}for(i=1;i<=n;i++)printf(i==1?"%d":" %d",ans[i]);printf("\n");}return 0;
}

这篇关于nyoj 856的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---