题目:http://codeforces.com/problemset/problem/356/A
题意:首先给你n,m,代表有n个人还有m次描述,下面m行,每行l,r,x,代表l到r这个区间都被x所击败了(l<=x<=r),被击败的人立马退出游戏让你最后输出每个人是被谁击败的,最后那个胜利者没被
人击败就输出0
思路:他的每次修改的是一个区间的被击败的人,他而且只会记录第一次那个被击败的人,用线段树堕落标记的话他会记录最后一次的,所以我们倒着来修改,
然后因为那个区间里面还包含了自己,在线段树操作里面修改不太方便,所以我们采用把他拆分成两个区间来操作
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct tree
{
int l,r;
int val;
}d[*];
struct sss
{
int x,y,z;
}a[];
int n,m;
void buildtree(int cnt,int l,int r)
{
if(cnt>n*) return;
d[cnt].l=l;
d[cnt].r=r;
int mid=(l+r)/;
buildtree(cnt*,l,mid);
buildtree(cnt*+,mid+,r);
}
void pushdown(int cnt)
{
if(d[cnt].val!=){
d[cnt*].val=d[cnt].val;
d[cnt*+].val=d[cnt].val;
d[cnt].val=;
}
}
void update(int cnt,int l,int r,int val){
if(l==d[cnt].l&&r==d[cnt].r){
d[cnt].val=val;
return;
}
pushdown(cnt);
int mid=(d[cnt].l+d[cnt].r)/;
if(r<=mid) update(cnt*,l,r,val);
else if(l>mid) update(cnt*+,l,r,val);
else{
update(cnt*,l,mid,val);
update(cnt*+,mid+,r,val);
} }
void query(int cnt,int x)
{
if(d[cnt].l==d[cnt].r){
if(d[cnt].val==x) printf("0 ");
else printf("%d ",d[cnt].val);
return;
}
pushdown(cnt);
int mid=(d[cnt].l+d[cnt].r)/;
if(x<=mid) query(cnt*,x);
else query(cnt*+,x); }
int main()
{
cin>>n>>m;
for(int i=;i<m;i++){
cin>>a[i].x>>a[i].y>>a[i].z;
}
buildtree(,,n);
for(int i=m-;i>=;i--){
if(a[i].z->=a[i].x) //拆分成两个区间来修改
update(,a[i].x,a[i].z-,a[i].z);
if(a[i].z+<=a[i].y)
update(,a[i].z+,a[i].y,a[i].z);
}
for(int i=;i<=n;i++){
query(,i);
}
}