题解 | #涂颜料#

先将涂色区域按照left升序排序。因为left越小覆盖的范围越左。

随后，维护一个小顶堆，根据left判断是否加入这个涂色区域的pair。在小顶堆内，保持right最小的元素始终在顶部。当小顶堆顶部的pair已经不覆盖当前区域时，将其移除。

#include <algorithm>
#include <iostream>
#include <bits/stdc++.h>
#include <queue>
#include <vector>
using namespace std;

bool cmp(vector<int> l1, vector<int> l2){
    if(l1[0]<l2[0]) return true;
    else if(l1[0]==l2[0]){
        if(l1[1]<l2[1]) return true;
        else return false;
    }
    else {
        return false;
    }
}
struct cmp2{
    bool operator () (vector<int> l1, vector<int> l2){
        return l1[1] > l2[1];
    }
};
int main() {
    int n;
    cin>>n;
    int q;
    cin >> q;
    vector<vector<int>> list;
    while(q!=0){
        q--;
        int l, r;
        cin >> l >> r;
        list.push_back({l-1, r-1});
    }
    sort(list.begin(),list.end(), cmp);
    // queue<vector<int>> que;
    priority_queue<vector<int>, vector<vector<int>>, cmp2> que2;
    int cur = 0;
    for(int i=0;i<n;i++){
        while(cur<list.size()&&list[cur][0]<=i){
            que2.push(list[cur]);
            cur++;
        }
        while(!que2.empty()&&que2.top()[1]<i) que2.pop();
        if(que2.size()==0){
            cout<<"O";
        }
        else if(que2.size()%3==0){
            cout<<"B";
        }
        else if(que2.size()%3==1){
            cout<<"R";
        }
        else if(que2.size()%3==2){
            cout<<"G";
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")