题解：[ABC216G] 01Sequence

chenxi2009 · 2024-12-25 21:46:28 · 题解

思路

贪心。P1250 加强版。

贪心思路：序列初始全为 0。把所有限制按右端点排序，依次采用选取区间内最靠右的 0 变为 1 的方式满足。这样每次选取的点会尽可能地在多个区间的交集。

考虑使用树状数组维护区间内 1 的个数，这样可以快速得知一个限制内还需要多少个 1。找寻最右端的 0 可以通过 set 维护。时间复杂度 O((N+M)\log N)。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l,r,x;
    bool friend operator < (const node &a,const node &b){
        return a.r < b.r;
    }
}; 
int n,m,c[200001];
node t[200001];
inline int lowbit(int x){
    return x & -x;
}
inline void upd(int x){
    for(;x <= n;x += lowbit(x)) c[x] ++;
    return;
}
inline int qry(int x){
    int rtn = 0;
    for(;x;x -= lowbit(x)) rtn += c[x];
    return rtn;
}
set<int>s;
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) s.insert(i);//维护 0 的集合
    for(int i = 1;i <= m;i ++) scanf("%d%d%d",&t[i].l,&t[i].r,&t[i].x);
    sort(t + 1,t + m + 1);//限制排序
    for(int i = 1;i <= m;i ++){
        int num = qry(t[i].r) - qry(t[i].l - 1);//这段区间内已有 1 的个数
        if(num >= t[i].x) continue;
        num = t[i].x - num;//还需要 1 的个数
        for(int j = 1;j <= num;j ++){
            auto it = s.upper_bound(t[i].r);
            upd(*(-- it));//第一个超出范围的 0 左边就是最右边的范围内的 0，把它改为 1
            s.erase(*it);
        }
    }
    for(int i = 1;i <= n;i ++) printf("%d ",!s.count(i));//判断是否在 0 集合中
    return 0;
}