题解：AT_abc432_e [ABC432E] Clamp

题目分析

说白了~~我白说了~~就是给你个长度为

N

的序列

A

，然后会给你

Q

次操作，操作呢分以下两种：

1 x y ：把 $A_x$ 修改成 $y$ 。
2 l r : 求出 $\displaystyle{\sum\limits_{i=1}^{N}\max(l,\min(r,A_i))}$ 的值。

看看第二个操作，不难想到

A_i

的值分三种情况：

$A_i < l$ ：贡献就为 $l$ ；
$l \le A_i \le r$ ：贡献就为 $A_i$ ；
$A_i > r$ ：贡献就为 $r$ 。

所以捏，查询操作就可以表示为：

l \cdot |\{i : A_i < l\}| + \sum_{i: l \leq A_i \leq r} A_i + r \cdot |\{i : A_i > r\}|

解法和思路

继续看着题目，我们需要一个数据结构来进行以下三种操作：

统计小于 $l$ 的元素个数
统计在区间 $[l, r]$ 内的元素和
统计大于 $r$ 的元素个数

值域线段树 你值得拥有 awa。

我们使用两颗线段树：

tr_cnt：统计每个数值出现的次数
tr_sum：统计每个数值的总和

两棵线段树都建立在值域

[0, 5\times 10^5]

上的哦。

所以捏，实现步骤就和下面一样啦！

初始化：
- 建两颗空线段树
- 将序列 $A$ 中的每个元素插入到两个线段树中
修改操作（单点修改）：
- 从两个线段树中删除原来的 $A_x$ 值
- 将新的 $y$ 值插入到两个线段树中
- 更新 $A_x = y$
查询操作（区间查询）：
- 小于 $l$ 的元素个数：cntl = query_cnt(0, l-1)
- 在 $[l, r]$ 区间内的元素和：summ = query_sum(l, r)
- 大于 $r$ 的元素个数：cntg = query_cnt(r+1, V)
- 结果： $l \times cntl + summ + r \times cntg$

我们当然不能少考虑特殊情况！

当

l > r

时，所有元素的贡献都是

l

，所以呀，结果直接为

l \times N

。

最后，当然要看看会不会超时或者爆空间对吧， MLE 和 TLE 真的很难受 qwq，所以捏，Losi 就分析分析复杂度。

线段树的每次操作时间复杂度是 $O(\log M)$ ，其中 $M$ 是值域大小喵
那么总的时间复杂度就是 $O((N+Q) \log M)$ ，其中 $M = 5 \times 10^5$ 哦~
空间复杂度当然为 $O(M)$ 啦

AC Code

终于到~~激动人心的~~代码环节啦！完整代码如下哦：

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
const int V = 5e5;
struct Node {
    int l, r;
    long long cnt;
    long long sum;
};
Node tr_cnt[4 * N], tr_sum[4 * N];
int a[N];
int n, q;
// 计数线段树的pushup操作
void pushup_cnt(int k) {
    int lc = k * 2;
    int rc = k * 2 + 1;
    tr_cnt[k].cnt = tr_cnt[lc].cnt + tr_cnt[rc].cnt;
}
// 求和线段树的pushup操作  
void pushup_sum(int k) {
    int lc = k * 2;
    int rc = k * 2 + 1;
    tr_sum[k].sum = tr_sum[lc].sum + tr_sum[rc].sum;
}
// 构建计数线段树
void build_cnt(int k, int l, int r) {
    tr_cnt[k].l = l;
    tr_cnt[k].r = r;
    tr_cnt[k].cnt = 0;
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    int lc = k * 2;
    int rc = k * 2 + 1;
    build_cnt(lc, l, mid);
    build_cnt(rc, mid + 1, r);
    pushup_cnt(k);
}
// 构建求和线段树
void build_sum(int k, int l, int r) {
    tr_sum[k].l = l;
    tr_sum[k].r = r;
    tr_sum[k].sum = 0;
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    int lc = k * 2;
    int rc = k * 2 + 1;
    build_sum(lc, l, mid);
    build_sum(rc, mid + 1, r);
    pushup_sum(k);
}
// 更新计数线段树
void update_cnt(int k, int pos, int delta) {
    if (tr_cnt[k].l == tr_cnt[k].r && tr_cnt[k].l == pos) {
        tr_cnt[k].cnt += delta;
        return;
    }
    int mid = (tr_cnt[k].l + tr_cnt[k].r) >> 1;
    int lc = k * 2;
    int rc = k * 2 + 1;
    if (pos <= mid) {
        update_cnt(lc, pos, delta);
    }
	else {
        update_cnt(rc, pos, delta);
    }
    pushup_cnt(k);
}
// 更新求和线段树
void update_sum(int k, int pos, int delta) {
    if (tr_sum[k].l == tr_sum[k].r && tr_sum[k].l == pos) {
        tr_sum[k].sum += delta;
        return;
    }
    int mid = (tr_sum[k].l + tr_sum[k].r) >> 1;
    int lc = k * 2;
    int rc = k * 2 + 1;
    if (pos <= mid) {
        update_sum(lc, pos, delta);
    }
	else {
        update_sum(rc, pos, delta);
    }
    pushup_sum(k);
}
// 查询计数线段树的区间和
long long query_cnt(int k, int l, int r) {
    if (l > r) {
        return 0;
    }
    if (tr_cnt[k].l >= l && tr_cnt[k].r <= r) {
        return tr_cnt[k].cnt;
    }
    int mid = (tr_cnt[k].l + tr_cnt[k].r) >> 1;
    long long ans = 0;
    if (l <= mid) {
        ans += query_cnt(k * 2, l, min(r, mid));
    }
    if (r > mid) {
        ans += query_cnt(k * 2 + 1, max(l, mid + 1), r);
    }
    return ans;
}
// 查询求和线段树的区间和
long long query_sum(int k, int l, int r) {
    if (l > r) {
        return 0;
    }
    if (tr_sum[k].l >= l && tr_sum[k].r <= r) {
        return tr_sum[k].sum;
    }
    int mid = (tr_sum[k].l + tr_sum[k].r) >> 1;
    long long ans = 0;
    if (l <= mid) {
        ans += query_sum(k * 2, l, min(r, mid));
    }
    if (r > mid) {
        ans += query_sum(k * 2 + 1, max(l, mid + 1), r);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    // 初始化线段树
    build_cnt(1, 0, V);
    build_sum(1, 0, V);
    // 读入初始数组并更新线段树
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        update_cnt(1, a[i], 1);
        update_sum(1, a[i], a[i]);
    }
    // 处理查询
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            // 删除原来的值
            update_cnt(1, a[x], -1);
            update_sum(1, a[x], -a[x]);
            // 更新为新值
            a[x] = y;
            update_cnt(1, a[x], 1);
            update_sum(1, a[x], a[x]);
        }
		else {
            int l, r;
            cin >> l >> r;
            // 计算三种情况的贡献
            long long cntl = query_cnt(1, 0, l - 1);    // 小于l的元素个数
            long long summ = query_sum(1, l, r);        // [l,r]区间内的元素和
            long long cntg = query_cnt(1, r + 1, V);    // 大于r的元素个数
            long long ans = cntl * l + summ + cntg * r;
            cout << ans << "\n";
        }
    }
    return 0;
}

请勿抄袭题解。这会失去学术诚信，同时浪费洛谷评测资源。如果被发现抄题解，可能会被处以棕名惩罚或者被封号。——摘自《洛谷新用户必读》

既然都看到这了，为什么不点一个赞呢QWQ

题解：AT_abc432_e [ABC432E] Clamp

文章操作

题目分析

解法和思路

AC Code

相关推荐

评论

题解：AT_abc432_e [ABC432E] Clamp