一、题意理解

1. 基本模型

• 清华有 $n$ 门课程，编号 $a_1,\dots,a_n$，质量 $x_1,\dots,x_n$。
• 北大有 $m$ 门课程，编号 $b_1,\dots,b_m$，质量 $y_1,\dots,y_m$。
• 课程编号范围在 $[1,n+m]$，同一所学校内编号互不相同，但两所学校可能有相同编号的课程（内容相同）。
• 神犇可以选择清华的一段连续课程 $[l_a,r_a]$，也可以不选（即 $l_a=r_a=0$）。
• 可以选择北大的一段连续课程 $[l_b,r_b]$，也可以不选。
• 选择时不能选两门编号相同的课程（即使它们在不同学校）。
• 目标是最大化所选课程的质量总和。

2. 难点

• 两段区间（清华段和北大段）必须各自连续。
• 两段区间内的课程编号不能重复。
• 可以只选一个学校，或两个都选，或不选（但质量非负，所以不会不选）。

---

二、问题转化

1. 无交集情况

如果清华和北大选择的课程编号没有交集，那么问题简化为：在两个数组上各选一个子段（可以为空），使和最大，且无相同编号。
实际上，如果无交集，那么直接分别选最大子段和即可，但“无交集”需要保证。

2. 有交集情况

如果两段有相同编号的课程，那么这些课程只能选一个（选质量大的那个学校）。
所以我们需要决策：对于每个编号，它出现在清华的某位置和北大的某位置，我们只能选其中一个。

---

三、算法思路概述

代码的核心思想是枚举清华段的左右边界，然后快速找到对应的北大段，使总质量最大。

更准确地说，算法做了以下转化：

1. 将课程编号映射为位置
   将北大的课程编号映射到清华的位置（如果清华也有该编号），否则标记为0。
   这样，我们可以用“清华的位置”来表示编号。

2. 用前缀和计算质量
   设 $X[i]$ 是清华前 $i$ 门课程的质量和，$Y[j]$ 是北大前 $j$ 门课程的质量和。

3. 枚举北大的右端点
   对于北大的每个右端点 $j$，我们想找到清华的一个区间 $[L,R]$ 和北大的左端点 $l$，使得：

   • 清华区间 $[L,R]$ 和北大区间 $[l,j]$ 无重复编号。
   • 总和 $X[R]-X[L-1] + Y[j]-Y[l-1]$ 最大。

4. 利用线段树维护最优值
   对于固定的北大右端点 $j$，我们把问题转化为：在清华的某个允许区间内找最大子段和，并加上北大 $[?,j]$ 段的和。
   线段树维护的是：对于清华的每个可能左端点 $L$，以 $L$ 为左端点的最优右端点 $R$ 能带来的最大收益。

---

四、代码细节解析

1. 数据读入与预处理

read(n), read(m);
for (int i = 1; i <= n; i++) read(a[i]);
for (int i = 1; i <= n; i++) read(x[i]), x[i] += x[i - 1];
for (int i = 1; i <= m; i++) read(b[i]);
for (int i = 1; i <= m; i++) read(y[i]), y[i] += y[i - 1];

• $a[i]$ 是清华课程编号。
• $x[i]$ 是质量前缀和。
• $b[i]$ 是北大课程编号。
• $y[i]$ 是质量前缀和。

for (int i = 1; i <= m; i++) c[b[i]] = i, b[i] = 0;
for (int i = 1; i <= n; i++) a[i] = c[a[i]], b[a[i]] = i;

• c[b[i]] = i 建立编号到北大位置的映射。
• a[i] = c[a[i]] 将清华的编号转为北大位置（如果不存在则为0）。
• b[a[i]] = i 建立北大位置到清华位置的映射（如果清华有相同编号）。

这样，a[i] 表示清华第 $i$ 门课程在北大中的位置（0表示北大没有），b[j] 表示北大第 $j$ 门课程在清华中的位置（0表示清华没有）。

---

2. 主要函数 solve

void solve(int n, int m, int *a, int *b, LL *x, LL *y, bool flg)

这个函数会处理两种情况（通过 flg 交换清华和北大的角色）。

---

2.1 初始化

int mid = lower_bound(x + 1, x + 1 + n, x[n] >> 1) - x;

mid 是清华前缀和中第一个大于等于总和一半的位置。
这个 mid 用于将清华课程分为“前半”和“后半”，有助于处理区间不交的条件。

---

2.2 建立关键点数组 p

pn = 0;
for (int i = 1; i <= m; i++)
    if (b[i]) p[++pn] = i, pos[pn] = b[i];
p[pn + 1] = m + 1;

p[1..pn] 存储的是北大中那些与清华有相同编号的课程的位置。
pos[k] 是北大第 p[k] 门课程在清华中的位置。

---

2.3 建立线段树

build(1, 0, pn, x[n], y);

线段树区间 [0, pn] 的叶子节点 k 对应：

• 清华左端点 L = pos[k]（注意 pos[0] 未定义，可能表示左端点为1）。
• 初始值 mx = x[n] - y[p[k]]，这里 x[n] 是清华总质量，y[p[k]] 是北大到 p[k] 的前缀和。
  这个初始化是为了方便后面更新。

---

2.4 枚举北大的右端点

for (int i = An = Bn = 0; i <= pn; i++) {

i 枚举的是 p 数组的索引，对应北大的某个关键点（相同编号的位置）。
An 和 Bn 是两个栈，分别维护清华前半段和后半段的最优左端点候选。

---

2.5 维护两个栈 A 和 B

if (i) {
    if (pos[i] <= mid) {
        // 清华位置在前半段
        mdf(1, 0, pn, A[An], i - 1, -x[pos[i]]);
        while (An && pos[i] > pos[A[An]])
            mdf(1, 0, pn, A[An - 1], A[An] - 1, -x[pos[i]] + x[pos[A[An]]]), --An;
        A[++An] = i;
    } else {
        // 清华位置在后半段
        mdf(1, 0, pn, B[Bn], i - 1, -x[n] + x[pos[i] - 1]);
        while (Bn && pos[i] < pos[B[Bn]])
            mdf(1, 0, pn, B[Bn - 1], B[Bn] - 1, -x[pos[B[Bn]] - 1] + x[pos[i] - 1]), --Bn;
        B[++Bn] = i;
    }
}

这里非常关键：

• 栈 A 维护清华位置在前半段（<=mid）的关键点，且保证 pos[A] 递减。
• 栈 B 维护清华位置在后半段（>mid）的关键点，且保证 pos[B] 递增。

为什么要这样？
因为我们要保证清华段和北大段无交集。清华段 $[L,R]$ 不能包含任何与北大段重复的编号。
A 栈的递减性保证了从某个左端点 L 开始，往右遇到的第一个相同编号的位置是递增的。
B 栈的递增性类似。

线段树上的区间加操作 mdf 是在更新：对于某些左端点范围，能选择的清华右端点受到限制，从而影响最大子段和的值。

---

2.6 更新答案

if (y[p[i + 1] - 1] + mx[1] > ans) {
    int k = find(1, 0, pn);
    int l = upper_bound(A + 1, A + 1 + An, k) - A;
    l = l <= An ? b[p[A[l]]] + 1 : 1;
    int r = upper_bound(B + 1, B + 1 + Bn, k) - B;
    r = r <= Bn ? b[p[B[r]]] - 1 : n;
    updans(y[p[i + 1] - 1] + mx[1], l, r, p[k] + 1, p[i + 1] - 1, flg);
}

• y[p[i + 1] - 1] 是北大到当前右端点的前缀和。
• mx[1] 是线段树根的最大值，表示最优的清华段收益。
• k 是达到最大值的清华左端点索引。
• 通过 A 和 B 栈找到清华段的实际左右边界 l 和 r。
• p[k] + 1 是北大左端点，p[i+1] - 1 是北大右端点。

---

3. 对称处理

solve(n, m, a, b, x, y, 0), solve(m, n, b, a, y, x, 1);

第一次：清华作为“前半”学校，北大作为“后半”学校。
第二次：交换角色，北大作为“前半”，清华作为“后半”。
这样可以覆盖所有可能的最优区间。

---

五、算法总结

1. 预处理：建立两校课程编号的对应关系。
2. 枚举北大右端点：通过关键点（相同编号的位置）将问题分段。
3. 线段树维护清华最优左端点：利用两个栈维护不交区间的限制。
4. 对称处理：交换两校角色，保证覆盖所有情况。
5. 输出最优解：记录最大和及对应的区间。

---

六、复杂度

• 每个 solve 中，枚举 i $O(pn)$，栈操作均摊 $O(1)$，线段树操作 $O(\log pn)$。
• 总复杂度 $O((n+m)\log(n+m))$，可以承受 $5\times 10^5$ 的数据规模。

---

七、样例验证

以样例1为例，算法会找到：

• 清华段 $[2,6]$：课程质量 $7+4+10+1+5=27$。
• 北大段 $[2,4]$：课程质量 $5+3+4=12$。
• 总 $39$，与输出一致。

---

这个解法巧妙利用栈维护区间不交条件，线段树快速查询最优左端点，是解决此类两段不交区间最大和问题的经典方法。