核心思路

1. 约束转化

对于每个员工 $i$，定义：

• $l_i$: 必须与 $i$ 同组的最小编号
• $r_i$: 必须与 $i$ 同组的最大编号
• $L_i$: 不能与 $i$ 同组的最小编号
• $R_i$: 不能与 $i$ 同组的最大编号

代码中用：

• l[i].fir = 必须同组的最小右边界
• l[i].sec = 不能同组的最小右边界
• r[i].fir = 必须同组的最大左边界
• r[i].sec = 不能同组的最大左边界

2. 约束处理规则

对于约束 $(t,x,y)$：

• $t=1$ (必须同组)：

  • 若 $x < y$：必须包含 $[x,y]$ 区间 → 更新 r[x].fir = max(r[x].fir, y)
  • 若 $x > y$：必须包含 $[y,x]$ 区间 → 更新 l[x].fir = min(l[x].fir, y)

• $t=2$ (不能同组)：

  • 若 $x < y$：不能包含 $[x+1,y]$ 区间 → 更新 r[x].sec = min(r[x].sec, y)
  • 若 $x > y$：不能包含 $[y,x-1]$ 区间 → 更新 l[x].sec = max(l[x].sec, y)

3. 动态规划状态

设 $f[i]$ 表示考虑前 $i$ 个员工的最大总效率。

转移： [ f[i] = \max_{0 \leq j < i} { f[j] + \text{sum}(j+1,i) } ] 其中 $\text{sum}(j+1,i)$ 是区间 $[j+1,i]$ 中所有约束被满足的员工的效率之和。

4. 线段树优化

关键观察：对于区间 $[j+1,i]$，员工 $x$ 被满足当且仅当：

• $l[x].fir \leq j+1$ 且 $r[x].fir \geq i$（必须同组约束满足）
• 且 $l[x].sec \geq j+1$ 或 $r[x].sec \leq i$（不能同组约束满足）

代码用扫描线 + 线段树维护：

• 当右端点 $i$ 扫描时，将满足条件的区间加入
• 线段树维护每个左端点 $j$ 对应的 $\text{sum}(j+1,i)$
• 用 mxv[1] 获取当前最大 $f[i]$

5. 算法流程

1. 初始化约束边界
2. 扫描线处理：
   • ins[i]: 当右端点 = i 时开始生效的约束
   • del[i]: 当右端点 = i 时失效的约束
3. 线段树更新：
   • 对每个生效约束，在左边界处加减效率值
   • 查询全局最大值得到 $f[i]$
4. 状态转移：
   • $f[i]$ 用于更新后续状态
   • 通过 modify(i, -f) 和 modify(i+1, f) 实现

重要公式

1. DP 转移： [ f[i] = \max_{0 \leq j < i} { f[j] + S(j+1,i) } ] 其中 $S(l,r)$ 是区间 $[l,r]$ 中有效员工的效率和。

2. 约束条件：

   • 必须同组：$l_{\text{min}} \leq \text{left} \leq x \leq \text{right} \leq r_{\text{max}}$
   • 不能同组：$\text{left} > L_{\text{max}}$ 或 $\text{right} < R_{\text{min}}$

3. 线段树维护：

   • sum[p]: 区间和
   • mxv[p]: 区间最大后缀和
   • 合并：mxv[p] = max(mxv[lp] + sum[rp], mxv[rp])

复杂度分析

• 约束处理：$O(m)$
• 扫描线：$O(n)$
• 线段树操作：$O(n \log n)$
• 总复杂度：$O(n \log n)$