知识点：差分约束
Link：https://codeforces.com/gym/103931/problem/B。
被卡 SPFA 了呃呃。
一看出题人是这个人：
如何看待 SPFA 算法已死这种说法？ - fstqwq 的回答 - 知乎，那没事了。
简述
给定参数 \(n, q\)，表示有一个长度为 \(n\) 的合法括号序列，且有 \(q\) 组限制。每组限制均为 \(l_i, r_i, c_i\) 的形式，表示括号序列区间 \([l_i, r_i]\) 中，左括号数减去右括号数得到的差值为 \(c_i\)。要求判断是否存在一个满足所有限制的合法括号序列，若存在则构造任意一组合法的解。
\(2\le n\le 3000\)，\(0\le q\le \min\left( \binom{n+1}{2}, 5\times 10^5\right)\)，\(1\le l_i\le r_i\le n\)，\(-n\le c_i\le n\)。
2S，1024MB。
分析
给定限制为数量关系，考虑把括号序列合法的条件也抽象成数量关系。记一个左括号的权值为 1，右括号权值为 -1，记 \(s_i\) 表示序列的前缀 \([1, i]\) 的权值之和，则一个长度为 \(n\) 的括号序列合法，则等价于：
- \(s_0 = s_n = 0\)。
- \(\forall 1\le i\le n,\ s_i\ge 0\)。
- \(\forall 1\le i\le n,\ |s_i - s_{i - 1}| = 1\)。
则本题中给定的限制 \((l_i, r_i, c_i)\) 可以表示为 \(s_r - s_{l - 1} = c_i\) 的形式。对于一组满足限制的 \(s\) 的取值，通过差分我们可以唯一确定这组值对应的括号序列。问题变为是否存在一组 \(s\) 的取值满足上述所有限制。
考虑差分约束，记 \(\operatorname{dis}_i\) 表示到达节点 \(i\) 的最短路长度，将上述所有限制转化为三角不等式形式：
- \(s_0 = s_n = 0\)，考虑以节点 0 为起点，且向节点 \(n\) 连一条权值为 0 的边。
- \(\forall 1\le i\le n,\ s_i\ge 0\)，即 \(s_i\ge s_0\)，从 \(i\) 向 0 连一条权值为 0 的边。
- 对于给定限制 \(s_r - s_{l - 1} = c_i\)，即 \(c_i \le s_r - s_{l - 1} \le c_i\)，从 \(l-1\) 向 \(r\) 连一条权值为 \(c_i\) 的边，从 \(r\) 向 \(l-1\) 连一条权值为 \(-c_i\) 的边。
- \(\forall 1\le i\le n,\ |s_i - s_{i - 1}| = 1\)，可以发现如果 \(q\) 个限制均满足偶数长度的限制区间的 \(c_i\) 为偶数，奇数长度的限制区间的 \(c_i\) 为奇数，则 \(s_{i} \not= s_{i-1}\) 一定成立。则可考虑先判断给定限制是否符合上述条件，再将该条件放松为 \(-1\le s_i - s_{i - 1}\le 1\)，从 \(i-1\) 向 \(i\) 连一条权值为 1 的边，从 \(i\) 向 \(i-1\) 连一条权值为 1 的边。
建图后运行差分约束算法，若存在负环则无解，否则根据 \(\operatorname{dis}\) 即可构造一组合法解。
此时如果直接使用 Bellman-Ford/SPFA 算法朴素地实现，则复杂度上界为 \(O(nq)\) 级别，在出题人的特别关照下，使用朴素的 SPFA 算法无法通过本题。
使用 SLF SPFA 可通过本题，且实际运行效率较高。std 则在此基础上采用了一种复杂度稳定的 \(O(n^2)\) 算法，详见下文：
代码
大力 SLF SPFA 爆炒：
//知识点：负环
/*
By:Luckyblock
*/
// #pragma GCC optimize(2)
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 3e3 + 10;
const int kM = 5e6 + 10;
//=============================================================
int n, q;
int e_num, head[kN], v[kM], w[kM], ne[kM];
int dis[kN], cnt[kN];
bool vis[kN];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Chkmax(int &fir_, int sec_) {
if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
if (sec_ < fir_) fir_ = sec_;
}
void AddEdge(int u_, int v_, int w_) {
v[++ e_num] = v_;
w[e_num] = w_;
ne[e_num] = head[u_];
head[u_] = e_num;
}
void Init() {
e_num = 0;
memset(head, 0, sizeof (head));
}
bool SpfaBfs(int s_) {
std::deque <int> q;
memset(cnt, 0, sizeof (cnt));
memset(vis, 0, sizeof (vis));
memset(dis, 63, sizeof (dis));
q.push_front(s_);
dis[s_] = 0;
vis[s_] = true;
while (! q.empty()) {
int u_ = q.front();
q.pop_front();
vis[u_] = false;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i], w_ = w[i];
if (dis[u_] + w_ < dis[v_]) {
dis[v_] = dis[u_] + w_;
cnt[v_] = cnt[u_] + 1;
if (cnt[v_] > n) return true;
if (! vis[v_]) {
if (!q.empty() && dis[v_] > dis[q.front()]) q.push_back(v_);
else q.push_front(v_);
vis[v_] = true;
}
}
}
}
return false;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
n = read(), q = read();
for (int i = 1; i <= q; ++ i) {
int l_ = read(), r_ = read(), c_ = read();
if ((r_ - l_ + 1) % 2 != (abs(c_) % 2)) {
printf("?\n");
return 0;
}
AddEdge(l_ - 1, r_, c_);
AddEdge(r_, l_ - 1, -c_);
}
for (int i = 1; i <= n; ++ i) {
AddEdge(i, 0, 0);
AddEdge(i - 1, i, 1); //(i - 1) <= i + 1
AddEdge(i, i - 1, 1); //i <= (i - 1) + 1
}
AddEdge(0, n, 0);
if (SpfaBfs(0)) {
printf("?\n");
return 0;
}
printf("! ");
for (int i = 1; i <= n; ++ i) {
// printf("%d ", dis[i]);
if (dis[i] - dis[i - 1] == 1) {
printf("(");
} else {
printf(")");
}
}
return 0;
}