自动搬运

查看原文

来自洛谷，原作者为

	Sunset_afterglow Wir werden den Zweiten Weltkrieg gewinnen || 我是羊我要开始说谎了 || 壶关条件：蓝题 50+ & 橙名及以上 & 除CTJ的人 || 人会背叛但OI不会，不会就是不会，怎么学都不会--Empty_Dream

搬运于2025-08-24 23:14:50，当前版本为作者最后更新于2025-08-07 10:43:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们班的首 A，写篇 Tj 纪念一下，这题我认为建虚点应该是过不了的，毕竟时间复杂度是 $O((n + m)((r-l+1)m))$，也就是 $2.9\times10^{10}$，居然过了，一点都不卡，所以我也不想优化了。

思路

我们观察一下式子 $\min_{l\le x\le r}a_x - \max_{p \le y \le q} a_y\ge ans$，想必大家一定是看完了标签吧，差分约束，感觉如果你刚学就不会来做这题，如果你学过，那你就一眼秒了，我们可以发现这是一个板子，区间与区间连边，经典的线段树优化建图，如果你想认真学习线段树优化建图的话就去看别的题解吧，我不会讲，也可以说是我太菜了，不想写。

这里发现如果 $\min_{l\le x\le r}a_x - \max_{p \le y \le q} a_y\ge ans$，那么 $[l ,r]$ 中的所有数都比 $[p ,q]$ 中的数大 $ans$ 以上，我们可以每次连边建一个虚点 $d$，设其值为 $k$，则 $\forall l\le x\le r \cap p\le y\le q,k - a_x \le -ans \cap a_y - k\le 0$，也就是 add(x ,d ,-ans),add(k ,y ,0)，我们可以直接暴力枚举 $x ,y$，然后将虚点直接建到原序列后面，跑一遍 SPFA，求最短路，此时的 $dist$ 就是 $a$ 的值，没有什么细节我就直接放代码了，硬要说就是判负环时最大更新数其实是 $n + m - 1$。

代码

链式前向星实现

链式前向星实现，最慢的点是 1.90ms，代码如下

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int x = 0 ,f = 1;
	char ch = getchar();
	while('0' > ch || ch > '9') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch & 15);
		ch = getchar();
	}
	return x * f;
}
const int N = 5e4 + 5;
int n ,m;
bool flag[N];
queue<int>que;
int dist[N] ,cnt[N] ,head[4 * N] ,cntt;
struct edge {
	int to;
	int next;
	int dis;
}edge[4 * N];
inline void add(int x ,int y ,int z) {
	edge[++ cntt].to = y;
	edge[cntt].dis = z;
	edge[cntt].next = head[x];
	head[x] = cntt;
  return ;
}
void Spfa() {
  memset(dist ,0x3f ,sizeof dist);
	memset(flag ,0 ,sizeof flag);
  memset(cnt ,0 ,sizeof cnt);
	for(int i = 1;i <= n + m;++ i)
		add(0 ,i ,0);
	while(!que.empty())que.pop();
	que.push(0);
	dist[0] = 0;
	while(!que.empty()){
		int u = que.front();
		flag[u] = 0;
		que.pop();
   for(int xt = head[u];xt;xt = edge[xt].next) {
      pair<int ,int> i = make_pair(edge[xt].to ,edge[xt].dis);
			if(dist[i.first] > dist[u] + i.second) {
				dist[i.first] = dist[u] + i.second;
        cnt[i.first] = cnt[u] + 1;
        if(cnt[i.first] >= n + m) {
          cout << "No Solution";
          return ;
        }
				if(!flag[i.first]) {
					flag[i.first] = true;
					que.push(i.first);
				}
			}
		}
	}
  int answer = LLONG_MAX ,maxx = LLONG_MIN ,minn = LLONG_MAX;
	for(int i = 1;i <= m;++ i) {
    maxx = max(maxx ,dist[i]);
    minn = min(minn ,dist[n + i]);
  }
  cout << maxx - minn;
	return ;
}
signed main() {
  m = read() ,n = read();
  for(int i = 1 ,u ,v ,l ,r ,w;i <= m;++ i) {
    u = read() ,v = read() ,l = read() ,r = read() ,w = read();
    for(int j =  u;j <= v;++ j) add(j ,n + i ,-w);
    for(int j =  l;j <= r;++ j) add(n + i ,j ,0);
  }
  Spfa();
  return 0;
}

邻接表实现

邻接表实现，最慢的点 1.09ms，代码如下。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int x = 0 ,f = 1;
	char ch = getchar();
	while('0' > ch || ch > '9') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch & 15);
		ch = getchar();
	}
	return x * f;
}
const int N = 5e4 + 5;
int n ,m;
bool flag[N];
queue<int>que;
int dist[N] ,cnt[N];
vector<pair<int ,int> >vt[2 * N];
void Spfa() {
  memset(dist ,0x3f ,sizeof dist);
	memset(flag ,0 ,sizeof flag);
  memset(cnt ,0 ,sizeof cnt);
	for(int i = 1;i <= n + m;++ i)
		vt[0].push_back(make_pair(i ,0));
	while(!que.empty())que.pop();
	que.push(0);
	dist[0] = 0;
	while(!que.empty()){
		int u = que.front();
		flag[u] = 0;
		que.pop();
		for(auto i: vt[u]) {
			if(dist[i.first] > dist[u] + i.second) {
				dist[i.first] = dist[u] + i.second;
        cnt[i.first] = cnt[u] + 1;
        if(cnt[i.first] >= n + m + 1) {
          cout << "No Solution";
          return ;
        }
				if(!flag[i.first]) {
					flag[i.first] = true;
					que.push(i.first);
				}
			}
		}
	}
  int answer = LLONG_MAX ,maxx = LLONG_MIN ,minn = LLONG_MAX;
	for(int i = 1;i <= n;++ i) {
    maxx = max(maxx ,dist[i]);
    minn = min(minn ,dist[i]);
  }
  cout << maxx - minn;
	return ;
}
signed main() {
  m = read() ,n = read();
  for(int i = 1 ,u ,v ,l ,r ,w;i <= m;++ i) {
    u = read() ,v = read() ,l = read() ,r = read() ,w = read();
    for(int j =  u;j <= v;++ j) vt[j].push_back(make_pair(n + i ,-w));
    for(int j =  l;j <= r;++ j) vt[n + i].push_back(make_pair(j ,0));
  }
  Spfa();
  return 0;
}