P12348 [蓝桥杯 2025 省 A 第二场] 交互
题目描述
小蓝正在做一道交互题。有一个未知的下标从 1 到 m 的数组 a，小蓝每次可以进行一次询问 (l,r,p,q)，然后交互程序会返回 ans 满足 l≤x≤rmina[x]−p≤y≤qmaxa[y]≥ans。但小蓝很快就发现，因为 ans 并不是精确的值，所以他永远也无法得到实际的数组元素的值。
给定小蓝的几次询问和交互程序的返回值，请你帮他求出 1≤x≤mmaxa[x]−1≤y≤mmina[y] 的可能的最小值。
输入格式
输入的第一行包含两个正整数 n,m，用一个空格分隔，分别表示小蓝的询问次数和数组长度。
接下来 n 行，每行包含五个正整数 li,ri,pi,qi,ansi，相邻整数之间使用一个空格分隔，表示第 i 次小蓝询问及其结果，含义如问题描述所述。
输出格式
输出一行包含一个整数表示答案，即 1≤x≤mmaxa[x]−1≤y≤mmina[y] 的可能的最小值，如果无解请输出 No Solution。
输入输出样例
输入 #1
2 4 1 1 2 2 2 1 2 3 4 2
输出 #1
4
输入 #2
2 2 1 1 2 2 1 2 2 1 1 1
输出 #2
No Solution
说明/提示
样例说明
- 对于样例 1，a1−a2≥2，min(a1,a2)−max(a3,a4)≥2。所以 a1−a3≥4，所以 ai 之间差值的最大值不会小于 4。
- 对于样例 2，a1−a2≥1，a2−a1≥1，这种情况显然是无解的。
题解：
题目类型：差分约束，
首先肯定是要根据题目的限制关系建图
根据题目要求：区间 [L, R] 的最小值减去区间 [P, Q] 的最大值应不小于 X
显然 [L , R] 中的每一位减去[P, Q]的每一位 都恒大于 X
按照上面方法建图，时间复杂度来到了 O((Q−P)*(R−L)*n)，毫无疑问会超时
仔细想想，其实可以创建类似中转站这样虚拟的点
假设 A = min( a[x] | x ∈ [L, R] )，B= max( a[y] | y ∈ [P, Q] )，
求的是最长路，把不等号翻转一下，再移项就变成 B <= A - X
我们设有大小等于D的中转点，存在 B <= D <= A - X，
就有下面式子：
D <= A - X (1)
B <= D + 0 (2)
通过这两个式子就可以构建图的关系，时间复杂度就大大降低了，
再接着就是判断负环，用 stack栈 代替 queue队列会快一些，
原理就是利用stcak后进先出的特性，加速判断负环存在与否
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<tuple>
#define inf 1152921504606846977
#define int long long
#define endl '\n'
#define F first
#define S second
using namespace std;
typedef pair<int, int> pii;
const int N = 50500, M = N * 2;int t, n, m, tot;
int h[N], e[M], ne[M], w[M], idx;
int dis[N], cnt[N];
bool st[N];void add(int a, int b, int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}bool spfa() {stack<int> q;for (int i = 1; i <= n + m; i++) {q.push(i);st[i] = true;}while (q.size()) {int u = q.top();q.pop();st[u] = false;for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (dis[j] > dis[u] + w[i]) {dis[j] = dis[u] + w[i];cnt[j] = cnt[u] + 1;if (cnt[j] >= n + m) return true;if (!st[j]) {q.push(j);st[j] = true;}}}}return false;
}signed main() {cin >> m >> n;memset(h, -1, sizeof h);for (int i = 1; i <= m; i++) {int l, r, p, q, x;cin >> l >> r >> p >> q >> x;for (int j = l; j <= r; j++) add(j, n + i, -x);for (int j = p; j <= q; j++) add(n + i, j, 0);}if (spfa()) cout << "No Solution" << endl;else {int maxn = dis[1], mins = dis[1];for (int i = 2; i <= n; i++) {maxn = max(maxn, dis[i]);mins = min(mins, dis[i]);}cout << maxn - mins << endl;}return 0;
}