题解：P17120 [Algo Beat 009 & MROI-R1] Parallel Parentheses
调试一亿发的最终原因是交的 C++14 这谁能蚌住。
这个题目显然就是想让我们状态压缩来进行通信，我们先节点内部自由匹配，考虑会剩下什么。
注意到，如果可以跨过这整个区间，那么我们内部自由匹配完剩下的是形如 )))((( 的东西。如果不能跨过，那么可以是左边右边各自有一个 )) 或者 (( 状态啊。
但是这个东西是带上了匹配系数的，就是我们如果匹配多一个 ) 可能会让我们拿到更多的 ()。
问题模型似乎比较清晰了，观察一下规模发现每个人可以大致传输 int 的信息，显然无法传递刚刚说到的系数，但是我们其实可以通过来回通信解决这一问题：
类似我告诉下一个人，然后下一个人告诉我需求我再还回去。形式化一下这个做法得到一个初步做法：
我们先接收左侧的信息，这个信息是形如：我有多少个未匹配的 )。
如果我是一个可以跨过的块并且我的 ) 数量不会太多，那么我们可以传递，我们叠加自己后向下一个块传递活动。
如果我们无法恰好或者我是一个无法跨过的块，那么在这里会截断。
右侧视为一个重新的开始，然后我们向左往回传递我们实际上能吃掉多少个未匹配的 )，和当前的带上匹配权重的答案。
我们从右边拿到之后就扣除手上的相对差然后向左传递，最后如果这里出现截断我们就向
这个其实我们每个人要发送
最直接的想法就是我们把直接回传 int 压缩一下，但是注意到 long long 的，差了不少。
具体化分析我们的操作次数，我们要缩减 int 的发送，如果我们可以把三元组压缩，那么我们就有
发动注意力：注意到 long long 的差很松，考虑压成
考虑从三元组的第三维
延续一下这个思路：注意到如果
注意到 ) 数量的约束的，具体的：
那么如果
还有一种情况是
现在还有一个我们忽略了的小问题：我们无法忽略信道让
但是这又产生了一个问题：
这个问题很好解决：我们注意到
我的压位是 AI 写的，因为没人想写这个。
/*
先想想然后看一下部分分提示再想想：
压缩状态似乎是一个关键啊，问题是最大匹配括号子串
先考虑跨过？是否可能的部分吧：
如果可以跨过那其实就一定内部匹配完可以构成一个 )( 状物吧
这个状态的本质是 n^2 的。
00.04.03
如果不能跨过？那么可以是左边右边各自有一个 )( 状态啊。
但是这个东西是带权的啊带上了匹配系数的，比如我多匹配一个可能有多若干
00.06.21
好了问题模型似乎比较清晰了，观察一下规模？
106 个 int，424 bit
1.6e7 划分 16个，单个最大 1.6e6。
每个人可以传差不多 7 个 int 吧。
00.12.44
哦我草有点唐，如果不能跨过的话状态就不是 )( 了，就只能是 ) 或者 (了
带起权还是很大啊，但是其实似乎有我告诉下一个人，然后下一个人告诉我需求我再还回去的说法
对的，这一步很大优化，现在开始考虑一个第一步做法：
基础包
00.16.40
第一版做法草稿：
我告诉下一个人我有多少个左，然后下一个人考虑他是否可以吃完我的所有左，
似乎可以先报需求？但是先不管，算一下流程：
然后如果刚好可以吃下去或者吃不完但是没有右就考虑向右找下一个人。
然后到吃不下了就再传回来每一步要吃多少，过去一个 int 回来一个 int，过去一个 int？
这对吗？然后再告诉 0 答案才 4 个 int？
完整包
00.27.13
一个块本质有两种状态：
一个是内部可以匹配，第二种是内部出现混乱和错误
第一种是剩下了一个 ）（ 状态，第二种意味着无法跨过，剩下了） 和 （ 的残缺。
考虑对于一个人：
我们先接收左侧的信息，这个信息是形如：我有多少个活动 （
如果我是一个1形态的块并且我的）刚好，那么我们可以传递，我们叠加自己后向下一个块传递活动
如果我们无法恰好或者我是一个2形态的块，那么在这里会截断。
右侧视为一个重新的开始，并且我们向左往回传递我们实际上能吃掉多少个东西，和当前的带上权重的答案。
我们从右边拿到之后就扣除手上的相对差然后向左传递，最后如果这里出现截断我们就向 1 传递答案。
dlc1
4 int 的发送量有一点点微超。感觉就是一个卡常啊，我有如下想法：
你注意到向 1 传答案拉完了，我们往回同时发答案和权值的时候试着发送一下若干个答案的 max
如果可以在剩下的大概 8e17 / 1.6e7 / 1.6e7 的机会发完，我们就发，不然我们就直接发给 1 然后清零。
注意到这个东西比较制约，因为如果我们短的可以带着发，长的的话本身中间就会少发，大力过掉
不知道为什么cph的计时器刷新了，查询一下和gemini的聊天得知过了 14min
00.41.51 END?
还没有结束，证明这个复杂度？其实更大的问题是1不知道他要收多少个
倒闭了，我们完全不会证明，我们需要压缩三元组到一个longlong里面
[0, 0.8e7], [0, 1.6e7], [0, 1.6e7]
同时三元组单调递增，也就是 a <= b <= c，分析到了 5e20
dlc2
仔细分析一下冗余量，剩下了64怎么处理更大的部分？相当于我们有一半的时候可以多发一个int
诶？是不是其实有一半的情况是 a = c 的如果我们带上那个丢弃，详细证明：
好像是对的！我们有一半的情况是发送并且不管的话我们另外一半就刚好有 a = c，那么我们就可以直接收掉8个int
好像不对？真的是有一半的情况吗，不对不对感觉会被卡
dlc3
尝试搞一个 M ^ 3 的状态，我们强制要求 c < M 否则有
a = c 或者 a b c 小于 m
想清楚了啊！！！
在每一个奇数我们都直接发送当前右侧的答案给 1
那么此时分两种case：
a b c 全部小于 m
否则如果a b > m 那么有 a b > c，那么我们的 c 没有维护的意义
刚刚好 21 位可以算出来一个 M，那我们直接状压，最后一位用来判断是第一种情况还是第二种情况。
c 其实阈值要到 2m，那感觉要精细实现啊
怎么办 a, b, c，满足有如下两种可能：a > b, c = 0, a, b \in [0, 1.6e7]，c >a > b, a, b, c \in [0, 3.13332e6]状压成一个 long long或者 ull
dlc4
不能直接奇数位置传送，得再带上一个计数器，好在只有8，依旧压进去！
dlc5
我们直接塞进去一个判断，然后抽到最后的包就可以了
dlc6
原来不需要知道信道怎么还是需要知道信道
dlc7
我们可以直接在 1 返回的那个块上面拉出来一条链，信息并不多！
压不进去！a和b奇偶性一致，压进去了！
*/
#include <bits/stdc++.h>
#include <cstring>
using namespace std;
#define rep(i, a, b) for (int i = (a) ; i <= (b) ; i ++)
#define per(i, a, b) for (int i = (a) ; i >= (b) ; i --)
using ll = long long;
using ull = unsigned long long;
int GetN();
int GetMyId();
long long GetM();
char GetCharAt(long long i);
void PutInt(int target, int val);
void PutLL(int target, long long val);
void Send(int target);
void Receive(int source);
int GetInt(int source);
long long GetLL(int source);
// ==================== 100% 标准安全的位重解释 ====================
inline ll bit_cast_to_ll(ull val) {
ll res;
std::memcpy(&res, &val, sizeof(ll));
return res;
}
inline ull bit_cast_to_ull(ll val) {
ull res;
std::memcpy(&res, &val, sizeof(ull));
return res;
}
// ==================== 奇偶相同且大于等于约束下的数学 ====================
// a >= b 且同奇偶情况下，有序对 (b <= a) 在 [0, a-1] 中的总数量
inline ull g(ull a) {
ull k = a / 2;
if (a % 2 == 0) {
return k * (k + 1);
} else {
return (k + 1) * (k + 1);
}
}
// 计算 c 以下，所有同奇偶且 c >= a >= b 的合法三元组总数
ull sum_pairs(ull n) {
ull m = n / 2;
ull a = m + 1, b = m + 2, c;
if (n % 2 == 0) {
c = 4 * m + 3;
} else {
c = 4 * m + 9;
}
// 安全整除，防止乘法中间步骤溢出
if (a % 2 == 0) a /= 2; else b /= 2;
if (a % 3 == 0) a /= 3; else if (b % 3 == 0) b /= 3; else c /= 3;
return a * b * c;
}
// 包含 c==0 边界的安全前缀和获取
inline ull get_sum_pairs(ull c) {
if (c == 0) return 0;
return sum_pairs(c - 1);
}
// 奇偶约束 & 大于等于约束下，情况 1 的最大可能状态分界线
// 最大 pair_rank << 4 | 15 = 1024000256000015ULL。因此阈值设为 1024000256000016ULL
const ull Threshold_2 = 1024000256000016ULL;
// ==================== 核心接口实现 ====================
// 压缩：将 (a, b, c, d) 压成 signed long long (ll)
// 约束：a >= b 且 a, b 奇偶性必须相同；d 属于 [0, 15]；c 可为任意值 (满足 c >= a)
ll encode(int a, int b, int c, int d) {
ull code = 0;
if (c == 0) {
// 情况 1: c = 0, a >= b, a 和 b 奇偶性相同, d 属于 [0, 15]
ull pair_rank = g(a) + b / 2;
code = (pair_rank << 4) | (ull)d;
} else {
// 情况 2: c >= a >= b, a 和 b 奇偶性相同, d 属于 [0, 15]
ull triple_rank = get_sum_pairs(c) + g(a) + b / 2;
code = Threshold_2 + ((triple_rank << 4) | (ull)d);
}
return bit_cast_to_ll(code);
}
// 解压：将 signed long long (ll) 还原为 (a, b, c, d)
std::tuple<int, int, int, int> decode(ll S) {
ull code = bit_cast_to_ull(S);
if (code < Threshold_2) {
// 解压情况 1
int d = code & 15ULL;
ull rem = code >> 4;
// 二分查找 a (范围扩至 [0, 20000000])
ull low = 0, high = 20000000, a = 0;
while (low <= high) {
ull mid = low + (high - low) / 2;
if (g(mid) <= rem) {
a = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
rem -= g(a);
int b = rem * 2 + (a % 2); // 还原 b，恢复奇偶性
return { (int)a, b, 0, d };
}
else {
// 解压情况 2
ull val = code - Threshold_2;
int d = val & 15ULL;
ull rem = val >> 4;
// 1. 二分查找 c (安全防溢出最大上界设为 5000000)
ull low_c = 0, high_c = 5000000, c = 0;
while (low_c <= high_c) {
ull mid = low_c + (high_c - low_c) / 2;
if (get_sum_pairs(mid) <= rem) {
c = mid;
low_c = mid + 1;
} else {
high_c = mid - 1;
}
}
rem -= get_sum_pairs(c);
// 2. 二分查找 a (范围 [0, c])
ull low_a = 0, high_a = c, a = 0;
while (low_a <= high_a) {
ull mid = low_a + (high_a - low_a) / 2;
if (g(mid) <= rem) {
a = mid;
low_a = mid + 1;
} else {
high_a = mid - 1;
}
}
rem -= g(a);
int b = rem * 2 + (a % 2); // 还原 b，恢复奇偶性
return { (int)a, b, (int)c, d };
}
}
// 压缩打包：将 x ∈ [0, 1.6e7] 和 y ∈ [0, 15] 压入一个 int
int encodep(int x, int y) {
return (x << 4) | (y & 15);
}
// 解压还原：将 int 还原为 {x, y}
std::pair<int, int> decodep(int v) {
int y = v & 15; // 取出低 4 位
int x = v >> 4; // 右移还原 x
return { x, y };
}
long long LongestValidParentheses () {
int n = GetN(), id = GetMyId(), m = GetM(), L = m / n;
int now = 0;
if (id != 0) {
Receive (id - 1);
now = GetInt (id - 1);
}
bool flg = 0;
int ra = 0, rc = 0, tmp = now, hans = 0, tot = 0;
int mys = 0, lp = 0;
rep (i, id * L, id * L + L - 1) {
char ch = GetCharAt (i);
if (ch == ')') {
if (mys) mys --;
else now --;
}
else mys ++;
tot ++;
if (now >= 0 && (! flg) && (! mys)) {
ra = max (i - id * L + 1, ra);
rc = tmp - now;
}
if (now < 0) {
if (! flg) ra = i - id * L + 1;
hans = max (hans, tot - 1);
flg = 1, now = 0, tot = 0;
}
}
int rans, rcnt;
if (id != n - 1) {
PutInt (id + 1, now + mys);
Send (id + 1);
Receive (id + 1);
ll S = GetLL (id + 1);
auto [t1, t2, t3, t4] = decode(S);
if (id == 0) {
int np = t4;
while (np) {
Receive (np);
int ss = GetInt(np);
auto [hs, nxt] = decodep (ss);
hans = max (hs, hans);
np = nxt;
}
}
rans = t1, rcnt = t2, hans = max (t3, hans); lp = t4;
}
else rans = 0, rcnt = 0;
int nans, ncnt;
per (i, id * L + L - 1, id * L) {
char ch = GetCharAt (i);
if (ch == '(') rcnt --;
else rcnt ++;
if (rcnt < 0) {
hans = max(hans, rans + id * L + L - i - 1);
break;
}
}
if (rcnt < 0) nans = ra, ncnt = rc;
else if (rcnt <= tmp) nans = rans + L, ncnt = rcnt;
else nans = ra, ncnt = rc;
if (hans < nans) hans = 0;
if (hans > 2 * L && (id != 0)) {
PutInt (0, encodep(hans, lp)); Send(0); lp = id; hans = 0;
}
if (id != 0) {
ll S = encode (nans, ncnt, hans, lp);
PutLL (id - 1, S);
Send (id - 1);
}
if (id == 0) {
hans = max (hans, nans);
return hans;
}
return 0;
}