题目大意
构造一个满足 \(m\) 个形如 \((l,r,x)\) 的限制条件的 \(01\) 序列，其中 \((l,r,x)\) 表示区间 \([l,r]\) 的和不小于 \(x\)，你需要保证序列中 \(1\) 的个数最小。
思路分析
贪心的想，如果我们将限制按右端点排序，那么当遍历到一个区间，发现现有的和不满足限制条件时，一定会从右往左放 \(1\) 直到满足条件，因为只有这样才能让后面的区间放的 \(1\) 更少。
具体过程的实现可以用链表或并查集，也可以用二分套树状数组实现。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=200100;
int n,m,in1,in2,in3;
int res[N];
struct BIT{
int a[N];
#define lowbit(x) ((x)&(-(x)))
void add(int x,int v){
for(int i=x;i<=n+1;i+=lowbit(i)) a[i]+=v;
}
int ask(int x){
int ans=0;
for(int i=x;i;i-=lowbit(i)) ans+=a[i];
return ans;
}
}tree;
struct Node{
int l,r,x;
}a[N];
bool cmp(Node a,Node b){//按右端点从小到大排序
if(a.r!=b.r) return a.r<b.r;
return a.l<b.l;
}
int find(int i){//对于当前的区间二分出下一个应该放的位置
int l=a[i].l,r=a[i].r;
while(l<r){
int mid=(l+r+1)>>1;
if(tree.ask(r)-tree.ask(mid-1)==r-mid+1) r=mid-1;//右半部分放满了
else l=mid;
}
return l;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&in1,&in2,&in3);
a[i]=Node{in1,in2,in3};
}
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++){
int num=a[i].x-(tree.ask(a[i].r)-tree.ask(a[i].l-1)),pos;//找到还差多少
while(num>0){tree.add((pos=find(i)),1);res[pos]=1;num--;}//逐一填充
}
for(int i=1;i<=n;i++) cout<<res[i]<<' ';
return 0;
}