题目：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[300005*4]; struct sss { int x,y,z; }a[300005]; int n,m; void buildtree(int cnt,int l,int r) { if(cnt>n*4) return; d[cnt].l=l; d[cnt].r=r; int mid=(l+r)/2; buildtree(cnt*2,l,mid); buildtree(cnt*2+1,mid+1,r); } void pushdown(int cnt) { if(d[cnt].val!=0){ d[cnt*2].val=d[cnt].val; d[cnt*2+1].val=d[cnt].val; d[cnt].val=0; } } 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)/2; if(r<=mid) update(cnt*2,l,r,val); else if(l>mid) update(cnt*2+1,l,r,val); else{ update(cnt*2,l,mid,val); update(cnt*2+1,mid+1,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)/2; if(x<=mid) query(cnt*2,x); else query(cnt*2+1,x); } int main() { cin>>n>>m; for(int i=0;i<m;i++){ cin>>a[i].x>>a[i].y>>a[i].z; } buildtree(1,1,n); for(int i=m-1;i>=0;i--){ if(a[i].z-1>=a[i].x) //拆分成两个区间来修改 update(1,a[i].x,a[i].z-1,a[i].z); if(a[i].z+1<=a[i].y) update(1,a[i].z+1,a[i].y,a[i].z); } for(int i=1;i<=n;i++){ query(1,i); } }