ABC216G 找到原题了！！1

SMT0x400 · 2023-12-01 22:37:41 · 题解

之前写过一篇 P1250 最优时间复杂度做法，现在一看，不就是种树的加强版吗。

首先，确定算法流程：（之前贪心正确性之类的证明就不讲了）

• 把所有要求按照右端点从小到大排序。
• 查询该要求所属的区间内被填的数数量。
• 如果不够，就从右往左寻找空位，给这些空位填数。因为从右往左肯定更优。

具体而言，使用平衡树维护一个集合，这个集合代表还能没被填的位置。

查询区间 [l,r] 的时候，我们就查询 r 的排名和 l-1 的排名之差，维护这段区间 0 的个数，就可以求得 1 的个数了；

从某个位置开始，从右往左寻找第一个空位，我们就寻找这个位置的前驱即可。

把 0 变成 1 就只需要删除即可。

时间复杂度：O((n+m)\log n)，因为每个数最多只会被删除一次。

采用 __gnu_pbds::tree 实现，常数略大。

#include<bits/stdc++.h>
#define fo(i,a,b) for(I i=a;i<=b;++i)
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;using I=int;
using namespace __gnu_pbds;tree<I,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>s;
const I N=200010;
I n,m,l[N],r[N],w[N],id[N],ans;
bool bz[N];
I main(){ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    fo(i,1,n)s.insert(i);
    fo(i,1,m)cin>>l[i]>>r[i]>>w[i],id[i]=i;
    sort(id+1,id+m+1,[=](I a,I b){return r[a]<r[b];});
    fo(i,1,m){I L=l[id[i]],R=r[id[i]],W=w[id[i]],
        t=(R-L+1)-(s.order_of_key(R+1)-s.order_of_key(L));
        auto it=s.upper_bound(R);
        if(it==s.begin())continue;
        --it;
        while(t<W){
            ++t;++ans;
            if(it==s.begin()){s.erase(it);break;}
            --it;s.erase(next(it));
        }
    }for(I i:s)bz[i]=1;
    fo(i,1,n)printf("%d ",!bz[i]);
    return 0;
}