本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 15:24:36

现在处理左端点最小的角色，与之配对的演员需要符合以下两个要求：

1. 演员的左端点小于等于角色的左端点。
2. 演员的右端点大于等于角色的右端点。

在满足条件 1 的前提下，事实上演员的左端点是什么已经无所谓了，因为如果一个演员的左端点小于等于当前角色的左端点，那么说明该演员的左端点也同时小于等于其他所有角色的右端点，那么就说明所有满足条件一的演员的左端点事实上互相没有优劣之分。

既然对于满足条件一的演员集合，左端点是什么不重要，那么就关心右端点了。

此时，必定选择右端点大于等于当前角色的演员里面，右端点最小的那个（当然记得满足条件一）。

考虑怎么写程序，可以用 set 实现，不过有更简单的办法，就是将演员和角色一起按左端点升序排列，如果左端点一致就把演员放在前面。

然后，每个角色左边的所有演员就是所有左端点小于等于其的演员。

#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
const int maxn=1e5+5;
int n,m;
struct INFO{
    bool type;
    int l,r,k;
    int id;
}info[maxn*2];
void solve(int id_of_test){
	read(n);
    FOR(i,1,n){
        info[i].type=0;
        read(info[i].l);
        read(info[i].r);
        info[i].id=i;
    }
    read(m);
    FOR(i,1,m){
        info[i+n].type=1;
        read(info[i+n].l);
        read(info[i+n].r);
        read(info[i+n].k);
        info[i+n].id=i;
    }
    sort(info+1,info+n+m+1,[&](INFO& a,INFO& b){
        if(a.l!=b.l)return a.l<b.l;
        if(a.r!=b.r)a.r>b.r;
        return a.type>b.type;
    });
    vi ans(n+1,0);
    set<pii> rem;
    FOR(i,1,n+m){
        if(info[i].type==1){
            rem.insert(mkpr(info[i].r,i))；
        }else{
            auto ptr=rem.lower_bound(mkpr(info[i].r,-1));
            if(ptr==rem.end()){
                puts("NO");
                return;
            }
            int pos=ptr->se;
            ans[info[i].id]=info[pos].id;
            info[pos].k--;
            if(!info[pos].k){
                rem.erase(ptr);
            }
        }
    }
    puts("YES");
    FOR(i,1,n)printf("%d ",ans[i]);
    pln
}