FJUT3574 HOME_W的附加题（带权线段树）题解

题意：

给定n个数a1,a2,a3,……an。和m次操作。

每次操作格式如下

x y k   表示将a[x]替换为y。并求替换后，前k小的数之和

思路：我们用带权线段树维护权值，这里就是维护i的个数num[i]，然后顺便维护一下和。每次查询前k个数求和。

练习赛题解：

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

typedef long long ll;

const int maxn =  + ;

const int seed = ;

const ll MOD = 1e9 + ;

const ll INF = 1e17;

using namespace std;

int num[maxn << ], a[maxn], b[maxn];

ll sum[maxn << ];

void build(int l, int r, int rt){

    if(l == r){

        num[rt] = a[l];

        sum[rt] = l * num[rt];

        return;

    }

    int m = (l + r) >> ;

    build(l, m, rt << );

    build(m + , r, rt <<  | );

    num[rt] = num[rt << ] + num[rt <<  | ];

    sum[rt] = sum[rt << ] + sum[rt <<  | ];

}

void update(int pos, int l, int r, int rt, int v){

    if(l == r){

        num[rt] += v;

        sum[rt] = l * num[rt];

        return;

    }

    int m = (l + r) >> ;

    if(pos <= m)

        update(pos, l, m, rt << , v);

    else

        update(pos, m + , r, rt <<  | , v);

    num[rt] = num[rt << ] + num[rt <<  | ];

    sum[rt] = sum[rt << ] + sum[rt <<  | ];

}

ll query(int l, int r, int rt, int k){

    if(l == r){

        return l * k;

    }

    int m = (l + r) >> ;

    ll ans = ;

    if(num[rt << ] >= k){

        ans += query(l, m, rt << , k);

    }

    else{

        ans += sum[rt << ];

        ans += query(m + , r, rt <<  | , k - num[rt << ]);

    }

    return ans;

}

int main(){

    int n, m;

    memset(a, , sizeof(a));

    scanf("%d%d", &n, &m);

    for(int i = ; i <= n; i++){

        scanf("%d", &b[i]);

        a[b[i]]++;

    }

    build(, , );

    int x, y, k;

    for(int i = ; i < m; i++){

        scanf("%d%d%d", &x, &y, &k);

        update(b[x], , , , -);

        update(y, , , , );

        b[x] = y;

        printf("%lld\n", query(, , , k));

    }

    return ;

}