题意
对于每个要求x[ l , r ],x都满足[ l , r ]中1的个数> = x
构造出这个序列满足上述要求，并且1的个数最小。
思路1：
先按照右端点排序，贪心的考虑，从右端点开始填1，并且用并查集找下一个可以填1的位置。
每次询问[ l , r ]的区间和，如果已经> = x的话就不用再考虑这个区间了。
单点修改区间求和可以用树状数组，时间复杂度O ( n l o g n )
代码1：
const int maxn=2e5+100; int n,m,tr[maxn],root[maxn],ans[maxn]; struct node{ int l,r,num; }q[maxn]; bool cmp(node a,node b){ return a.r<b.r; } int Find(int x){ if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } int lowbit(int x){return x&-x;} void update(int pos){ while(pos<=n) tr[pos]++,pos+=lowbit(pos); } int query(int pos){ int res=0; while(pos) res+=tr[pos],pos-=lowbit(pos); return res; } int main() { n=read,m=read; rep(i,1,m){ q[i].l=read,q[i].r=read,q[i].num=read; } sort(q+1,q+1+m,cmp); rep(i,1,n) root[i]=i; rep(i,1,m){ int now=query(q[i].r)-query(q[i].l-1); if(now>=q[i].num) continue; q[i].num-=now; for(int j=Find(q[i].r);j>=q[i].l&&q[i].num;j=Find(j)){ update(j);root[j]=Find(j-1);q[i].num--;ans[j]=1; } } for(int i=1;i<=n;i++) cout<<ans[i]<<" "; return 0; }
思路2
设x i表示序列中[ 1 , i ]的1的个数，给出的条件就可以转化成x r − x l − 1 > = x，这样就变成经典的差分约束问题了，由于求的是x n的最小值，从l − 1 − > r连一条权值为x的边，跑最长路。由于边权为正，所以不能用d i j k s t r a又会被卡。
所以就转化成0的个数后跑最短路，用d i j k s t r a,注意要从0开始。
代码2
int n,m,dis[maxn]; vector<PII>g[maxn]; bool st[maxn]; void dij(){ memset(dis,0x3f,sizeof dis); dis[0]=0; ///建立一个维护最小值的优先队列 priority_queue<PII,vector<PII>,greater<PII>>heap; heap.push({0,0});///起始点放入队列 while(heap.size()){ PII t=heap.top();///最小值 heap.pop(); int ver=t.second,d=t.first; if(st[ver]) continue;///该点更新 st[ver]=true; for(int i=0;i<g[ver].size();i++){ int j=g[ver][i].first,w=g[ver][i].second; if(dis[j]>d+w){ dis[j]=d+w; heap.push({dis[j],j}); } } } } int main(){ n=read,m=read; rep(i,1,m){ int l=read,r=read,x=read; x=r-l+1-x; g[l-1].push_back({r,x}); } rep(i,0,n-1){ g[i].push_back({i+1,1}); g[i+1].push_back({i,0}); } dij(); rep(i,1,n) printf("%d ", (dis[i]-dis[i-1])^1); return 0; }
