Point Updates in Merge Sort Trees

tutorial
, ,
21

U have to assume all are distinct elements. i know this is totally wrong .
and when u submit the code on spoj also, then u will get AC by this assumption.
and in comments also it is mentioned.
I think both the questions have their proper solution using sqrt decomposition.

22

Maybe, but n log^2 n is better than n sqrt n. It should have worked.

1 Like
23

Variation of ~0.1seconds on resubmitting is common. But it does seem suspicious, I will ask admins to have a look.

3 Likes
24

thanks bro :slight_smile: learned a lot

25

merge sort trees using binary indexed tree
problem : CodeChef: Practical coding for everyone
if count small is false in query it will return kth smallest element in range [a,b]

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


#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<int,null_type,less_equal<int>,rb_tree_tag,
tree_order_statistics_node_update> orderedmultiset;


int sz;
vector<orderedmultiset> bit;

int lowbit(int x){
    return x&-x;
}

void add(int i,int x){
    for(;i<=sz;i+=lowbit(i))
        bit[i].insert(x);
}

int query(int i,int x){
// count number strictly smaller than x till ith
    int count = 0;
    for( ; i > 0; i-=lowbit(i)){
        count += bit[i].order_of_key(x);
    }
    return count;
}

int query(int l,int r,int kth,bool cntsmall=false){

    if(cntsmall){
        return query(r,kth) - query(l-1,kth);
    }

    int low = 0, high = 10, ans = 0;
    while(low <= high){
        int mid = (low+high)/2;
        int cnt = query(r,mid) - query(l-1,mid);

        if(cnt < kth){
            ans = mid;
            low = mid+1;
        }else{
            high = mid-1;
        }
    }
    return ans;
}

void update(int i,int old,int newval){
    for(;i<=sz;i+=lowbit(i)){
        bit[i].erase(bit[i].upper_bound(old));
        bit[i].insert(newval);
    }
}

void build(vector<int> &v){
    sz = v.size();
    bit.resize(sz+1);
    for(int i=1;i<sz;i++){
        add(i,v[i]);
    }
}


void solve(){

    int n;
    cin >> n;
    
    vector<int> v(n+1);
    for(int i=1;i<=n;i++){
        cin >> v[i];
    }

    build(v);

    int q;
    cin >> q;
    while(q--){
        int type;
        cin >> type;
        if(type == 0){
            int l,r,x;
            cin >> l >> r >> x;
            cout<<( r-l+1 - query(l,r,x,true))<<endl;
        }
        else{
            int p,x;
            cin >> p >> x;
            update(p,v[p],x);
            v[p] = x;
        }
    }
}   

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
    solve();
    return 0;
}