1）题目意思
有一条很长的格子带（编号从 1 开始到 1e9），要放 n 条蛇。开始时每条蛇长度为 1，占一个格子，且不同蛇不能占同一格。
之后有 q 次操作，每次对某条蛇执行：
* +：区间 [l,r] 变成 [l,r+1]（向右变长）
* -：区间 [l,r] 变成 [l+1,r]（从左缩短）
任何时刻蛇不能撞到边界（格子编号不能 < 1），也不能和其它蛇重叠（同一格不能被两条蛇同时占用）。
游戏结束后，得分是所有蛇占用到的最大格子编号（也就是所有蛇的 r 的最大值）。你要让得分尽可能小，输出最小可能得分。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2）思路解析（核心等价 + 二分答案 + 状压DP选顺序）
关键等价：每条蛇在任意时刻的位置只和“+/- 的次数”有关
设第 s 条蛇初始放在位置 p[s]（初始 l=r=p）。
令：
* plus[s][t]：前 t 秒内对蛇 s 执行过 + 的次数
* minus[s][t]：前 t 秒内对蛇 s 执行过 - 的次数
那么在第 t 秒后（含 t=0 初始）：
* 左端点 l = p[s] + minus[s][t]
* 右端点 r = p[s] + plus[s][t]
（因为 + 只让右端点 +1，- 只让左端点 +1，且输入保证不会缩到空。）
所以整题变成：选一组互不相同的起点 p[s]，使得对所有时刻 t，任意两条蛇区间不重叠，并最小化最终最大的 r。
不重叠条件（假设放置顺序从左到右）
如果某时刻我们保证蛇 A 的起点在蛇 B 左边（p[A] < p[B]），要想永远不重叠，需要对所有时刻 t 都满足：
* p[A] + plus[A][t] < p[B] + minus[B][t]
整理得：
* p[B] - p[A] > plus[A][t] - minus[B][t]
因此只要让相邻两条蛇的起点间距满足一个“最大需求间距”即可：
* gap(A,B) = 1 + max_t( plus[A][t] - minus[B][t] )
然后只要 p[B] >= p[A] + gap(A,B)，就能保证任意时刻 A 永远在 B 左边且不重叠。
二分答案 M（最终最大格子编号）
如果我们猜一个最终得分上限 M，就等价于对每条蛇都有：
* p[s] + plus[s][q] <= M
也就是：
* p[s] <= M - plusFinal[s]
在给定 M 时，问题变成：
* 给 n 条蛇排一个从左到右的顺序
* 从最左开始放，最左蛇放在 p=1
* 后面每条蛇满足相邻间距 gap
* 并且每条蛇的起点不超过它的上界 ub[s]=M-plusFinal[s]
问能否做到。能做到则 M 可行，否则不可行。可行性随 M 单调，所以可以二分。
如何判断某个 M 是否可行：状态压缩 DP 选顺序
n<=20，可以用状压 DP 来选排列顺序：
* dp[mask][last] 表示：已放置集合 mask 这些蛇，并且最后一条是 last，在“尽量靠左放”的策略下，last 的最小可能起点位置。
* 初始：选某条蛇作为第一条，放在 p=1，要求 1<=ub[first]
* 转移：从 last 接一条 nxt，则
* pNext = dp[mask][last] + gap(last,nxt)
* 要求 pNext <= ub[nxt]
* 更新 dp[mask|1<<nxt][nxt] = min(原值, pNext)
如果能做到 mask=ALL（所有蛇都放完）则这个 M 可行。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3）代码
上述代码TLE三个
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正确解法
这题的关键是：蛇的形状始终是一个区间，并且每次操作只会改变区间的左端或右端 1 格。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1）把每条蛇任意时刻的位置写成“起点 + 偏移”
设第 s 条蛇初始放在格子 p[s]（一开始区间是 [p,p]）。
统计到第 t 秒为止：
* plusCnt[s][t]：对蛇 s 执行 + 的次数
* minusCnt[s][t]：对蛇 s 执行 - 的次数
那么第 t 秒后蛇 s 的区间一定是：
* 左端点 L = p[s] + minusCnt[s][t]
* 右端点 R = p[s] + plusCnt[s][t]
所以整个过程只和 p[s]、以及这两个前缀次数有关。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2）两条蛇不相撞的充分必要条件：固定左右顺序 + 保证所有时刻区间不重叠
假设我们决定蛇 a 在蛇 b 的左边（也就是 p[a] < p[b]），为了任何时刻都不重叠，需要对所有 t：
* p[a] + plusCnt[a][t] < p[b] + minusCnt[b][t]
把 p[b] 移到右边整理，得到：
* p[b] - p[a] > plusCnt[a][t] - minusCnt[b][t]
因此只要让相邻两条蛇的起点间距满足：
* gapNeed[a][b] = 1 + max_t( plusCnt[a][t] - minusCnt[b][t] )
就能保证：只要 a 在左 b 在右，就永远不会相撞。
代码里就是先枚举 a,b，再扫一遍 t=0..q 求这个最大值，得到 gapNeed[a][b]。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3）最终得分怎么计算
游戏结束时（t=q），蛇 s 的右端点是：
* R_final = p[s] + plusFinal[s]
其中 plusFinal[s] = plusCnt[s][q]
最终得分是所有蛇 R_final 的最大值，也就是：
* max_s( p[s] + plusFinal[s] )
你要让它最小。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4）为什么可以“从左到右贪心放位置”，只需要决定顺序
如果我们已经决定了蛇的从左到右顺序，例如 s1, s2, ..., sn，那么为了得分尽量小，显然应该：
* 第一条蛇放到最左 p[s1]=1
* 后面每条蛇都放到“刚好不撞”的最左位置
p[si] = p[s(i-1)] + gapNeed[s(i-1)][si]
因为把任何一条蛇往右挪，只会让最终最大右端点变大或不变，不可能更优。
所以问题变成：只需要选出一条从左到右的排列顺序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5）状压 DP：一次性求“最小得分”（不二分）
n<=20，我们用 mask 表示已经放进队列的蛇集合。
DP 状态存两件信息：
* pos：当前最后一条蛇的起点（按最靠左放算出来的）
* mx：当前为止所有蛇的最终右端点最大值（也就是当前方案的得分）
定义：
* dp[mask][last]：放置了 mask 中的蛇，并且最右边那条是 last 时的最优 (mx,pos)
比较规则：先 mx 小更优；mx 相同则 pos 小更优（更靠左对后续更有利）。
初始化（只有 1 条蛇）：
* pos = 1
* mx = 1 + plusFinal[s]
转移：
* 从 (mask,last) 接一条新蛇 nxt 到右边
* nextPos = pos + gapNeed[last][nxt]
* nextMx = max(mx, nextPos + plusFinal[nxt])
* 更新 dp[mask|1<<nxt][nxt]
答案：
* 在 mask=ALL（所有蛇都放完）时，取所有 last 中最小的 mx
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6）这版为什么不会 MLE / 为什么比二分快
* 不再二分 M，只做一次 DP（少了约 30 倍）
* 用“按 popcount 分层滚动”，只存当前层和下一层，内存显著下降
* mx、pos 都用 int 存（答案不会超过 1e9），进一步省内存
以上就是这版代码的完整思路链条：
把碰撞约束变成相邻起点间距 gapNeed，再用状压 DP 选最优排列顺序，同时在 DP 中直接最小化最终得分 mx。
代码
