题解：序列交换与区间查询问题

问题分析

我们有一个序列 $a_1,\dots,a_n$，每次操作：

1. 从 $i=1$ 到 $n$，如果 $x > a_i$，就交换 $x$ 和 $a_i$
2. 查询 $\sum_{i=l}^r a_i$

直接模拟的复杂度是 $O(nm)$，在 $n,m \le 5\times 10^5$ 时不可行。

---

关键观察

1. 操作的本质

这个操作实际上是在做：

• 把 $x$ 插入到序列中合适的位置
• 把序列中所有小于 $x$ 的元素"上浮"到前面
• 最终 $x$ 会变成序列中某个位置的值

更具体地说：

• 设序列中所有严格小于 $x$ 的值为 $v_1 < v_2 < \cdots < v_k$
• 操作后：$a_1 = v_1, a_2 = v_2, \dots, a_k = v_k, a_{k+1} = x$，其余不变
• 原来的 $x$ 被替换为最后一个被交换的值

---

2. 数据结构选择

我们需要支持：

• 快速找到所有小于 $x$ 的值
• 快速区间求和
• 高效修改序列

平衡树（如 Splay、Treap）或线段树是合适的选择。

---

3. 平衡树解法

用平衡树维护序列，每个节点存储：

• 值
• 子树大小
• 子树和

操作过程：

1. 在平衡树中找到所有值小于 $x$ 的节点
2. 将这些节点移到最前面
3. 在它们后面插入 $x$
4. 查询区间和

具体步骤：

• 按值分裂：将树分成 $< x$ 和 $\ge x$ 两部分
• 在 $< x$ 的部分中找到最大值 $maxval$
• 将 $x$ 插入到 $< x$ 部分之后，$\ge x$ 部分之前
• 原来的 $x$ 被替换为 $maxval$（最后一个交换的值）

---

4. 线段树结合有序结构的解法

另一种思路：用权值线段树维护每个值的出现次数和总和。

但本题需要维护序列顺序，所以需要支持按位置的操作。

---

5. 更简单的思路：维护最小值堆

观察发现，每次操作实际上是把序列"排序"了一部分：

• 所有小于 $x$ 的数被提到前面
• $x$ 插入到它们后面
• 其余数相对顺序不变

我们可以维护：

• 一个"已排序"的前缀
• 剩余未排序的部分

但这样仍然难以高效处理。

---

6. 正解：Splay 或 Treap

使用平衡树，每个节点代表序列中的一个位置，存储：

• 值 $val$
• 子树大小 $size$
• 子树和 $sum$

操作算法：

// 伪代码
Node* root;  // 平衡树根节点

void process(int x) {
    // 按值分裂：将树分成 <x 和 >=x 两部分
    auto [left, right] = split_by_value(root, x);
    
    if (left == nullptr) {
        // 没有小于x的值，直接在最前面插入x
        root = merge(new Node(x), right);
    } else {
        // 找到left中的最大值（最后一个被交换的值）
        int max_val = find_max(left);
        
        // 在left后面插入x
        auto [left_part, max_node] = split_by_rank(left, size(left)-1);
        root = merge(merge(left_part, new Node(x)), right);
        
        // 更新x为max_val（用于后续操作）
        x = max_val;
    }
}

---

7. 复杂度分析

• 每次操作：$O(\log n)$
• 总复杂度：$O((n+m)\log n)$
• 空间复杂度：$O(n)$

在 $n,m \le 5\times 10^5$ 时可行。

---

8. 实现细节

平衡树节点定义：

struct Node {
    int val, size;
    long long sum;
    Node *left, *right;
    // 维护size和sum的函数
    void update() {
        size = 1 + get_size(left) + get_size(right);
        sum = val + get_sum(left) + get_sum(right);
    }
};

核心操作：

long long query(int l, int r) {
    auto [left, mid_right] = split_by_rank(root, l-1);
    auto [mid, right] = split_by_rank(mid_right, r-l+1);
    long long res = get_sum(mid);
    root = merge(merge(left, mid), right);
    return res;
}

void modify(int x) {
    // 实现上述process操作
}

---

9. 样例验证

输入：

6 8
1 6 1 3 5 4
2 3 6

初始序列：$[1,6,1,3,5,4]$

第一次操作：$x=2$

• 比较过程：
  • $2 > 1$，交换：$a_1=2, x=1$ → $[2,6,1,3,5,4]$
  • $1 > 6$？否
  • $1 > 1$？否
  • $1 > 3$？否
  • $1 > 5$？否
  • $1 > 4$？否
• 最终序列：$[2,6,1,3,5,4]$
• 查询 $[3,6]$ 和：$1+3+5+4=13$

输出 $13$，与样例一致。

---

10. 优化技巧

• 使用内存池避免频繁new/delete
• 非递归Splay减少常数
• 批量操作优化

---

代码框架

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 500010;

struct Node {
    int val, size;
    long long sum;
    Node *left, *right;
    Node(int v) : val(v), size(1), sum(v), left(nullptr), right(nullptr) {}
};

// 平衡树操作：split, merge, insert, query_range_sum 等

int n, m;
int a[N];
Node* root;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        // 构建初始平衡树
        root = insert(root, new Node(a[i]), i);
    }
    
    while (m--) {
        int x, l, r;
        cin >> x >> l >> r;
        process(x);  // 执行交换操作
        cout << query(l, r) << '\n';  // 查询区间和
    }
    
    return 0;
}

---

总结

本题的关键在于：

1. 理解操作的本质是部分排序和插入
2. 选择平衡树维护序列
3. 高效实现分裂、合并和查询操作
4. 注意常数优化以适应大数据量

这是一个典型的数据结构题，考察对高级数据结构的掌握和灵活运用。