题目链接

题目描述

BPM=RT

给定正整数 n n n，和非负整数组成的参数序列 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1​,a2​,…,an​ 。
进行 m m m 次操作。
操作包含以下两种：

• 查询速度：给定 l , r , k l,r,k l,r,k，设 S ( x ) = ∑ i = l r max ⁡ ( a i − x , 0 ) S(x) = \sum\limits_{i=l}^r \max(a_i-x,0) S(x)=i=l∑r​max(ai​−x,0)，求 [ 0 , 1 0 5 ] [0,10^5] [0,105] 内满足 S ( x ) ≥ k S(x) \ge k S(x)≥k 的最大的整数 x x x。
• 转发：给定 p , k p,k p,k，将 a p a_p ap​ 修改为 k k k。

输入描述:

第一行，两个正整数 n , m n,m n,m。
第二行， n n n 个非负整数 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1​,a2​,…,an​ 。
以下 m m m 行，每行第一个整数 o p \rm op op 表示操作的类型。

若 o p = 0 {\rm op} = 0 op=0，则接下来有三个整数 l , r , k l,r,k l,r,k，表示一个查询速度操作。
若 o p = 1 {\rm op} = 1 op=1，则接下来有两个整数 p , k p,k p,k，表示一个转发操作。

输出描述:
对于每个查询操作，一行一个整数，表示答案。若在 [ 0 , 1 0 5 ] [0,10^5] [0,105] 内无解，输出 − 1 {-1} −1。
示例1
输入

6 5
4 42 40 26 46 6
0 1 5 20
1 6 4
0 2 6 20
0 2 6 114514
0 1 6 0

输出

36
36
-1
100000

备注:
1 ≤ n , m ≤ 1 0 5 1 \le n,m \le 10^5 1≤n,m≤105 ， 0 ≤ a i ≤ 1 0 5 0 \le a_i \le 10^5 0≤ai​≤105；修改操作满足 1 ≤ p ≤ n 1 \le p \le n 1≤p≤n， 0 ≤ k ≤ 1 0 5 0 \le k \le 10^5 0≤k≤105 ；查询操作满足 1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1≤l≤r≤n， 0 ≤ k ≤ 1 0 10 0 \le k \le 10^{10} 0≤k≤1010 。

如图， S ( x ) S(x) S(x) 本质上就是绿框中的线段长度和 。
看到3s的时限企图用 O ( n m 2 3 log ⁡ 1 0 5 + m log ⁡ 1 0 5 ) O(nm^{\frac{2}{3}}\log10^5+m\log10^5) O(nm32​log105+mlog105) 的带修莫队套权值线段树卡过去，无奈常数过大，线段树上二分合并一个 log ⁡ \log log 也只能过 60 % 60\% 60% 的点。

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

struct Seg_Tree {
    struct T {
        int l, r;
        long long sum, add;
    } t[N << 2];

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l == r)return;
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
    }

    void spread(int p) {
        if (!t[p].add)return;
        t[p << 1].sum += t[p].add * (t[p << 1].r - t[p << 1].l + 1);
        t[p << 1 | 1].sum += t[p].add * (t[p << 1 | 1].r - t[p << 1 | 1].l + 1);
        t[p << 1].add += t[p].add, t[p << 1 | 1].add += t[p].add, t[p].add = 0;
    }

    void change(int p, int x, int v) {
        if (x >= t[p].r)return t[p].add += v, t[p].sum += v * (t[p].r - t[p].l + 1), void();
        spread(p), change(p << 1, x, v);
        if (x > ((t[p].l + t[p].r) >> 1))change(p << 1 | 1, x, v);
        t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
    }

    int ask(int p, long long k, long long s) {
        if (t[p].l == t[p].r)return t[p].l;
        spread(p);
        if (s + t[p << 1 | 1].sum >= k)return ask(p << 1 | 1, k, s);
        return ask(p << 1, k, s + t[p << 1 | 1].sum);
    }
} S;

struct MODUI {
    int n, m, len, a[N], ans[N], u[N], v[N];

    struct Q {
        int l, r, t, x, y, i;
        long long k;

        inline Q() {}

        inline Q(int l, int r, long long k, int t, int i, int len) : l(l), r(r), k(k), t(t), i(i) {
            x = l / len, y = r / len;
        }

        inline friend bool operator<(const Q &a, const Q &b) {
            return a.x == b.x ? a.y == b.y ? (a.y & 1) ? a.t < b.t : a.t > b.t : a.y < b.y : a.x < b.x;
        }
    } q[N];

    inline void update(int i, int x) {
        if (q[i].l <= u[x] && q[i].r >= u[x])
            S.change(1, a[u[x]], -1), S.change(1, v[x], 1);
        swap(a[u[x]], v[x]);
    }

    inline void solve() {
        scanf("%d%d", &n, &m), len = max(1, int(pow(n, 2.0 / 3.0)));
        for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
        int h = 0;
        long long k;
        for (int i = 1, o, l, r, t = 0; i <= m; i++) {
            scanf("%d", &o);
            if (o)++t, scanf("%d%d", &u[t], &v[t]);
            else scanf("%d%d%lld", &l, &r, &k), h++, q[h] = Q(l, r, k, t, h, len);
        }
        sort(q + 1, q + h + 1), S.build(1, 1, 100001);
        for (int i = 1, l = 1, r = 0, t = 0; i <= h; i++) {
            while (l > q[i].l)S.change(1, a[--l], 1);
            while (r < q[i].r)S.change(1, a[++r], 1);
            while (l < q[i].l)S.change(1, a[l++], -1);
            while (r > q[i].r)S.change(1, a[r--], -1);
            while (t < q[i].t)update(i, ++t);
            while (t > q[i].t)update(i, t--);
            ans[q[i].i] = S.t[1].sum < q[i].k ? -1 : S.ask(1, q[i].k, 0) - 1;
        }
        for (int i = 1; i <= h; i++)printf("%d\n", ans[i]);
    }
} MD;

int main() {
    MD.solve();
    return 0;
}

由于线段树可以为维护前缀和的前缀和，因此可以用带修主席树 O ( n log ⁡ 2 n ) O(n\log^2n) O(nlog2n) 维护。

#include<bits/stdc++.h>

#define lowbit(x) (x&(-(x)))
using namespace std;
const int N = 1e5 + 10, M = 1e5 + 1;
int a[N], n, m;

struct CMT {
    int rt[N], tmp[2][17], cnt[2], tot;
    struct {
        int l, r, val;
        long long sum;
    } t[N * 200];

    void update(int &p, int l, int r, int x, int v) {
        if (!p)p = ++tot;
        if (l == r)return t[p].sum = (t[p].val += v), void();
        int mid = (l + r) >> 1;
        x <= mid ? update(t[p].l, l, mid, x, v) : update(t[p].r, mid + 1, r, x, v);
        t[p].val = t[t[p].l].val + t[t[p].r].val;
        t[p].sum = t[t[p].r].sum + 1ll * t[t[p].r].val * (mid - l + 1) + t[t[p].l].sum;
    }

    int ask(int l, int r, long long k, int c, long long s) {
        if (l == r) {
            long long ns = c + s;
            for (int i = 1; i <= cnt[0]; i++)ns -= t[tmp[0][i]].sum;
            for (int i = 1; i <= cnt[1]; i++)ns += t[tmp[1][i]].sum;
            return ns < k ? 0 : l;
        }
        int mid = (l + r) >> 1;
        long long ns = 1ll * c * (r - mid) + s;
        for (int i = 1; i <= cnt[0]; i++)ns -= t[t[tmp[0][i]].r].sum;
        for (int i = 1; i <= cnt[1]; i++)ns += t[t[tmp[1][i]].r].sum;
        if (ns < k) {
            for (int i = 1; i <= cnt[0]; i++)c -= t[t[tmp[0][i]].r].val, tmp[0][i] = t[tmp[0][i]].l;
            for (int i = 1; i <= cnt[1]; i++)c += t[t[tmp[1][i]].r].val, tmp[1][i] = t[tmp[1][i]].l;
            return ask(l, mid, k, c, ns);
        } else {
            for (int i = 1; i <= cnt[0]; i++)tmp[0][i] = t[tmp[0][i]].r;
            for (int i = 1; i <= cnt[1]; i++)tmp[1][i] = t[tmp[1][i]].r;
            return ask(mid + 1, r, k, c, s);
        }
    }

    inline void change(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i))
            update(rt[i], 1, M, a[x], -1);
        a[x] = v;
        for (int i = x; i <= n; i += lowbit(i))
            update(rt[i], 1, M, v, 1);
    }

    inline int solve(int l, int r, long long k) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = l - 1; i; i -= lowbit(i))tmp[0][++cnt[0]] = rt[i];
        for (int i = r; i; i -= lowbit(i))tmp[1][++cnt[1]] = rt[i];
        return ask(1, M, k, 0, 0) - 1;
    }
} C;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        for (int j = i; j <= n; j += lowbit(j))
            C.update(C.rt[j], 1, M, a[i], 1);
    }
    while (m--) {
        int o;
        scanf("%d", &o);
        if (o) {
            int p, k;
            scanf("%d%d", &p, &k);
            C.change(p, k);
        } else {
            int l, r;
            long long k;
            scanf("%d%d%lld", &l, &r, &k);
            printf("%d\n", C.solve(l, r, k));
        }
    }
    return 0;
}