题目简析

给定长度为 $n$ 的序列，$q$ 次询问，把在 $[l,r]$ 内的元素覆盖为 $x$。

求最初的和每次询问时元素之和。

思路解析

动态开点权值线段树

对于在区间的操作容易想到线段树，线段树支持区间查询、区间清零和单点更新。

用动态开点权值线段树维护值域上的元素个数和总和。

时间复杂度 $O(q \log V)$，其中 $V$ 是值域范围（$0 \le V \le10^9$），可以考虑离散化。

平衡树（FHQ-Treap）

使用 FHQ-Treap 维护值域。每个节点存储一个值 $val$，该值出现的次数 $cnt$，子树总和 $sum$，子树总节点数 $tot$。

对于每个查询：

分裂出值在 $[l, r]$ 范围内的节点。
删除这部分，合并剩余部分。
计算被删除的节点数 $cnt$ 和总和 $sum$。
插入 $cnt$ 个新值 $x$。

时间复杂度 $O((n + q) \log n )$。

STL

使用 std::map 存储每个值及其出现次数，维护值域到出现次数的映射，这样我们可以快速查找、删除和插入值。

使用 lower_bound 和 upper_bound 快速查找。

时间复杂度 $ O((n + q) \log n)$。

珂朵莉树

珂朵莉树特别适合有大量区间赋值操作，只需要考虑如何维护和就可以了。

直接操作值域点，利用 std::set 定位值域范围，合并相同值节点，这样，就可以 AC 了。

详见 OI WIKI 上的珂朵莉树。

时间复杂度 $O((n + q) \log D)$，其中 $D \le n + q$，$D$ 为不同值的数量。

代码实现

动态开点权值线段树实现：

#pragma G++ optimize("O3", "unroll-loops", "omit-frame-pointer", "inline")
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000000000;
const int MAXNODE = 20000000;
struct Node {int lson, rson;long long sum;long long cnt;bool zero;
} tree[MAXNODE + 10];
int root, tot;void push_up(int p) {tree[p].cnt = 0;tree[p].sum = 0;if (tree[p].lson) {tree[p].cnt += tree[tree[p].lson].cnt;tree[p].sum += tree[tree[p].lson].sum;}if (tree[p].rson) {tree[p].cnt += tree[tree[p].rson].cnt;tree[p].sum += tree[tree[p].rson].sum;}
}void push_down(int p) {if (tree[p].zero) {if (tree[p].lson) {int ls = tree[p].lson;tree[ls].cnt = 0;tree[ls].sum = 0;tree[ls].zero = true;}if (tree[p].rson) {int rs = tree[p].rson;tree[rs].cnt = 0;tree[rs].sum = 0;tree[rs].zero = true;}tree[p].zero = false;}
}void update_point(int& p, int l, int r, int pos, long long delta_cnt) {if (delta_cnt == 0)return;if (!p) {p = ++tot;tree[p].lson = tree[p].rson = 0;tree[p].sum = 0;tree[p].cnt = 0;tree[p].zero = false;}if (l == r) {tree[p].cnt += delta_cnt;tree[p].sum = tree[p].cnt * (long long)l;return;}push_down(p);int mid = (l + (long long)r) >> 1;if (pos <= mid) {update_point(tree[p].lson, l, mid, pos, delta_cnt);} else {update_point(tree[p].rson, mid + 1, r, pos, delta_cnt);}push_up(p);
}void update_zero(int& p, int l, int r, int ql, int qr) {if (!p || tree[p].cnt == 0)return;if (ql <= l && r <= qr) {tree[p].cnt = 0;tree[p].sum = 0;tree[p].zero = true;return;}push_down(p);int mid = (l + (long long)r) >> 1;if (ql <= mid) {update_zero(tree[p].lson, l, mid, ql, qr);}if (qr > mid) {update_zero(tree[p].rson, mid + 1, r, ql, qr);}push_up(p);
}pair<long long, long long> query(int p, int l, int r, int ql, int qr) {if (!p || tree[p].cnt == 0) {return {0, 0};}if (ql <= l && r <= qr) {return {tree[p].sum, tree[p].cnt};}push_down(p);int mid = (l + (long long)r) >> 1;pair<long long, long long> res = {0, 0};if (ql <= mid) {auto left_res = query(tree[p].lson, l, mid, ql, qr);res.first += left_res.first;res.second += left_res.second;}if (qr > mid) {auto right_res = query(tree[p].rson, mid + 1, r, ql, qr);res.first += right_res.first;res.second += right_res.second;}return res;
}
long long a[(int)(2e5 + 1)];
int main() {int n, q;scanf("%d %d", &n, &q);long long total = 0;for (int i = 0; i < n; i++) {scanf("%lld", &a[i]);total += a[i];}root = 0;tot = 0;for (int i = 0; i < n; i++) {update_point(root, 0, MAXV, a[i], 1);}printf("%lld\n", total);for (int j = 0; j < q; j++) {long long l, r, x;scanf("%lld %lld %lld", &l, &r, &x);auto res = query(root, 0, MAXV, l, r);long long remove_sum = res.first;long long remove_cnt = res.second;update_zero(root, 0, MAXV, l, r);if (remove_cnt > 0) {update_point(root, 0, MAXV, x, remove_cnt);}total = total - remove_sum + x * remove_cnt;printf("%lld\n", total);}return 0;
}

FHQ-Treap 实现：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int MAXN = 400010; // 最大节点数struct Node {int l, r;       // 左右子节点索引ll val;         // 节点存储的值ll cnt;         // 该值出现的次数ll sum;         // 子树值总和（值×出现次数）ll tot;         // 子树节点出现次数总和int rnd;        // 随机优先级
} tree[MAXN];int idx = 0;        // 节点池索引
int root = 0;       // 树根// 创建新节点
int new_node(ll val, ll cnt) {if (cnt == 0) return 0;idx++;tree[idx].l = tree[idx].r = 0;tree[idx].val = val;tree[idx].cnt = cnt;tree[idx].sum = val * cnt;tree[idx].tot = cnt;tree[idx].rnd = rand();return idx;
}// 更新节点信息
void push_up(int id) {if (!id) return;Node &t = tree[id];t.tot = tree[t.l].tot + tree[t.r].tot + t.cnt;t.sum = tree[t.l].sum + tree[t.r].sum + t.val * t.cnt;
}// 按值分裂：将树id分裂为<=k的树x和>k的树y
void split(int id, ll k, int &x, int &y) {if (!id) {x = y = 0;return;}if (tree[id].val <= k) {x = id;split(tree[id].r, k, tree[id].r, y);push_up(x);} else {y = id;split(tree[id].l, k, x, tree[id].l);push_up(y);}
}// 合并两棵树x和y（x的所有值<=y的所有值）
int merge(int x, int y) {if (!x || !y) return x | y;if (tree[x].rnd < tree[y].rnd) {tree[x].r = merge(tree[x].r, y);push_up(x);return x;} else {tree[y].l = merge(x, tree[y].l);push_up(y);return y;}
}// 插入cnt个值为val的节点
void insert(ll val, ll cnt) {if (cnt == 0) return;int x, y, z;z = 0;split(root, val, x, y);      // 分裂为<=val和>valsplit(x, val - 1, x, z);    // 将<=val的再分裂为<val和=valif (z) {tree[z].cnt += cnt;tree[z].sum += val * cnt;tree[z].tot += cnt;push_up(z); // 更新节点z} else {z = new_node(val, cnt);}root = merge(merge(x, z), y); // 合并三部分
}int main() {srand(time(0)); // 初始化随机种子int n, q;scanf("%d%d", &n, &q);root = idx = 0;// 读入初始数组for (int i = 0; i < n; i++) {ll a_val;scanf("%lld", &a_val);insert(a_val, 1); // 插入每个值}// 输出初始总和printf("%lld\n", tree[root].sum);// 处理每个查询for (int i = 0; i < q; i++) {ll l, r, x_val;scanf("%lld%lld%lld", &l, &r, &x_val);int left, mid, right, mid_right;// 第一次分裂：按l-1分裂split(root, l - 1, left, mid_right);// 第二次分裂：按r分裂split(mid_right, r, mid, right);// 合并左部分和右部分（删除中间部分）root = merge(left, right);ll del_cnt = 0, del_sum = 0;if (mid) {del_cnt = tree[mid].tot; // 被删除的节点数del_sum = tree[mid].sum; // 被删除节点的总和}// 插入新值insert(x_val, del_cnt);// 输出当前总和printf("%lld\n", tree[root].sum);}return 0;
}

std::map 实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;int main() {ios::sync_with_stdio(false);cin.tie(0);int n, q;cin >> n >> q;map<ll, ll> m; // 值 -> 出现次数ll total_sum = 0;// 读入初始数组for (int i = 0; i < n; i++) {ll a_val;cin >> a_val;m[a_val]++; // 计数total_sum += a_val;}// 输出初始总和cout << total_sum << '\n';for (int i = 0; i < q; i++) {ll l, r, x;cin >> l >> r >> x;// 找到第一个大于等于 l 的节点auto it = m.lower_bound(l);ll cnt_total = 0; // 记录被删除的元素总数// 遍历区间 [l, r] 内的节点while (it != m.end() && it->first <= r) {// 记录当前节点的值和出现次数ll num = it->first;ll cnt = it->second;cnt_total += cnt;total_sum -= num * cnt; // 从总和中减去贡献// 删除当前节点，并获取下一个节点的迭代器it = m.erase(it);}// 如果存在被删除的元素，则将它们替换为 xif (cnt_total > 0) {m[x] += cnt_total; // 增加 x 的出现次数total_sum += x * cnt_total; // 更新总和}// 输出当前总和cout << total_sum << '\n';}return 0;
}

珂朵莉树实现：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;// 节点结构体：表示值域区间 [v, v]
struct Node {ll v;           // 元素值mutable ll cnt; // 该值出现的次数Node(ll v, ll cnt) : v(v), cnt(cnt) {}// 按值排序bool operator<(const Node& rhs) const {return v < rhs.v;}
};class ChthollyTree {
private:set<Node> s;    // 存储所有值域节点ll total_sum;   // 当前总和public:ChthollyTree() : total_sum(0) {}// 添加初始元素void add_element(ll value) {auto it = s.find(Node(value, 0));if (it != s.end()) {it->cnt++;} else {s.insert(Node(value, 1));}total_sum += value;}// 处理查询void query(ll l, ll r, ll x) {// 找到第一个 ≥ l 的节点auto it = s.lower_bound(Node(l, 0));vector<set<Node>::iterator> to_remove;ll cnt_total = 0;ll sum_remove = 0;// 收集要删除的节点（迭代器）while (it != s.end() && it->v <= r) {cnt_total += it->cnt;sum_remove += it->v * it->cnt;to_remove.push_back(it);it++;}// 删除节点for (auto iter : to_remove) {s.erase(iter);}// 更新总和total_sum = total_sum - sum_remove + x * cnt_total;// 插入新值if (cnt_total > 0) {auto it_x = s.find(Node(x, 0));if (it_x != s.end()) {it_x->cnt += cnt_total;} else {s.insert(Node(x, cnt_total));}}}// 获取当前总和ll get_sum() const {return total_sum;}
};int main() {ios::sync_with_stdio(false);cin.tie(0);int n, q;cin >> n >> q;ChthollyTree ct;// 读入初始数组for (int i = 0; i < n; i++) {ll a_val;cin >> a_val;ct.add_element(a_val);}// 输出初始总和cout << ct.get_sum() << '\n';// 处理查询for (int i = 0; i < q; i++) {ll l, r, x;cin >> l >> r >> x;ct.query(l, r, x);cout << ct.get_sum() << '\n';}return 0;
}