CodeForces 356A - Knight Tournament

题目背景和大致意思是，王国要举行骑士比赛。
骑士编号从1—N；开始给定骑士的数目和比赛的场数。
接着每一行给定一个区间L和R，和一个骑士编号X，区间L—R里面的人都被X击败。
骑士被击败以后就出局，不在继续参加。
最后输出每个人是谁击败的他，如果没人击败他，那么他肯定赢到最后，是冠军，输出0；


这道题数据范围很大，每次都是区间操作，如果暴力去做，肯定会超时。
分析以下，一旦 一个人被击败过，那么他肯定不会再出现。
这有点想Set的性质，每个元素只会出现一次，且可以随意删除。
于是这道题目可以用Set做，每次给定一个区间，删除这个区间里面的所有数字，当然删除过的不会再删除。

给删除的人标记击败他们的人，最后输出一个数组，保存击败他们的人的编号。

看到有人说不能直接删除，于是先标记在删除。

但是好像直接删除并没有影响。不是很清楚Set的原理

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<set>
using namespace std;

set<int> s;
set<int>::iterator it,k,tmp[1000005];
int a[1000005];
int n,m,num;
int l,r,x;
int main()
{
	int i,j;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		s.clear();
		memset(a,0,sizeof(a));
		for(i=1;i<=n;i++)
			s.insert(i);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&l,&r,&x);
			k=s.lower_bound(l);//二分查找找第一个大于等于L的数字
			num=0;
			for(it=k;*it<=r&&it!=s.end();it++)
			{
				if(*it!=x)
				{
					a[*it]=x;
					tmp[num++]=it;
				}
			}
			for(j=0;j<num;j++)//先标记再删除
				s.erase(tmp[j]);
		}
		for(i=1;i<n;i++)
			printf("%d ",a[i]);
		printf("%d\n",a[n]);
	}
	return 0;
}