题意理解

我们有一个长度为 ( N ) 的整数数组 ( c[1..N] )，以及 ( Q ) 个查询，每个查询给出区间 ([L_i, R_i])。

对于每个查询，我们要找出在区间 ([L_i, R_i]) 内，最多能选出多少个不相交的、和为 0 的子数组。

• 不相交：子数组之间没有公共元素（但可以相邻）。
• 一些元素可以不属于任何选出的子数组。

---

样例分析

样例：

数组: 1 2 -3 0 1 -4 3 2 -1 1
查询1: [1,10] → 答案4
查询2: [1,5]  → 答案2
查询3: [2,9]  → 答案2

---

问题转化

设前缀和： [ s[i] = \sum_{k=1}^i c[k], \quad s[0] = 0 ] 那么子数组 ([l, r]) 的和为 0 等价于： [ s[r] = s[l-1] ]

问题变成：在区间 ([L, R]) 内，找出尽可能多的不相交的配对 ((l-1, r)) 满足 (s[l-1] = s[r])，并且这些区间不重叠。

---

贪心策略

经典贪心：从左到右扫描，一旦发现一个位置 (r) 使得存在某个 (l-1 \ge L-1) 且 (s[r] = s[l-1]) 并且区间 ([l, r]) 与已选区段不重叠，就选取它。

这等价于：在区间 ([L-1, R]) 的前缀和序列中，找尽可能多的不相交的相等数对。

---

数据结构解法思路

代码的核心思路是：

1. 预处理前缀和，离散化。
2. 找出所有和为 0 的子数组（即 (s[r] = s[l-1]) 的 ((l, r))），并按照某种顺序存储。
3. 贪心选择：对于每个右端点，选择最晚可用的左端点（不重叠）。
4. 回答查询：用某种数据结构快速得到区间 ([L, R]) 内能选出的最多子数组数。

---

代码结构分析

1. 前缀和与离散化

ll sum = 0;
S[n + 1] = 0;
for (int i = 1; i <= n; i++) {
    cin >> c[i];
    sum += c[i];
    S[i] = sum;
}
sort(S + 1, S + 2 + n);
int len = unique(S + 1, S + 1 + len) - (S + 1);

这里 S 数组用来存前缀和，并离散化。

---

2. 建立“下一个相同前缀和”的关系

sum = 0;
for (int i = 1; i <= n; i++) {
    sum += c[i];
    int id = lower_bound(S + 1, S + 1 + len, sum) - S;
    if (sz[id]) {
        dfn[i] = sz[id];  // 记录与当前前缀和相等的上一个位置+1
        sz[id] = i + 1;
    } else {
        dfn[i] = n + 1;
        sz[id] = i + 1;
    }
}

这里 dfn[i] 表示：对于右端点 (i)，上一个相同前缀和的位置是 dfn[i] - 1，所以区间是 [dfn[i], i] 和为 0。

---

3. 贪心选择区间

int lst = 0;
for (int i = 1; i <= n; i++) {
    if (dfn[i] == n + 1 || dfn[i] <= lst) {
        dfn[i] = 0; // 不可用
        continue;
    }
    lst = dfn[i]; // 选择这个区间，更新 lst
}

这里 lst 表示上一个选择的区间的左端点，为了保证不重叠，必须 dfn[i] > lst。

---

4. 建立树结构

之后代码构建了一个树结构，head 和 nxt 是邻接表，add(u, v) 表示 v 是 u 的孩子。

这个树是按照区间包含关系建立的：每个区间 [dfn[i], i] 作为节点，它的父节点是包含它的下一个区间。

---

5. DFS 序与 BIT

用 DFS 序将树结构线性化，然后用树状数组（BIT）维护某些信息，用于快速回答查询。

查询时，对于区间 ([L, R])，找到在 DFS 序中对应的节点，用 BIT 查询覆盖的区间数量。

---

算法标签

• 前缀和 + 哈希 (Prefix Sum + Hashing)
• 离散化 (Discretization)
• 贪心选择 (Greedy Selection)
• 树状数组 (Fenwick Tree / BIT)
• DFS 序 (DFS Order)
• 区间查询优化 (Range Query Optimization)

---

核心思想总结

1. 将“和为 0 的子数组”转化为“前缀和相等的位置对”。
2. 用贪心法选择不重叠的区间：按右端点排序，每次选左端点尽量靠右的。
3. 将选出的区间建成树结构，利用 DFS 序和 BIT 快速回答任意区间 ([L, R]) 内能选出的最多子数组数。
4. 时间复杂度 (O((N+Q) \log N))，适合 (N, Q \le 4\times 10^5)。

---

样例验证

对于样例：

• 数组 1 2 -3 0 1 -4 3 2 -1 1
• 前缀和 1 3 0 0 1 -3 0 2 1 2
• 和为 0 的子数组有：[3,3], [1,3], [4,4], [3,4], [6,6], [3,7], [7,7], [9,9], [8,10] 等
• 贪心选择后得到最优不重叠集合。

查询 [1,10] 能选 4 个，例如 [1,3], [4,4], [6,7], [8,10]。

---

这样，我们就用高效的数据结构完成了大规模数据的查询。