分析
一道差分约束题。
我们令 \(\mathit{sum}_{i}\) 表示 \(1\) 到 \(i\) 中，\(1\) 的数量，根据题意可得：
- \(\mathit{sum}_{l_i-1}+x_i \le \mathit{sum}_{r_i}\)
- \(\mathit{sum}_{l+1} +(-1)\le \mathit{sum}_{l}\)
- \(\mathit{sum}_{l}+0 \le \mathit{sum}_{l+1}\)
因为我们要尽可能地使 \(1\) 的数量少，所以这是求不等式最小解。又因为边权有负，所以我们要跑 spfa 来求解，代码如下：
//sum[l-1]+x<=sum[r]
//sum[l]<=sum[r]
//sum[r]+(-1)<=sum[l]
#include<bits/stdc++.h>
using namespace std;
#define int long long
#pragma G++ optimize(2)
int n,m;
const int N=1e6+10;
int ne[N],e[N],h[N],w[N],idx;
inline void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
inline void read(int &x) {
x=0;
short flag=true;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=flag;
}
int l,r,x;
int dis[N],vis[N];
inline void spfa(){
memset(dis,-0x3f,sizeof(dis));
queue<int> qu;
qu.push(0),dis[0]=0,vis[0]=1;
while(!qu.empty()){
int now=qu.front();
qu.pop();
vis[now]=0;
for(int i=h[now];~i;i=ne[i]){
int j=e[i];
if(dis[j]<dis[now]+w[i]){
dis[j]=dis[now]+w[i];
if(!vis[j]){
vis[j]=1;
qu.push(j);
}
}
}
}
}
signed main(){
memset(h,-1,sizeof(h));
read(n),read(m);
for(register int i=1;i<=m;i++){
read(l),read(r),read(x);
add(l-1,r,x);
}
for(register int i=0;i<n;i++){
add(i,i+1,0);
add(i+1,i,-1);
}
spfa();
for(register int i=1;i<=n;i++){
printf("%lld ",dis[i]-dis[i-1]);//前缀和
}
return 0;
}
很显然，\(1 \le n,m \le 2 \times 10^5\)，超时了。
我们考虑优化方法，可以使用正难则反的思想。如果我们我们令 \(\mathit{sum'}_{i}\) 表示 表示 \(1\) 到 \(i\) 中，\(0\) 的数量，那么再次根据题意就可以把上面的式子变成：
- \(\mathit{sum'}_{r_i}\le \mathit{sum'}_{l_i-1}+(r-l+1-x)\)
- \(\mathit{sum'}_{l+1} \le \mathit{sum'}_{l} +1\)
- \(\mathit{sum'}_{l} \le \mathit{sum'}_{l+1}+0\)
很显然，在我们需要 \(1\) 的数量最少时，该不等式方程组的解就需要最大，而所有的权值又是非负的，所以可以用 dijkstra 求出最短路。注意，求得的解是关于 \(\mathit{sum'}_{i}\) 的，所以我们需要进行取反。
代码
//sum[r]<=sum[l-1]+r-l+1-x
//sum[l]<=sum[l-1]+1
//sum[l-1]<=sum[l]+0
#include<bits/stdc++.h>
using namespace std;
#define int long long
#pragma G++ optimize(2)
#define PII pair<int,int>
#define x first
#define y second
int n,m;
const int N=1e6+10;
int ne[N],e[N],h[N],w[N],idx;
inline void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
inline void read(int &x) {
x=0;
short flag=true;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=flag;
}
int l,r,x;
int dis[N],vis[N];
//inline void spfa() TLE
// memset(dis,-0x3f,sizeof(dis));
// queue<int> qu;
// qu.push(0),dis[0]=0,vis[0]=1;
// while(!qu.empty()){
// int now=qu.front();
// qu.pop();
// vis[now]=0;
// for(int i=h[now];~i;i=ne[i]){
// int j=e[i];
// if(dis[j]<dis[now]+w[i]){
// dis[j]=dis[now]+w[i];
// if(!vis[j]){
// vis[j]=1;
// qu.push(j);
// }
// }
// }
// }
//}
void dj(){
memset(dis,0x3f,sizeof(dis));
priority_queue<PII,vector<PII>,greater<PII> > qu;
dis[0]=0,qu.push({dis[0],0});
while(!qu.empty()){
PII now=qu.top();qu.pop();
if(vis[now.y]) continue;
vis[now.y]=1;
for(int i=h[now.y];~i;i=ne[i]){
int j=e[i];
if(dis[j]>now.x+w[i]){
dis[j]=now.x+w[i];
qu.push({dis[j],j});
}
}
}
}
signed main(){
memset(h,-1,sizeof(h));
read(n),read(m);
for(register int i=1;i<=m;i++){
read(l),read(r),read(x);
//add(l-1,r,x);
add(l-1,r,r-l+1-x);
}
for(register int i=0;i<n;i++){
//add(i,i+1,0);
//add(i+1,i,-1);
add(i,i+1,1);
add(i+1,i,0);
}
//spfa();
dj();
for(register int i=1;i<=n;i++){
printf("%lld ",(dis[i]-dis[i-1]==1?0:1));//取反，也可以用位运算
}
return 0;
}