提出 #70977279

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct fenwick {
    int n;
    vector<ll> bit;
    fenwick(int n = 0) { init(n); }
    void init(int n_) { n = n_; bit.assign(n + 1, 0); }
    void add(int i, ll val) {
        for (; i <= n; i += i & -i) bit[i] += val;
    }
    ll sum(int i) {
        ll res = 0;
        for (; i > 0; i -= i & -i) res += bit[i];
        return res;
    }
};

void solve()
{
    ll n,t;
    cin>>n>>t;
    vector<ll> a(n+1);
    vector<ll> v;
    vector<tuple<ll,ll,ll>> q(t);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v.push_back(a[i]);
    }
    for(int i=0;i<t;i++){
        ll type,p1,p2;
        cin>>type>>p1>>p2;
        q[i]=make_tuple(type,p1,p2);
        if(type==1) v.push_back(p2);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    map<ll,int> val_map;
    for(size_t i=0;i<v.size();i++)
        val_map[v[i]]=i+1;
    int m = v.size();
    fenwick bit_cnt(m);
    fenwick bit_sum(m);
    for(int i=1;i<=n;i++){
        int id=val_map[a[i]];
        bit_cnt.add(id,1);
        bit_sum.add(id,a[i]);
    }
    for(int i=0;i<t;i++){
        ll type,p1,p2;
        tie(type,p1,p2)=q[i];
        if(type==1){
            ll x=p1;
            ll new_v=p2;
            ll old_v=a[x];
            if (old_v==new_v) continue;
            int old_id=val_map[old_v];
            bit_cnt.add(old_id,-1);
            bit_sum.add(old_id,-old_v);
            int new_id=val_map[new_v];
            bit_cnt.add(new_id,1);
            bit_sum.add(new_id,new_v);
            a[x] = new_v;
        }
        else{
            ll l=p1;
            ll r=p2;
            if(l>r){
                ll total_n=bit_cnt.sum(m);
                cout<<total_n*l<<"\n";
                continue;
            }
            ll total_sum=0;
            auto it_l=lower_bound(v.begin(),v.end(),l);
            int id_before_l=distance(v.begin(),it_l);
            auto it_r=upper_bound(v.begin(),v.end(),r);
            int id_le_r=distance(v.begin(),it_r);
            ll count_lt_l=bit_cnt.sum(id_before_l);
            total_sum+=count_lt_l*l;
            ll sum_le_r=bit_sum.sum(id_le_r);
            ll sum_lt_l=bit_sum.sum(id_before_l);
            ll sum_range=sum_le_r-sum_lt_l;
            total_sum+=sum_range;
            ll total_n=bit_cnt.sum(m);
            ll count_le_r=bit_cnt.sum(id_le_r);
            ll count_gt_r=total_n-count_le_r;
            total_sum += count_gt_r*r;
            cout<<total_sum<<"\n";
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    //cin>>t;
    t=1;
    while(t--) solve();
    return 0;
}

提出情報

ジャッジ結果