U390630 分考场题解-526互联

题目链接:U390630 分考场

本题来自于2019年蓝桥杯国赛的题。在洛谷上也被标为了假题。原因是首先官方在需要输出浮点数的情况下，并没有开启spj，并且官方所给的数据当中，总有一两个数据以不知道到底是怎样的一个算法导致能莫名其妙四舍五入了，保留十位小数也看不出不该四舍五入的理由。并且在很明显的树套树的题目中给出了 $2e5 \text{的数据范围,却只给了256} mb$。所以我把官网数据爬了下，把错的几条修正了下，并且自己又造了下新的数据。然后想着本题不是比赛题，只是为了大家训练 ds 使用。所以把 $2e5$ 的数据稍微构造了下，保证离线带上修改的值也是 $2e5$ 。这样一来一些大常数做法也不至于被卡空间了，已经申请调到 $1G$了。放心食用。

思路讲解：

首先呢，需要贪心证明一些东西。先考虑题目让求的式子：

\[ \max(\frac{\sum_{i=1}^{k}(\frac{\sum_{j=1}^{cnt_i}{val_{ij}}}{cnt_i})}{k}),\text{等价于求} \max(\sum_{i=1}^{k}\frac{\sum_{j=1}^{cnt_i}{val_{ij}}}{cnt_i}) \text{之后除以k} \]

其中 $cnt_i$ 表示第 $i$ 组的元素个数，而 $val_{ij}$ 表示第 $i$ 组第 $j$ 个元素的值。考虑如何分组使得最优。先来考虑一下以下两种策略：

考虑单独一个数一组其余数为一组，这种情况下单独一个数越大越好。数学表示为：
考虑 $v_1 \le v_2 \le v_3 \text{....} \le v_n=v_{max}$

\[ val_{max}+\frac{\sum_{i=1}^{n-1}val_i}{n-1} \ge val_{other}+\frac{\sum_{i=1}^{n}val_i(i \neq other)}{n-1} \]

稍微通个分做差得到左边-右边有：

\[ \frac{n-2}{n-1} \times(val_{max}-val_{other}) \ge 0 \]

考率平均分组和上述第一点分组谁更优。考虑 $4$ 个数的情况。比如：

\[ (v_4+\frac{v_1+v_2+v_3}{3}) \text{与} (\frac{v_4+v_3}{2} + \frac{v_2+v_1}{2}) \]

考虑左-右同理可得：

\[ \frac{3 \times v4-(v1+v2+v3)}{6} \ge 0 \]

所以稍微推广到多个数一样同理可证：单个数自成一组由于平均分组。
那么我们就得到了以下的贪心策略了：

越多的数自成一组越好。
这些自成一组的数越大越好。

贪心最终算法

根据上述结合题意，对于查询而言我们需要分为 $k$ 组，那么我们贪心地至多可以取 $k-1$ 个数自成一组，再贪心而言，这 $k-1$ 个数应该为最大的 $k-1$ 个数。所以最终需要维护的数据结构功能为:

1.单点修改
2.区间查询 $[l,r]$ 上 $1 \sim kth$ 数的和。比如求最大的 $k-1$ 个数可以用区间总和减去 $1 \sim cnt_{l\sim r}-(k-1)$ 的数之和。剩余的数之和也是需要知道的。

正文硬货

开始阐述各种解法，包括错解和常数大的解法。

在观看之前，务必保证你已经会了如何求 $1-kth$ 之和问题。如果不会请学习这题:

P3168 [CQOI2015] 任务查询系统。如果你不会主席树之类的经典静态区间求 Kth 问题，那么可以观看这篇文章静态主席树教程

比较好想的错解

线段树套平衡树

这也是最经典的树套树入门数据结构。我们在 P3380 【模板】二逼平衡树（树套树）容易知道，传统的线段树套平衡树寻找第 $k$ 大的思路是三支 $\log$ 的。具体为二分答案+查找指定区间上的一系列平衡树+计算这个比这个二分的数在每棵平衡树上小的数的总和是否满足 check。很显然的三支log。所以使用这类数据结构而言，我们可以轻松地写出最终参照代码：

早期瞎写较烂代码1

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

template <typename T, T N>
T ModInt(T value) { return (value % N + N) % N; }

#define mod(m, n) ModInt<int,n>(m);

struct Node
{
    ll val;
    Node* child[2];
    ll size{1};

    Node(ll val) : val(val)
    {
        child[0] = child[1] = nullptr;
    }

    void update()
    {
        size = 1;
        if (child[0] != nullptr)size += child[0]->size;
        if (child[1] != nullptr)size += child[1]->size;
    }
};

ll get_size(Node* node)
{
    return node ? node->size : 0;
}

enum Rota
{
    L = 1,
    R = 0
};

struct SBT
{
    Node* root{nullptr};

    void insert(const ll v)
    {
        root = add(root, v);
    }

    static Node* rota(Node* node, Rota t)
    {
        auto new_root = node->child[t];
        node->child[t] = new_root->child[t ^ 1];
        new_root->child[t ^ 1] = node;
        node->update();
        new_root->update();
        return new_root;
    }

    static Node* push_down(Node* node)
    {
        if (node == nullptr)return nullptr;
        ll l = get_size(node->child[0]);
        ll r = get_size(node->child[1]);
        ll l_l = 0, l_r = 0, r_l = 0, r_r = 0;
        if (node->child[0])
        {
            l_l = get_size(node->child[0]->child[0]), l_r = get_size(node->child[0]->child[1]);
        }
        if (node->child[1])
        {
            r_l = get_size(node->child[1]->child[0]), r_r = get_size(node->child[1]->child[1]);
        }
        if (l_l > r)
        {
            node = rota(node, Rota::R);
            node->child[1] = push_down(node->child[1]);
            node = push_down(node);
        }
        else if (l_r > r)
        {
            node->child[0] = rota(node->child[0], Rota::L);
            node = rota(node, Rota::R);
            node->child[0] = push_down(node->child[0]);
            node->child[1] = push_down(node->child[1]);
            node = push_down(node);
        }
        else if (r_l > l)
        {
            node->child[1] = rota(node->child[1], Rota::R);
            node = rota(node, Rota::L);
            node->child[0] = push_down(node->child[0]);
            node->child[1] = push_down(node->child[1]);
            node = push_down(node);
        }
        else if (r_r > l)
        {
            node = rota(node, Rota::L);
            node->child[0] = push_down(node->child[0]);
            node = push_down(node);
        }
        return node;
    }

    static Node* add(Node* node, const ll val)
    {
        if (node == nullptr)return new Node(val);
        if (node->val > val)
        {
            node->child[0] = add(node->child[0], val);
        }
        else
        {
            node->child[1] = add(node->child[1], val);
        }
        node->update();
        return push_down(node);
    }

    void remove(ll val)
    {
        root = del(root, val);
    }

    static Node* del(Node* node, ll val)
    {
        if (node == nullptr)return nullptr;
        if (node->val > val)
        {
            node->child[0] = del(node->child[0], val);
        }
        else if (node->val < val)
        {
            node->child[1] = del(node->child[1], val);
        }
        else
        {
            int state = 0;
            if (node->child[0] != nullptr)state |= 1;
            if (node->child[1] != nullptr)state |= 1 << 1;
            if (state == 0)return nullptr;
            if (state == 1)return node->child[0];
            if (state == 2)return node->child[1];
            Node* ans = node->child[0];
            while (ans->child[1])ans = ans->child[1];
            node->val = ans->val;
            node->child[0] = del(node->child[0], node->val);
        }
        node->update();
        return node;
    }

    ll query_kth(ll val)
    {
        return q_kth(root, val);
    }

    ll q_kth(Node* node, ll val)
    {
        if (node == nullptr)return 0;
        ll size = node->child[0] == nullptr ? 0 : node->child[0]->size;
        if (val <= node->val)
        {
            return q_kth(node->child[0], val);
        }
        return q_kth(node->child[1], val) + 1 + size;
    }
};

struct Node2
{
    Node2* left;
    Node2* right;
    SBT* root;
    int l, r, mid;

    Node2(int l, int r) : l(l), r(r)
    {
        mid = (l + r) >> 1;
        left = right = nullptr;
        root = new SBT();
    }
};

void push_down(Node2* node)
{
    if (node->left == nullptr)node->left = new Node2(node->l, node->mid);
    if (node->right == nullptr)node->right = new Node2(node->mid + 1, node->r);
}

struct Seg
{
    Node2* root;
    ll* b;

    void build(Node2* node)
    {
        push_down(node);
        for (int i = node->l; i <= node->r; i++)node->root->insert(b[i]);
        if (node->l == node->r)
        {
            return;
        }
        build(node->left);
        build(node->right);
    }

    Seg(ll* a, const int n)
    {
        root = new Node2(0, n - 1);
        b = a;
        build(root);
    }

    void update(const int k, const int val) const
    {
        u(b[k], k, val, root);
        b[k] = val;
    }

    static void u(const int old, const int x, const ll val, const Node2* node)
    {
        node->root->remove(old);
        node->root->insert(val);
        if (node->l == x && node->r == x)
        {
            return;
        }
        if (x <= node->mid)u(old, x, val, node->left);
        else u(old, x, val, node->right);
    }

    ll query(const int l, const int r, const ll val)
    {
        return q(l, r, val, root) + 1;
    }

    ll q(const int l, const int r, const ll val, const Node2* node)
    {
        if (l <= node->l && node->r <= r) return node->root->query_kth(val);
        ll ans = 0;
        if (l <= node->mid)ans += q(l, r, val, node->left);
        if (r > node->mid) ans += q(l, r, val, node->right);
        return ans;
    }

    ll kth(const int l, const int r, const int k)
    {
        ll left = 0;
        ll right = 1e18;
        while (left < right)
        {
            auto mid = (right + left + 1) >> 1;
            if (query(l, r, mid) <= k)left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

int n;

void solve()
{
    scanf("%d", &n);
    auto a = new ll[n];
    for (int i = 0; i < n; i++)scanf("%lld", &a[i]);
    auto seg = new Seg(a, n);
    int m;
    scanf("%d", &m);
    while (m--)
    {
        int t;
        scanf("%d", &t);
        if (t == 1)
        {
            ll p, x;
            scanf("%lld %lld", &p, &x);
            p--;
            seg->update(p, x);
            a[p] = x;
        }
        else
        {
            ll l, r, k;
            scanf("%lld %lld %lld", &l, &r, &k);
            l--, r--;
            ll d = r - l + 1;
            long double ans = 0.0;
            if (d == k)
            {
                ll t = 0;
                for (int i = l; i <= r; i++)
                {
                    t += a[i];
                }
                ll su = t;
                ans = static_cast<long double>(su) / static_cast<long double>(k);
            }
            else
            {
                ll s = d - (k - 1);
                ll tm = seg->kth(l, r, s);
                ll y = 0;
                ll su = 0;
                ll prefix = 0;
                for (ll i = l; i <= r; i++)
                {
                    if (a[i] <= tm)prefix += a[i], y++;
                    else su += a[i];
                }
                if (y > s)
                {
                    prefix -= (y - s) * tm;
                    su += (y - s) * tm;
                }
                ans = static_cast<long double>(prefix) / static_cast<long double>(s) / static_cast<long double>(k) +
                    static_cast<long double>(su) / static_cast<long double>(k);
            }
            printf("%.3Lf\n", ans);
        }
    }
    delete[]a;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //------------------------------------------------------
    int t = 1;
    // cin >> t;
    while (t--)solve();
}

早期瞎写较烂代码2

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

template <typename T, T N>
T ModInt(T value) { return (value % N + N) % N; }

#define mod(m, n) ModInt<int,n>(m);

struct InNode
{
    ll l, r, mid;
    InNode* left;
    InNode* right;
    ll val;
    ll cnt;

    InNode(ll l, ll r) : l(l), r(r)
    {
        mid = (l + r) >> 1;
        cnt = 0;
        val = 0;
        left = right = nullptr;
    }
};

void push_down1(InNode* node)
{
    if (node->left == nullptr)node->left = new InNode(node->l, node->mid);
    if (node->right == nullptr)node->right = new InNode(node->mid + 1, node->r);
}

void push_up1(InNode* node)
{
    node->val = node->left->val + node->right->val;
    node->cnt = node->left->cnt + node->right->cnt;
}

struct InSeg
{
    InNode* root;

    InSeg()
    {
        root = new InNode(0, 1e11);
    }

    void update(ll old, ll newValue)
    {
        add(old, -old, -1, root);
        add(newValue, newValue, 1, root);
    }

    void add(ll x, ll v, ll c, InNode* node)
    {
        if (node->l == x && node->r == x)
        {
            node->val += v;
            node->cnt += c;
            return;
        }
        push_down1(node);
        if (x <= node->mid)add(x, v, c, node->left);
        else add(x, v, c, node->right);
        push_up1(node);
    }

    ll query_cnt(ll l, ll r, InNode* node)
    {
        if (l <= node->l && node->r <= r)
        {
            ll ans = node->cnt;
            return ans;
        }
        int ans = 0;
        push_down1(node);
        if (l <= node->mid)ans += query_cnt(l, r, node->left);
        if (r > node->mid)ans += query_cnt(l, r, node->right);
        return ans;
    }


    ll sum_prefix(ll l, ll r, InNode* node)
    {
        if (l <= node->l && node->r <= r)return node->val;
        push_down1(node);
        ll ans = 0;
        if (l <= node->mid)ans += sum_prefix(l, r, node->left);
        if (r > node->mid)ans += sum_prefix(l, r, node->right);
        return ans;
    }
};

struct OutNode
{
    int l, r, mid;
    InSeg* root;
    OutNode* left;
    OutNode* right;

    OutNode(ll l, ll r) : l(l), r(r)
    {
        mid = (l + r) >> 1;
        left = right = nullptr;
        root = new InSeg();
    }
};

void push_down2(OutNode* node)
{
    if (node->left == nullptr)node->left = new OutNode(node->l, node->mid);
    if (node->right == nullptr)node->right = new OutNode(node->mid + 1, node->r);
}

struct OutSeg
{
    OutNode* root;
    ll* b;

    void build(OutNode* node)
    {
        for (int i = node->l; i <= node->r; i++)
        {
            ll z = b[i];
            node->root->add(z, z, 1, node->root->root);
        }
        if (node->l == node->r)return;
        push_down2(node);
        build(node->left);
        build(node->right);
    }

    OutSeg(ll* a, int n)
    {
        root = new OutNode(0, n - 1);
        b = a;
        build(root);
    }

    ll query_cnt(ll l, ll r, ll val, OutNode* node)
    {
        if (l <= node->l && node->r <= r)
        {
            ll ans = node->root->query_cnt(0, val, node->root->root);
            return ans;
        }
        push_down2(node);
        ll ans = 0;
        if (l <= node->mid)ans += query_cnt(l, r, val, node->left);
        if (r > node->mid) ans += query_cnt(l, r, val, node->right);
        return ans;
    }

    void update(ll i, ll val)
    {
        ll old = b[i];
        update_(i, old, val, root);
        b[i] = val;
    }

    void update_(ll x, ll old, ll val, OutNode* node)
    {
        node->root->update(old, val);
        if (x == node->l && node->r == x)return;
        push_down2(node);
        if (x <= node->mid)update_(x, old, val, node->left);
        else update_(x, old, val, node->right);
    }

    ll query(ll l, ll r, int k)
    {
        ll left = 0;
        ll right = 1e11;
        while (left < right)
        {
            ll mid = (left + right + 1) >> 1;
            if (query_cnt(l, r, mid - 1, root) + 1 <= k)left = mid;
            else right = mid - 1;
        }
        return left;
    }

    ll query_ans(ll l, ll r, ll val, OutNode* node)
    {
        if (l <= node->l && node->r <= r)return node->root->sum_prefix(0, val, node->root->root);
        push_down2(node);
        ll ans = 0;
        if (l <= node->mid)ans += query_ans(l, r, val, node->left);
        if (r > node->mid)ans += query_ans(l, r, val, node->right);
        return ans;
    }

    ll query_sum(int l, int r, OutNode* node)
    {
        if (l <= node->l && node->r <= r)
        {
            ll ans = node->root->root->val;
            return ans;
        }
        push_down2(node);
        ll ans = 0;
        if (l <= node->mid)
        {
            ll k = query_sum(l, r, node->left);
            ans += k;
        }
        if (r > node->mid)
        {
            ll k = query_sum(l, r, node->right);
            ans += k;
        }
        return ans;
    }
};

ll n;

void solve()
{
    scanf("%lld", &n);
    auto a = new ll[n];
    for (int i = 0; i < n; i++)scanf("%lld", &a[i]);
    OutSeg* seg = new OutSeg(a, n);
    int m;
    scanf("%d", &m);
    while (m--)
    {
        int t;
        scanf("%d", &t);
        if (t == 1)
        {
            ll p, x;
            scanf("%lld %lld", &p, &x);
            p--;
            seg->update(p, x);
        }
        else
        {
            ll l, r, k;
            scanf("%lld %lld %lld", &l, &r, &k);
            l--, r--;
            ll d = r - l + 1;
            double ans = 0.0;
            if (d == k)
            {
                ll su = seg->query_sum(l, r, seg->root);
                ans = (double)su / (double)k;
            }
            else
            {
                ll s = d - (k - 1);
                ll tm = seg->query(l, r, s);
                ll num = seg->query_cnt(l, r, tm, seg->root); //实际编号
                ll prefix = seg->query_ans(l, r, tm, seg->root);
                prefix -= (s - num) * tm;
                ll su = seg->query_sum(l, r, seg->root);
                ans = ((double)prefix / (double)s) / (double)k + (double)(su - prefix) / (double)k;
            }
            printf("%.3f\n", ans);
        }
    }
    free(seg);
    delete []a;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //------------------------------------------------------
    // int t = 1;
    //    cin >> t;
    // while (t--)solve();
    solve();
}

需要分类讨论下区间刚好 $k$ 个数的话就直接取区间和了，否则查找时则是查找第 $0$ 大的 $1 \sim kth $ 之和。好吧，我也不知道之前写的啥了，具体而言，外层线段树维护区间限制，内存要么权值线段树要么平衡树找第 $k$ 大，早期那时候不会求 $1 \sim kth$ 之和还幻想着要不(内层套个平衡树和权值线段树共存，阿巴阿巴。还上了点暴力emmmm。如果正儿八经实现这种做法应该这样做：外层区间线段树，内存平衡树不仅维护 $value$ 同时维护 $sum$，例如 $FHQ$ 平衡树就能在确定这个 $\le val$ 的节点数量的同时还能拿到 $1 \sim kth$ 之和。这样一来正儿八经的： $$ \text{时间复杂度为}O(n\log^3{n}) $$

正解栏目

解法一

原本没有这个解法的，这个解法写起来比较逆天。然后申请调大了下时间限制 AC了，理想下确实应该写出来给大家借鉴的。

这是一种非传统的求区间第 $k$ 的方法

出处：区间 rank 的 N 种解法，你都会了吗

具体而言，如图所说的。大致解释下算法思路：我们首先需要离散化值域（减小常数大小，尤其是树套树之类的东西很有必要）。具体而言是一个外层权值线段树内存套一个有序序列。对于一个权值线段树的有序序列而言，它的实际意义为：

$ [l,r] \text{值域上包括的下标序列}$，这样一来对于某个值域我们可以二分出这个值域内满足它们的下标序列在待查找的区间 $[L,R]$ 的个数。知道了这个，我们就可以线段树上二分出 $th$ 了。具体 P3834 【模板】可持久化线段树 2 参照代码：

参照代码

#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast,unroll-loops")

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (typeid(x) == typeid(char))return;
    if (x < 0)x = -x, putchar('-');
    if (x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}


template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow)return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3() { one = tow = three = 0; }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y)x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y)x = y;
}

constexpr int N = 2e5 + 10;
int a[N], b[N];
int n, q;
hash2<int, int> mp;
int mx;

vector<int> order[N << 2];
vector<int> init[N];
#define tr(x) order[x]

inline void build(const int curr, const int l, const int r)
{
    if (l == r)
    {
        tr(curr) = init[l];
        return;
    }
    const int mid = (l + r) >> 1;
    build(ls(curr), l, mid);
    build(rs(curr), mid + 1, r);
    int i = 0, j = 0;
    while (i < tr(ls(curr)).size() and j < tr(rs(curr)).size())
    {
        if (tr(ls(curr))[i] < tr(rs(curr))[j])
            tr(curr).push_back(tr(ls(curr))[i++]);
        else
            tr(curr).push_back(tr(rs(curr))[j++]);
    }
    while (i < tr(ls(curr)).size())
        tr(curr).push_back(tr(ls(curr))[i++]);
    while (j < tr(rs(curr)).size())
        tr(curr).push_back(tr(rs(curr))[j++]);
}

inline int query(const int curr, const int s, const int e, const int l, const int r, const int k)
{
    if (s == e)return b[s];
    int leftCnt = ranges::upper_bound(all(tr(ls(curr))), r) - ranges::upper_bound(all(tr(ls(curr))), l - 1);
    const int mid = (s + e) >> 1;
    if (leftCnt >= k)return query(ls(curr), s, mid, l, r, k);
    return query(rs(curr), mid + 1, e, l, r, k - leftCnt);
}

inline void solve()
{
    cin >> n >> q;
    forn(i, 1, n)cin >> a[i], b[i] = a[i];
    sortArr(b, n);
    mx = disc(b, n);
    forn(i, 1, mx)mp[b[i]] = i;
    forn(i, 1, n)init[mp[a[i]]].push_back(i);
    build(1, 1, mx);
    while (q--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        cout << query(1, 1, mx, l, r, k) << endl;
    }
}

signed int main()
{
    Spider
    //------------------------------------------------------
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test)solve();
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
}

稍微做了一点常数优化，就是两个有序序列合并我们可以使用类似归并排序的双指针方式进行合并。非常舒服。
来讲讲解法一如何让上述的东西改成可以正儿八经地支持我们需要的东西。很显然最终的答案为：权值线段树套文艺平衡树即可。
具体的，权值线段树用于二分答案，文艺平衡树我们可以考虑维护基本的查找 $val$ 是第几大的数的功能，同时维护一下 $sum$ 即可。

暴力建树

#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC optimize(2)

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (typeid(x) == typeid(char))return;
    if (x < 0)x = -x, putchar('-');
    if (x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}


template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow)return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3() { one = tow = three = 0; }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y)x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y)x = y;
}

constexpr int N = 4e5 + 10;

int a[N];
int n, q;
int mp[N];
int mx;

struct FHQ
{
    int siz;
    ll sum;
    int val;
    int rnk;
    int child[2];
} fhq[N * 50];

#define siz(x) fhq[x].siz
#define left(x) fhq[x].child[0]
#define right(x) fhq[x].child[1]
#define rnk(x) fhq[x].rnk
#define sum(x) fhq[x].sum
#define val(x) fhq[x].val
int cnt;
int st[N << 2], stCnt;

inline int newID()
{
    if (stCnt)return st[stCnt--];
    return ++cnt;
}

inline int newNode(const int val)
{
    int curr = newID();
    rnk(curr) = Rand(1,INT_MAX);
    siz(curr) = 1;
    left(curr) = right(curr) = 0;
    val(curr) = val;
    sum(curr) = a[val];
    return curr;
}

inline void push_up(const int curr)
{
    sum(curr) = sum(left(curr)) + sum(right(curr)) + a[val(curr)];
    siz(curr) = siz(left(curr)) + siz(right(curr)) + 1;
}


inline int merge(const int x, const int y)
{
    if (!x or !y)return x ^ y;
    if (rnk(x) < rnk(y))
    {
        right(x) = merge(right(x), y);
        push_up(x);
        return x;
    }
    left(y) = merge(x,left(y));
    push_up(y);
    return y;
}

inline void split(const int curr, const int val, int& x, int& y)
{
    if (!curr)
    {
        x = 0, y = 0;
        return;
    }
    if (val(curr) <= val)x = curr, split(right(curr), val,right(curr), y);
    else y = curr, split(left(curr), val, x,left(curr));
    push_up(curr);
}

inline void add(int& root, const int val)
{
    int l = 0, r = 0;
    split(root, val, l, r);
    root = merge(merge(l, newNode(val)), r);
}

void del(int& root, const int val)
{
    int lTree = 0, rTree = 0;
    split(root, val, lTree, rTree);;
    int l = 0, r = 0;
    split(lTree, val - 1, l, r);
    st[++stCnt] = r;
    root = merge(lTree = merge(l, r = 0), rTree);
}

inline pll query(int& root, const int L, const int R)
{
    int l1 = 0, r1 = 0;
    split(root, R, l1, r1);
    int l2 = 0, r2 = 0;
    split(l1, L, l2, r2);
    int siz = siz(r2);
    ll sum = sum(r2);
    root = merge(l1 = merge(l2, r2), r1);
    return pll(siz, sum);
}

vector<int> init[N];

struct SegNode
{
    int tree;
} node[N << 2];

#define root(x) node[x].tree

inline void build(const int curr, const int l, const int r)
{
    forn(i, l, r) for (const auto v : init[i])add(root(curr), v);
    const int mid = l + r >> 1;
    if (l == r)return;
    build(ls(curr), l, mid);
    build(rs(curr), mid + 1, r);
}

inline ll query(const int curr, const int s, const int e, const int l, const int r, const int k)
{
    if (s == e)return mp[s] * ll(k);
    auto [leftCnt,sum] = query(root(ls(curr)), l - 1, r);
    const int mid = s + e >> 1;
    if (leftCnt >= k)return query(ls(curr), s, mid, l, r, k);
    return query(rs(curr), mid + 1, e, l, r, k - leftCnt) + sum;
}

inline void update(const int curr, const int l, const int r, const int pos, const int val)
{
    if (val < 0)
        del(root(curr), -val);
    else
        add(root(curr), val);
    if (l == r)return;
    if (const int mid = l + r >> 1; pos <= mid)update(ls(curr), l, mid, pos, val);
    else update(rs(curr), mid + 1, r, pos, val);
}

int siz;

struct Query
{
    int op;
    int l, r, pos, val;
    int k;
} qu[N];

hash2<int, int> idx;

inline void solve()
{
    // MyFile
    read(n);
    forn(i, 1, n)read(a[i]), mp[++siz] = a[i];
    read(q);
    forn(i, 1, q)
    {
        read(qu[i].op);
        if (qu[i].op == 1)
        {
            read(qu[i].pos, qu[i].val);
            mp[++siz] = qu[i].val;
        }
        else
        {
            read(qu[i].l, qu[i].r, qu[i].k);
        }
    }
    sortArr(mp, siz);
    mx = disc(mp, siz);
    forn(i, 1, mx)idx[mp[i]] = i;
    forn(i, 1, n)init[idx[a[i]]].push_back(i);
    build(1, 1, mx);
    forn(i, 1, q)
    {
        if (qu[i].op == 1)
        {
            update(1, 1, mx, idx[a[qu[i].pos]], -qu[i].pos);
            update(1, 1, mx, idx[a[qu[i].pos] = qu[i].val], qu[i].pos);
        }
        else
        {
            int l = qu[i].l, r = qu[i].r, k = qu[i].k;
            int d = r - l + 1;
            ld ans;
            if (d == k)ans = static_cast<ld>(query(1, 1, mx, l, r, r - l + 1)) / k;
            else
            {
                int need = d - (k - 1);
                auto t1 = query(1, 1, mx, l, r, need);
                auto t2 = query(1, 1, mx, l, r, r - l + 1);
                ans = (t2 - t1 + static_cast<ld>(t1) / need) / k;
            }
            cout << fixed << setprecision(3) << ans << endl;
        }
    }
}

signed int main()
{
    Spider
    //------------------------------------------------------
    // clock_t start = clock();
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test)solve();
    // clock_t end = clock();
    // cerr << "time = " << double(end - start) / CLOCKS_PER_SEC << "s" << endl; //输出时间
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
}

归并合并有序序列以后类似笛卡尔树建树优化

#include <bits/stdc++.h>

// #pragma GCC target("sse3","sse2","sse","avx","sse4","sse4.1","sse4.2","ssse3","f16c")
// #pragma GCC diagnostic error "-fwhole-program","-fcse-skip-blocks","-funsafe-loop-optimizations","-std=c++20"
//#pragma GCC optimize("Ofast,unroll-loops")

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (typeid(x) == typeid(char))return;
    if (x < 0)x = -x, putchar('-');
    if (x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}


template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow)return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3() { one = tow = three = 0; }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y)x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y)x = y;
}

constexpr int N = 4e5 + 10;

int a[N];
int n, q;
int mp[N];
int mx;

struct FHQ
{
    int siz;
    ll sum;
    int val;
    int rnk;
    int child[2];
} fhq[N * 50];

#define siz(x) fhq[x].siz
#define left(x) fhq[x].child[0]
#define right(x) fhq[x].child[1]
#define rnk(x) fhq[x].rnk
#define sum(x) fhq[x].sum
#define val(x) fhq[x].val
int cnt;
int st[N << 2], stCnt;

inline int newID()
{
    if (stCnt)return st[stCnt--];
    return ++cnt;
}

inline int newNode(const int val)
{
    int curr = newID();
    rnk(curr) = Rand(1,INT_MAX);
    siz(curr) = 1;
    left(curr) = right(curr) = 0;
    val(curr) = val;
    sum(curr) = a[val];
    return curr;
}

inline void push_up(const int curr)
{
    sum(curr) = sum(left(curr)) + sum(right(curr)) + a[val(curr)];
    siz(curr) = siz(left(curr)) + siz(right(curr)) + 1;
}


inline int merge(const int x, const int y)
{
    if (!x or !y)return x ^ y;
    if (rnk(x) < rnk(y))
    {
        right(x) = merge(right(x), y);
        push_up(x);
        return x;
    }
    left(y) = merge(x,left(y));
    push_up(y);
    return y;
}

inline void split(const int curr, const int val, int& x, int& y)
{
    if (!curr)
    {
        x = 0, y = 0;
        return;
    }
    if (val(curr) <= val)x = curr, split(right(curr), val,right(curr), y);
    else y = curr, split(left(curr), val, x,left(curr));
    push_up(curr);
}

inline void add(int& root, const int val)
{
    int l = 0, r = 0;
    split(root, val, l, r);
    root = merge(merge(l, newNode(val)), r);
}

void del(int& root, const int val)
{
    int lTree = 0, rTree = 0;
    split(root, val, lTree, rTree);;
    int l = 0, r = 0;
    split(lTree, val - 1, l, r);
    st[++stCnt] = r;
    root = merge(lTree = merge(l, r = 0), rTree);
}

inline pll query(int& root, const int L, const int R)
{
    int l1 = 0, r1 = 0;
    split(root, R, l1, r1);
    int l2 = 0, r2 = 0;
    split(l1, L, l2, r2);
    int siz = siz(r2);
    ll sum = sum(r2);
    root = merge(l1 = merge(l2, r2), r1);
    return pll(siz, sum);
}

vector<int> init[N];

struct SegNode
{
    int tree;
    vector<int> order;
} node[N << 2];

#define root(x) node[x].tree
#define tr(x) node[x].order

inline void Merge(const int curr)
{
    if (!tr(ls(curr)).size())
    {
        swap(tr(curr),tr(rs(curr)));
        return;
    }
    if (!tr(rs(curr)).size())
    {
        swap(tr(curr),tr(ls(curr)));
        return;
    }
    if (tr(ls(curr)).back() < tr(rs(curr)).front())
    {
        swap(tr(curr),tr(ls(curr)));
        tr(curr).insert(tr(curr).end(),all(tr(rs(curr))));
        return;
    }
    int i = 0, j = 0;
    while (i < tr(ls(curr)).size() and j < tr(rs(curr)).size())
    {
        if (tr(ls(curr))[i] < tr(rs(curr))[j])
            tr(curr).push_back(tr(ls(curr))[i++]);
        else
            tr(curr).push_back(tr(rs(curr))[j++]);
    }
    while (i < tr(ls(curr)).size())
        tr(curr).push_back(tr(ls(curr))[i++]);
    while (j < tr(rs(curr)).size())
        tr(curr).push_back(tr(rs(curr))[j++]);
}

inline void build(const int curr, const int l, const int r)
{
    const int mid = l + r >> 1;
    if (l == r)
    {
        swap(tr(curr), init[l]);
        stack<int> t;
        for (auto v : tr(curr))
        {
            int last = 0;
            int x = newNode(v);
            while (!t.empty() and rnk(t.top()) > rnk(x))push_up(last = t.top()), t.pop();
            if (!t.empty())
                right(t.top()) = x;
            left(x) = last, t.push(x);
        }
        while (!t.empty())
        {
            if (t.size() == 1)
                root(curr) = t.top();
            push_up(t.top()), t.pop();
        }
        return;
    }
    build(ls(curr), l, mid);
    build(rs(curr), mid + 1, r);
    Merge(curr);
    stack<int> t;
    for (auto v : tr(curr))
    {
        int last = 0;
        int x = newNode(v);
        while (!t.empty() and rnk(t.top()) > rnk(x))push_up(last = t.top()), t.pop();
        if (!t.empty())
            right(t.top()) = x;
        left(x) = last, t.push(x);
    }
    while (!t.empty())
    {
        if (t.size() == 1)
            root(curr) = t.top();
        push_up(t.top()), t.pop();
    }
}

inline ll query(const int curr, const int s, const int e, const int l, const int r, const int k)
{
    if (s == e)return mp[s] * ll(k);
    auto [leftCnt,sum] = query(root(ls(curr)), l - 1, r);
    const int mid = s + e >> 1;
    if (leftCnt >= k)return query(ls(curr), s, mid, l, r, k);
    return query(rs(curr), mid + 1, e, l, r, k - leftCnt) + sum;
}

inline void update(const int curr, const int l, const int r, const int pos, const int val)
{
    if (val < 0)
        del(root(curr), -val);
    else
        add(root(curr), val);
    if (l == r)return;
    if (const int mid = l + r >> 1; pos <= mid)update(ls(curr), l, mid, pos, val);
    else update(rs(curr), mid + 1, r, pos, val);
}

int siz;

struct Query
{
    int op;
    int l, r, pos, val;
    int k;
} qu[N];

hash2<int, int> idx;

inline void solve()
{
    // MyFile
    read(n);
    forn(i, 1, n)read(a[i]), mp[++siz] = a[i];
    read(q);
    forn(i, 1, q)
    {
        read(qu[i].op);
        if (qu[i].op == 1)
        {
            read(qu[i].pos, qu[i].val);
            mp[++siz] = qu[i].val;
        }
        else
        {
            read(qu[i].l, qu[i].r, qu[i].k);
        }
    }
    sortArr(mp, siz);
    mx = disc(mp, siz);
    forn(i, 1, mx)idx[mp[i]] = i;
    forn(i, 1, n)init[idx[a[i]]].push_back(i);
    build(1, 1, mx);
    forn(i, 1, q)
    {
        if (qu[i].op == 1)
        {
            update(1, 1, mx, idx[a[qu[i].pos]], -qu[i].pos);
            update(1, 1, mx, idx[a[qu[i].pos] = qu[i].val], qu[i].pos);
        }
        else
        {
            int l = qu[i].l, r = qu[i].r, k = qu[i].k;
            int d = r - l + 1;
            ld ans;
            if (d == k)ans = static_cast<ld>(query(1, 1, mx, l, r, r - l + 1)) / k;
            else
            {
                int need = d - (k - 1);
                auto t1 = query(1, 1, mx, l, r, need);
                auto t2 = query(1, 1, mx, l, r, r - l + 1);
                ans = (t2 - t1 + static_cast<ld>(t1) / need) / k;
            }
            cout << fixed << setprecision(3) << ans << endl;
        }
    }
}

signed int main()
{
    Spider
    //------------------------------------------------------
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test)solve();
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
}

常数很大的一种解法,可能需要卡点常。简单分析下复杂度。建树显然根据不同的建法有不同的复杂度，但都不会超过双 $\log$，其实就跟线段树套平衡树差不多，只是用的不再是区间线段树而是权值线段树，平衡树则是用的文艺平衡树，和常规的区间线段树套权值平衡树而言对换了功能。修改的复杂度显然每次回修改 $\log{n}$ 个节点，每个节点一次平衡树修改又是 $\log{n}$。查询线段树上二分+二分的check需要一次平衡树查询，所以修改和查找的单次复杂度都为 $O(\log^2{n})$

\[ \text{最终期望复杂度为：大常数的} O(n\log^2{n}) \]

空间复杂度是非常优秀的，因为采用了文艺平衡树替代了常见的权值线段树功能，空间一下子就小了很多。当然代码也给出了空间优化的常见方式，回收删除标记，复用为下次新节点标记。

解法二

也是我没事瞎捉摸的一种解法。时间常数较为不错。回到第一个问题，传统区间线段树套权值线段树有木有 $\log^2{n}$ 级别查找第 $k$ 大数的方法。有一种神奇的做法----优雅的暴力。把涉及到查询的区间对应的权值树的根统统拿出来，然后跑一次一堆节点的二分，其实跟BIT套权值树已经很类似了，但二者还是有部分区别，一个是基于区间思想，一个是借助主席树的设计思想，利用前缀和去维护。

很显然的是涉及到待查询的区间节点数量为 $\log{n}$ 个，每次 check 就是将这些节点的左子树的权值贡献合并起来，和主席树其实是一致的。外层就是主席树上二分。空间复杂度显然巨大：

小空间优化参照代码

#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast,unroll-loops")

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (x == ' ' or x == endl)return;
    if (x < 0)x = -x, putchar('-');
    if (x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}


template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow)return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3() { one = tow = three = 0; }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y)x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y)x = y;
}

constexpr int N = 4e5 + 10;
int cnt;
int mp[N];
int a[N];

struct In
{
    int left, right;
    int cnt;
    ll sum;
} in[N * 200];

int mx;
#define left(x) in[x].left
#define right(x) in[x].right
#define cnt(x) in[x].cnt
#define sum(x) in[x].sum

int del[N * 20];
int d;

inline void clear(int& curr)
{
    if (left(curr))del[++d] = left(curr), left(curr) = 0;
    if (right(curr))del[++d] = right(curr), right(curr) = 0;
    del[++d] = curr, curr = 0;
}

inline int newNode()
{
    if (d)return del[d--];
    return ++cnt;
}

inline void push_up(int& curr)
{
    cnt(curr) = cnt(left(curr)) + cnt(right(curr));
    sum(curr) = sum(left(curr)) + sum(right(curr));
    if (!cnt(curr))clear(curr);
}

inline void addIn(int& curr, const int l, const int r, const int pos, const int val)
{
    if (!curr)curr = newNode();
    if (l == r)
    {
        cnt(curr) += val;
        sum(curr) += mp[pos] * val;
        if (!cnt(curr))clear(curr);
        return;
    }
    const int mid = l + r >> 1;
    if (pos <= mid)addIn(left(curr), l, mid, pos, val);
    else addIn(right(curr), mid + 1, r, pos, val);
    push_up(curr);
}

struct Out
{
    int root;
} out[N << 2];

#define root(x) out[x].root
#define vis(x) out[x].vis
#define lazy(x) out[x].lazy

inline void addOut(const int curr, const int l, const int r, const int outPos, const int inPos, const int val)
{
    if (val < 0)addIn(root(curr), 1, mx, inPos, -1);
    else addIn(root(curr), 1, mx, inPos, 1);
    if (l == r)return;
    const int mid = l + r >> 1;
    if (outPos <= mid)addOut(ls(curr), l, mid, outPos, inPos, val);
    else addOut(rs(curr), mid + 1, r, outPos, inPos, val);
}

vector<int> kthQ;

inline void queryKth(const int curr, const int l, const int r, const int s, const int e)
{
    const int mid = s + e >> 1;
    if (l <= s and e <= r)
    {
        kthQ.push_back(root(curr));
        return;
    }
    if (l <= mid)queryKth(ls(curr), l, r, s, mid);
    if (r > mid)queryKth(rs(curr), l, r, mid + 1, e);
}


inline void build(const int curr, const int l, const int r)
{
    forn(i, l, r)
        addIn(root(curr), 1, mx, a[i], 1);
    if (l == r)return;
    const int mid = (l + r) >> 1;
    build(ls(curr), l, mid);
    build(rs(curr), mid + 1, r);
}

int n, q;

inline ll queryAns(const int l, const int r, const int k)
{
    if (l == r)return mp[l] * ll(k);
    int sum = 0;
    ll leftSum = 0;
    for (auto root : kthQ)sum += cnt(left(root)), leftSum += sum(left(root));
    const int mid = (l + r) >> 1;
    if (sum >= k)
    {
        for (auto& x : kthQ)x = left(x);
        return queryAns(l, mid, k);
    }
    for (auto& x : kthQ)x = right(x);
    return queryAns(mid + 1, r, k - sum) + leftSum;
}

struct Query
{
    int l, r, k;
} qu[N];

int siz;
hash2<int, int> idx;

inline void solve()
{
    // MyFile
    cin >> n;
    forn(i, 1, n)cin >> a[i], mp[++siz] = a[i];
    cin >> q;
    forn(i, 1, q)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            cin >> qu[i].l >> qu[i].r;
            mp[++siz] = qu[i].r;
        }
        else
        {
            cin >> qu[i].l >> qu[i].r >> qu[i].k;
        }
    }
    sortArr(mp, siz);
    mx = disc(mp, siz);
    forn(i, 1, mx)idx[mp[i]] = i;
    forn(i, 1, n)a[i] = idx[a[i]];
    build(1, 1, n);
    forn(i, 1, q)
    {
        if (qu[i].k == 0)
        {
            int pos = qu[i].l, val = qu[i].r;
            addOut(1, 1, n, pos, a[pos], -1);
            addOut(1, 1, n, pos, a[pos] = idx[val], 1);
        }
        else
        {
            int l = qu[i].l, r = qu[i].r, k = qu[i].k;
            int d = r - l + 1;
            ld ans;
            kthQ.clear();
            queryKth(1, l, r, 1, n);
            auto tmp = kthQ;
            if (d == k)
            {
                ans = static_cast<ld>(queryAns(1, mx, r - l + 1)) / k;
            }
            else
            {
                int need = d - (k - 1);
                auto t1 = queryAns(1, mx, need);
                kthQ = tmp;
                auto t2 = queryAns(1, mx, r - l + 1);
                ans = (t2 - t1 + static_cast<ld>(t1) / need) / k;
            }
            cout << fixed << setprecision(3) << ans << endl;
        }
    }
}

signed int main()
{
    Spider
    //------------------------------------------------------
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test)solve();
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
}

我们注意到每次查询和修改涉及的区间不多，如果全部 build 完是常数巨大的，所以我们可以考虑维护 lazy 待插入队列进行优化。

大时间优化代码

#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast,unroll-loops")

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (x == ' ' or x == endl)return;
    if (x < 0)x = -x, putchar('-');
    if (x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}


template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow)return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3() { one = tow = three = 0; }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y)x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y)x = y;
}

constexpr int N = 2e5 + 10;
int cnt;
int mp[N << 1];
int a[N];

struct In
{
    int left, right;
    int cnt;
    ll sum;
} in[N * 200];

int mx;
#define left(x) in[x].left
#define right(x) in[x].right
#define cnt(x) in[x].cnt
#define sum(x) in[x].sum

int del[N];
int d;

inline void clear(int& curr)
{
    if (left(curr))del[++d] = left(curr), left(curr) = 0;
    if (right(curr))del[++d] = right(curr), right(curr) = 0;
    del[++d] = curr, curr = 0;
}

inline int newNode()
{
    if (d)return del[d--];
    return ++cnt;
}

inline void push_up(int& curr)
{
    cnt(curr) = cnt(left(curr)) + cnt(right(curr));
    sum(curr) = sum(left(curr)) + sum(right(curr));
    if (!cnt(curr))clear(curr);
}

inline void addIn(int& curr, const int l, const int r, const int pos, const int val)
{
    if (!curr)curr = newNode();
    if (l == r)
    {
        cnt(curr) += val;
        sum(curr) += mp[pos] * val;
        if (!cnt(curr))clear(curr);
        return;
    }
    const int mid = l + r >> 1;
    if (pos <= mid)addIn(left(curr), l, mid, pos, val);
    else addIn(right(curr), mid + 1, r, pos, val);
    push_up(curr);
}

struct Out
{
    int root;
    vector<int> lazy;
} out[N << 2];

#define root(x) out[x].root
#define vis(x) out[x].vis
#define lazy(x) out[x].lazy

inline void addOut(const int curr, const int l, const int r, const int outPos, const int inPos, const int val)
{
    lazy(curr).push_back(inPos * val);
    if (l == r)return;
    const int mid = (l + r) >> 1;
    if (outPos <= mid)addOut(ls(curr), l, mid, outPos, inPos, val);
    else addOut(rs(curr), mid + 1, r, outPos, inPos, val);
}

vector<int> kthQ;

inline void queryKth(const int curr, const int l, const int r, const int s, const int e)
{
    const int mid = s + e >> 1;
    if (l <= s and e <= r)
    {
        for (auto t : lazy(curr))
        {
            if (t < 0)addIn(root(curr), 1, mx, -t, -1);
            else addIn(root(curr), 1, mx, t, 1);
        }
        lazy(curr).clear();
        kthQ.push_back(root(curr));
        return;
    }
    if (l <= mid)queryKth(ls(curr), l, r, s, mid);
    if (r > mid)queryKth(rs(curr), l, r, mid + 1, e);
}


inline void build(const int curr, const int l, const int r)
{
    forn(i, l, r)
        lazy(curr).push_back(a[i]);
    if (l == r)return;
    const int mid = (l + r) >> 1;
    build(ls(curr), l, mid);
    build(rs(curr), mid + 1, r);
}

int n, q;

inline ll queryAns(const int l, const int r, const int k)
{
    if (l == r)return mp[l] * ll(k);
    int sum = 0;
    ll leftSum = 0;
    for (auto root : kthQ)sum += cnt(left(root)), leftSum += sum(left(root));
    const int mid = (l + r) >> 1;
    if (sum >= k)
    {
        for (auto& x : kthQ)x = left(x);
        return queryAns(l, mid, k);
    }
    for (auto& x : kthQ)x = right(x);
    return queryAns(mid + 1, r, k - sum) + leftSum;
}

struct Query
{
    int l, r, k;
} qu[N];

int siz;
hash2<int, int> idx;

inline void solve()
{
    // MyFile
    cin >> n;
    forn(i, 1, n)cin >> a[i], mp[++siz] = a[i];
    cin >> q;
    forn(i, 1, q)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            cin >> qu[i].l >> qu[i].r;
            mp[++siz] = qu[i].r;
        }
        else
        {
            cin >> qu[i].l >> qu[i].r >> qu[i].k;
        }
    }
    sortArr(mp, siz);
    mx = disc(mp, siz);
    forn(i, 1, mx)idx[mp[i]] = i;
    forn(i, 1, n)a[i] = idx[a[i]];
    build(1, 1, n);
    forn(i, 1, q)
    {
        if (qu[i].k == 0)
        {
            int pos = qu[i].l, val = qu[i].r;
            addOut(1, 1, n, pos, a[pos], -1);
            addOut(1, 1, n, pos, a[pos] = idx[val], 1);
        }
        else
        {
            int l = qu[i].l, r = qu[i].r, k = qu[i].k;
            int d = r - l + 1;
            ld ans;
            kthQ.clear();
            queryKth(1, l, r, 1, n);
            auto tmp = kthQ;
            if (d == k)
            {
                ans = static_cast<ld>(queryAns(1, mx, r - l + 1)) / k;
            }
            else
            {
                int need = d - (k - 1);
                kthQ = tmp;
                auto t1 = queryAns(1, mx, need);
                kthQ = tmp;
                auto t2 = queryAns(1, mx, r - l + 1);
                ans = (t2 - t1 + static_cast<ld>(t1) / need) / k;
            }
            cout << fixed << setprecision(3) << ans << endl;
        }
    }
}

signed int main()
{
    Spider
    //------------------------------------------------------
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test)solve();
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
}

\[ \text{显而易见的是总复杂度为小常数的 } O(n\log^2{n}) \]

解法三

最好想的正解，也是绝大部分人应该想到的经典解

前置知识点: P2617 Dynamic Rankings

需要会这题的标准动态第 $k$ 大解法。
实际上就是解法二的优化思想。树状数组套权值线段树，然后正常维护动态第 $k$ 大的信息就行了。好像没啥可说的，具体的可以看那道题的一些题解理解。每次修改 $\log{n}$ 个树状数组的节点所对应的权值线段树即可。

空间优化后的参考代码

#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast,unroll-loops")

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (x == ' ' or x == endl)return;
    if (x < 0)x = -x, putchar('-');
    if (x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}


template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow)return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3() { one = tow = three = 0; }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y)x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y)x = y;
}

constexpr int N = 2e5 + 10;

struct Node
{
    int cnt;
    ll sum;
    int left, right;
} node[N << 7];

#define lll node[curr].left
#define rrr node[curr].right
#define sum(x) node[x].sum
#define cnt(x) node[x].cnt
int tot;
int a[N];
ll mp[N << 1];
hash2<int, int> idx;
int st[N << 5], stCnt;

inline void push_up(int& curr)
{
    sum(curr) = sum(lll) + sum(rrr);
    cnt(curr) = cnt(lll) + cnt(rrr);
    if (!cnt(curr))
        lll = rrr = 0, st[++stCnt] = curr, curr = 0;
}


inline int newNode()
{
    if (stCnt)return st[stCnt--];
    return ++tot;
}

inline void add(int& curr, const int l, const int r, const int pos, const int siz)
{
    if (!curr)curr = newNode();
    if (l == r)
    {
        cnt(curr) += siz;
        sum(curr) += siz * mp[l];
        if (!cnt(curr))st[++stCnt] = curr, curr = 0;
        return;
    }
    const int mid = (l + r) >> 1;
    if (pos <= mid)add(lll, l, mid, pos, siz);
    else add(rrr, mid + 1, r, pos, siz);
    push_up(curr);
}

inline ll query(vector<int>& left, vector<int>& right, const int l, const int r, int k)
{
    const int mid = (l + r) >> 1;
    if (l == r)return k * mp[l];
    int left_cnt = 0, right_cnt = 0;
    ll left_sum = 0, right_sum = 0;
    for (const auto curr : left)left_cnt += cnt(lll), left_sum += sum(lll);
    for (const auto curr : right)right_cnt += cnt(lll), right_sum += sum(lll);
    if (right_cnt - left_cnt >= k)
    {
        for (auto& x : left)x = node[x].left;
        for (auto& x : right)x = node[x].left;
        return query(left, right, l, mid, k);
    }
    k -= (right_cnt - left_cnt);
    for (auto& x : left)x = node[x].right;
    for (auto& x : right)x = node[x].right;
    return query(left, right, mid + 1, r, k) + right_sum - left_sum;
}

int n;
int root[N];
int mx;

inline void update(const int pos, const int val, const int siz)
{
    for (int x = pos; x <= n; x += lowBit(x))add(root[x], 1, mx, val, siz);
}

inline ll query(const int l, const int r, const int k)
{
    vector<int> left, right;
    for (int x = l - 1; x; x -= lowBit(x))left.push_back(root[x]);
    for (int x = r; x; x -= lowBit(x))right.push_back(root[x]);
    return query(left, right, 1, mx, k);
}

int q;

struct Query
{
    int op;
    int l, r, pos, val;
    int k;
} qu[N];

int siz;

inline void solve()
{
    // MyFile
    cin >> n;
    forn(i, 1, n)cin >> a[i], mp[++siz] = a[i];
    cin >> q;
    forn(i, 1, q)
    {
        cin >> qu[i].op;
        if (qu[i].op == 1)
        {
            cin >> qu[i].pos >> qu[i].val;
            mp[++siz] = qu[i].val;
        }
        else
        {
            cin >> qu[i].l >> qu[i].r >> qu[i].k;
        }
    }
    sortArr(mp, siz);
    mx = disc(mp, siz);
    forn(i, 1, mx)idx[mp[i]] = i;
    forn(i, 1, n)a[i] = idx[a[i]];
    forn(i, 1, n)update(i, a[i], 1);
    forn(i, 1, q)
    {
        if (qu[i].op == 1)
        {
            update(qu[i].pos, a[qu[i].pos], -1);
            a[qu[i].pos] = idx[qu[i].val];
            update(qu[i].pos, a[qu[i].pos], 1);
        }
        else
        {
            int l = qu[i].l, r = qu[i].r, k = qu[i].k;
            int d = r - l + 1;
            ld ans;
            if (d == k)
            {
                ans = static_cast<ld>(query(l, r, r - l + 1)) / k;
            }
            else
            {
                ll need = d - (k - 1);
                auto t1 = query(l, r, need);
                auto t2 = query(l, r, r - l + 1);
                ans = (t2 - t1 + static_cast<ld>(t1) / need) / k;
            }
            cout << fixed << setprecision(3) << ans << endl;
        }
    }
}

signed int main()
{
    Spider
    //------------------------------------------------------
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test)solve();
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
}

\[ \text{显而易见的是总复杂度为 } O(n\log^2{n}) \]

解法四

前置知识点：P4119 [Ynoi2018] 未来日记

当然是神仙分块了，在第一分块中提到的，只需要序列分块套值域分块就行了。具体的我们对原序列进行分块，然后对于整个值域也进行分块操作。需要维护几个前缀和：

1.每个区间块中每个值域块的前缀和信息（数量与和）
2.每个区间块中值域单点前缀和信息（同上，单点可以不用维护和，因为直接数量*点值即可）

考虑修改操作，找到点对应的区间块，类似树状数组一样，开始从这个块往后更新新的前缀和信息。复杂度 $O(\sqrt{n})$。其实完全可以类比树状数组

考虑查询操作，类似解法二，对值域块进行类似二分的过程，如果区间同一个块，暴力使用库函数 nth_element 即可。如果跨块，记录散块单点信息：

第一个桶记录散块对应的值域块数量情况
第二个桶记录单点数量
第三个桶记录散块对应的值域块的和

开始查找第 $k$ 大。逐个逐个值域判断，利用前缀和做差，轻松拿到在某个值域块上 $[l,r]$ 区间的符合数量。其实这不就是解法一的思路吗？二分到正确的值域块以后，再暴力枚举判断单点类似二分的形式。这样一来复杂度为 $ O(2 \times \sqrt{n})$ 相当地优秀。

参考代码

#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast,unroll-loops")

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (x == ' ' or x == endl)return;
    if (x < 0)x = -x, putchar('-');
    if (x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}

template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow)return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3() { one = tow = three = 0; }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y)x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y)x = y;
}

constexpr int N = 4e5 + 10;
constexpr int MX = sqrt(N);
constexpr int CNT = (N + MX - 1) / MX;
pair<int, ll> pre[CNT + 1][CNT + 1];
int siz, cnt;
int n;
int a[N / 2], mp[N];
hash2<int, int> idx;
int preCnt[CNT + 1][N / 2];
int pos[N], s[CNT + 1], e[CNT + 1];

struct Query
{
    int op;
    int l, r, pos, val;
    int k;
} qu[N];

int mx;
int q;

inline void update(const int curr, const int p, const int val)
{
    int valPos = pos[p];
    int blockPos = pos[curr];
    forn(i, blockPos, cnt)
    {
        pre[i][valPos].first += val;
        pre[i][valPos].second += val * mp[p];
        preCnt[i][p] += val;
    }
}

int tmp[MX + 1];
int c1[N / 2], c2[N / 2];
ll c3[N / 2];

inline ll query(const int l, const int r, ll k)
{
    const int L = pos[l], R = pos[r];
    if (L == R)
    {
        int i = 0;
        forn(j, l, r)tmp[++i] = a[j];
        nth_element(tmp + 1, tmp + k, tmp + i + 1);
        ll ans = 0;
        forn(j, 1, k)ans += mp[tmp[j]];
        return ans;
    }
    forn(i, l, e[L])c1[pos[a[i]]]++, c2[a[i]]++, c3[pos[a[i]]] += mp[a[i]];
    forn(i, s[R], r)c1[pos[a[i]]]++, c2[a[i]]++, c3[pos[a[i]]] += mp[a[i]];
    ll ans = 0;
    forn(i, 1, pos[N-1])
    {
        if (int valCnt = c1[i] + pre[R - 1][i].first - pre[L][i].first; valCnt >= k)
        {
            forn(j, (i-1)*siz+1, i*siz)
            {
                int point_cnt = c2[j] + preCnt[R - 1][j] - preCnt[L][j];
                if (point_cnt >= k)
                {
                    forn(t, l, e[L])c1[pos[a[t]]]--, c2[a[t]]--, c3[pos[a[t]]] -= mp[a[t]];
                    forn(t, s[R], r)c1[pos[a[t]]]--, c2[a[t]]--, c3[pos[a[t]]] -= mp[a[t]];
                    return ans + k * mp[j];
                }
                k -= point_cnt;
                ans += point_cnt * static_cast<ll>(mp[j]);
            }
        }
        else
        {
            k -= valCnt;
            ans += c3[i] + pre[R - 1][i].second - pre[L][i].second;
        }
    }
    return -1;
}

inline void solve()
{
    // MyFile
    cin >> n;
    forn(i, 1, n)cin >> a[i], mp[++siz] = a[i];
    cin >> q;
    forn(i, 1, q)
    {
        cin >> qu[i].op;
        if (qu[i].op == 1)
        {
            cin >> qu[i].pos >> qu[i].val;
            mp[++siz] = qu[i].val;
        }
        else
        {
            cin >> qu[i].l >> qu[i].r >> qu[i].k;
        }
    }
    sortArr(mp, siz);
    mx = disc(mp, siz);
    forn(i, 1, mx)idx[mp[i]] = i;
    forn(i, 1, n)a[i] = idx[a[i]];
    siz = sqrt(n);
    cnt = (n + siz - 1) / siz;
    forn(i, 1, N-1)pos[i] = (i - 1) / siz + 1;
    forn(i, 1, cnt)s[i] = (i - 1) * siz + 1, e[i] = i * siz;
    e[cnt] = n;
    forn(i, 1, cnt)
    {
        forn(j, 1, CNT)
        {
            pre[i][j].first += pre[i - 1][j].first;
            pre[i][j].second += pre[i - 1][j].second;
        }
        forn(j, 1, N-1)preCnt[i][j] = preCnt[i - 1][j];
        forn(j, s[i], e[i])
        {
            pre[i][pos[a[j]]].first++;
            pre[i][pos[a[j]]].second += mp[a[j]];
            preCnt[i][a[j]]++;
        }
    }
    forn(i, 1, q)
    {
        if (qu[i].op == 1)
        {
            update(qu[i].pos, a[qu[i].pos], -1);
            a[qu[i].pos] = idx[qu[i].val];
            update(qu[i].pos, a[qu[i].pos], 1);
        }
        else
        {
            int l = qu[i].l, r = qu[i].r, k = qu[i].k;
            int d = r - l + 1;
            ld ans = 0.0;
            if (d == k)
            {
                ans = static_cast<ld>(query(l, r, r - l + 1)) / k;
            }
            else
            {
                ll need = d - (k - 1);
                auto t1 = query(l, r, need);
                auto t2 = query(l, r, r - l + 1);
                ans = (t2 - t1 + static_cast<ld>(t1) / need) / k;
            }
            cout << fixed << setprecision(3) << ans << endl;
        }
    }
}

signed int main()
{
    Spider
    //------------------------------------------------------
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test)solve();
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
}

\[ \text{最终总的复杂度显然为 } O(n\sqrt{n}) \]