有一个由 \(0\) 和 \(1\) 构成的序列 \(a\) ，长度为 \(n\) .
有 \(m\) 个限制，其中第 \(i\) 个限制为区间 \([l_i,r_i]\) 中，\(1\) 必须出现至少 \(x_i\) 次.
保证一定有解.
问最少有多少个 \(1\) . 需要输出方案.
\(1\leq n\leq 2\cdot 10^5,1\leq m\leq \min(2\cdot 10^5,\frac{n(n+1)}{2})\)
做法1
看到这个至少出现 \(x_i\) 次的限制，就想到了差分约束 .
最大化 \(0\) 的个数 .
由 \(i\) 向 \(i+1\) 连一条权值为 \(1\) 的边，由 \(i+1\) 向 \(i\) 连一条权值为 \(0\) 的边 .
由 \(l_i-1\) 向 \(r_i\) 连一条全值为 \(r_i-l_i+1-x_i\) 的边 .
因为保证了有解，那么就说明没有负环 . 可以用 dijkstra .
时间复杂度 : \(O(n\log (n+m))\)
空间复杂度 : \(O(n+m)\)
code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
while(ch<‘0‘||ch>‘9‘)ch=getchar();
int res=0;
while(ch>=‘0‘&&ch<=‘9‘){
res=res*10+ch-‘0‘;
ch=getchar();
}
return res;
}
const int inf=1e9+10;
int n,m;
vector<pair<int,int> >g[200010];
int dist[200010];
priority_queue<pair<int,int> >Q;
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
n=read();m=read();
for(int i=0;i<n;i++){
g[i].push_back(make_pair(i+1,1));
g[i+1].push_back(make_pair(i,0));
}
for(int i=0;i<m;i++){
int l=read(),r=read(),x=read();
g[l-1].push_back(make_pair(r,r-l+1-x));
}
for(int i=0;i<=n;i++)dist[i]=inf;
dist[0]=0;
Q.push(make_pair(-dist[0],0));
while(!Q.empty()){
int val=-Q.top().first,x=Q.top().second;
Q.pop();
if(dist[x]<val)continue;
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i].first,w=g[x][i].second;
if(dist[to]>dist[x]+w){
dist[to]=dist[x]+w;
Q.push(make_pair(-dist[to],to));
}
}
}
for(int i=1;i<=n;i++)cout<<dist[i-1]-dist[i]+1<<" ";
cout<<endl;
return 0;
}
/*inline? ll or int? size? min max?*/
做法2
这个贪心好像比较套路 . 把要求按照 \(r_i\) 为第一关键字，从小到大，\(l_i\) 为第二关键字，从大到小，排序 . 用 bit 计算连续区间 \(1\) 出现的次数 .
排完序后依次访问询问，如果当前 \(1\) 的数量不及 \(x_i\) ，那么就从后往前放入 \(1\) 并跟新 bit ，直到满足条件 .
时间复杂度 : \(O((n+m)\log(n+m))\)
空间复杂度 : \(O(n+m)\)
code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
while(ch<‘0‘||ch>‘9‘)ch=getchar();
int res=0;
while(ch>=‘0‘&&ch<=‘9‘){
res=res*10+ch-‘0‘;
ch=getchar();
}
return res;
}
int n,m;
int bit[200010];
inline int sum(int i){
int res=0;
while(i){
res+=bit[i];
i-=i&-i;
}
return res;
}
inline void add(int i){
while(i<=n){
bit[i]++;
i+=i&-i;
}
}
stack<int>s;
vector<pair<int,int> >v[200010];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
n=read();m=read();
for(int i=0;i<m;i++){
int l=read(),r=read(),x=read();
v[r].push_back(make_pair(l,x));
}
for(int i=1;i<=n;i++){
sort(v[i].begin(),v[i].end());
reverse(v[i].begin(),v[i].end());
}
for(int i=1;i<=n;i++){
s.push(i);
for(int j=0;j<(int)v[i].size();j++){
int l=v[i][j].first,x=v[i][j].second,num=x-sum(i)+sum(l-1);
for(int k=0;k<num;k++){
add(s.top());
s.pop();
}
}
// for(int j=1;j<=n;j++)cout<<sum(j)-sum(j-1)<<" ";
// cout<<endl;
}
for(int i=1;i<=n;i++)printf("%d ",sum(i)-sum(i-1));
printf("\n");
return 0;
}
/*inline? ll or int? size? min max?*/