在某所学校，有一群善于咕咕咕的鸽子。 鸽子是很可爱的动物，桃子很喜欢。她每天早晨都要喂鸽子，然而这些鸽子渐渐地不爱运动，变得越来越胖，最后甚至飞不起来了。 桃子很着急，这些鸽子需要运动来减肥。她想到一个好方法，让鸽子和学生一起上课间操。 鸽子们按照学生们站队伍的方法，分成 n n 个队站好，每个队有一定数量的鸽子。每两个鸽子队伍相距一定的距离，这个距离有大有小，但可以忽略队伍本身的长宽，并且没有两个鸽子队站在同一位置。即鸽子队伍可以看成在 x x 轴上互不重合的点。桃子将队伍从左到右编号为 1 ∼ n 1∼n。每个队伍都有一个位置坐标，第 i i 队的位置坐标为 ( p i , 0 ) (p i ​ ,0)。 这所学校的课间操令鸽子发指，这些鸽子并不想跳，所以它们会逃走。而每当鸽子逃走，桃子就会发动技能把它们抓回来（鸽子：悲剧啊！）。桃子也会调整一队鸽子的位置，使一些队伍相邻且互相熟悉的鸽子不会组团逃跑。 总的说来，会有以下两个操作： A l r c A l r c，若 c > 0 c>0，则表示 桃子又抓回一些逃跑的鸽子，她将这些鸽子放到编号在

```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; struct Node { ll sum; // 区间鸽子总数 ll weighted_sum; // 区间位置加权和 sum(p_i * a_i) ll pos_sum; // 区间位置和 sum(p_i) ll cnt; // 区间队伍数 }; class SegmentTree { private: int n; vector<Node> tree; vector<ll> lazy; vector<ll> positions; // 存储每个队伍的位置 void push_up(int idx) { tree[idx].sum = tree[idx * 2].sum + tree[idx * 2 + 1].sum; tree[idx].weighted_sum = tree[idx * 2].weighted_sum + tree[idx * 2 + 1].weighted_sum; tree[idx].pos_sum = tree[idx * 2].pos_sum + tree[idx * 2 + 1].pos_sum; tree[idx].cnt = tree[idx * 2].cnt + tree[idx * 2 + 1].cnt; } void apply(int idx, ll val) { tree[idx].sum += val * tree[idx].cnt; tree[idx].weighted_sum += val * tree[idx].pos_sum; lazy[idx] += val; } void push_down(int idx) { if (lazy[idx] != 0) { apply(idx * 2, lazy[idx]); apply(idx * 2 + 1, lazy[idx]); lazy[idx] = 0; } } void build(int idx, int l, int r, const vector<ll>& a, const vector<ll>& p) { if (l == r) { tree[idx] = {a[l], p[l] * a[l], p[l], 1}; return; } int mid = (l + r) / 2; build(idx * 2, l, mid, a, p); build(idx * 2 + 1, mid + 1, r, a, p); push_up(idx); } void update_range(int idx, int l, int r, int ql, int qr, ll val) { if (ql <= l && r <= qr) { apply(idx, val); return; } push_down(idx); int mid = (l + r) / 2; if (ql <= mid) update_range(idx * 2, l, mid, ql, qr, val); if (qr > mid) update_range(idx * 2 + 1, mid + 1, r, ql, qr, val); push_up(idx); } void update_position(int idx, int l, int r, int pos, ll new_pos) { if (l == r) { ll delta = new_pos - tree[idx].pos_sum; tree[idx].pos_sum = new_pos; tree[idx].weighted_sum += delta * tree[idx].sum; return; } push_down(idx); int mid = (l + r) / 2; if (pos <= mid) update_position(idx * 2, l, mid, pos, new_pos); else update_position(idx * 2 + 1, mid + 1, r, pos, new_pos); push_up(idx); } Node query(int idx, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tree[idx]; push_down(idx); int mid = (l + r) / 2; Node res = {0, 0, 0, 0}; if (ql <= mid) { Node left = query(idx * 2, l, mid, ql, qr); res.sum += left.sum; res.weighted_sum += left.weighted_sum; res.pos_sum += left.pos_sum; res.cnt += left.cnt; } if (qr > mid) { Node right = query(idx * 2 + 1, mid + 1, r, ql, qr); res.sum += right.sum; res.weighted_sum += right.weighted_sum; res.pos_sum += right.pos_sum; res.cnt += right.cnt; } return res; } public: SegmentTree(int size, const vector<ll>& a, const vector<ll>& p) : n(size) { tree.resize(4 * n); lazy.resize(4 * n, 0); positions = p; build(1, 0, n - 1, a, p); } void add_pigeons(int l, int r, ll c) { update_range(1, 0, n - 1, l, r, c); } void move_team(int x, int y) { if (x == y) return; int l = min(x, y); int r = max(x, y); // 获取x位置的信息 Node node_x = query(1, 0, n - 1, x, x); ll pos_x = node_x.pos_sum; // 获取y位置的信息 Node node_y = query(1, 0, n - 1, y, y); ll pos_y = node_y.pos_sum; // 更新x到y的位置 if (x < y) { // x向右移动，中间队伍向左移动 for (int i = x + 1; i <= y; i++) { Node node_i = query(1, 0, n - 1, i, i); update_position(1, 0, n - 1, i - 1, node_i.pos_sum); } update_position(1, 0, n - 1, y, pos_x); } else { // x向左移动，中间队伍向右移动 for (int i = x - 1; i >= y; i--) { Node node_i = query(1, 0, n - 1, i, i); update_position(1, 0, n - 1, i + 1, node_i.pos_sum); } update_position(1, 0, n - 1, y, pos_x); } } ll get_optimal_position() { Node total = query(1, 0, n - 1, 0, n - 1); if (total.sum == 0) return 0; // 二分查找中位数位置 int l = 0, r = n - 1; ll target = (total.sum + 1) / 2; // 向上取整 while (l < r) { int mid = (l + r) / 2; Node left = query(1, 0, n - 1, 0, mid); if (left.sum >= target) { r = mid; } else { l = mid + 1; } } // 获取第l个队伍的位置 Node node = query(1, 0, n - 1, l, l); return node.pos_sum; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<ll> a(n), p(n); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> p[i]; SegmentTree seg(n, a, p); // 输出初始最优位置 cout << seg.get_optimal_position() << "\n"; for (int i = 0; i < m; i++) { char op; cin >> op; if (op == 'A') { int l, r; ll c; cin >> l >> r >> c; l--; r--; // 转为0-based seg.add_pigeons(l, r, c); } else if (op == 'B') { int x, y; cin >> x >> y; x--; y--; // 转为0-based seg.move_team(x, y); } // 输出操作后的最优位置 cout << seg.get_optimal_position() << "\n"; } return 0; } ``` 代码说明： 1. 数据结构设计： - 使用线段树维护四个关键信息：鸽子总数、位置加权和、位置和、队伍数 - 支持区间更新（增减鸽子）和单点更新（移动队伍位置） 2. 核心算法： - 最优集合位置是鸽子数量的中位数对应的位置 - 通过线段树二分查找中位数位置 - 移动操作时，更新相关队伍的位置信息 3. 时间复杂度： - 每次查询：O(log n) - A操作：O(log n) - B操作：O(k log n)，其中k为移动的距离 4. 注意事项： - 使用long long防止溢出 - 输入输出使用快速IO - 位置索引从0开始处理 这个解决方案能够高效处理题目中的两种操作，并在每次操作后快速找到最优集合位置。 [2026-01-19 19:14:39 | AI问答 | 2067点数解答]