CF356A Knight Tournament

题意: 思路:之前频繁地看见这个类型的题目,但是往往又不会做,今天来学习一下 方法1:用一个集合维护每个人存活情况,对于一个序列 [ l , r , x ] [l,r,x] [l,r,x]每次扫描集合中剩余的元素(用lower_bound去找下标),让他们的ans等于x.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
//前向星
// for(int i=head[u];i!=-1;i=nxt[i]) v = to[i]
//int nxt[maxn],head[maxn],to[maxn];// head[u],cnt 初始值是-1
//int tot = -1;
//void add(int u,int v){
//	nxt[++tot] = head[u];
//	head[u] = tot;
//	to[tot] = v;
//}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;cin>>n>>m;
	set s;
	for(int i=1;il>>r>>x;
		vector a;
		for(auto it = s.lower_bound(l);it!=s.end();it++){
			int cur = *it;
			if(cur>r) break;
			if(cur!=x){
				a.pb(cur);ans[cur] = x;
			}
		}
		for(auto y : a) s.erase(y);
	}
	for(int i=1;il>>r>>x;
		int cur = find(l);
		while(cur