Help me with this data structure problem pls!
Difference between en1 and en2, changed 171 character(s)
Given an array A of size n. Do these q queries:↵

1 pos x: assign A[pos] = x;↵

2 l r k: find k-th smallest element in range [l,r]↵

Constraints:↵

n,q <= 1e5↵

A[i], x <= 1e9↵


My first aproach was to use a Wavelet tree with a BST(specifically a Treap) on each of its nodes. This gives a time complexity of O(n*log^2) and can do online queries(I still did it offline, i had to read all the input and compress the values because i don't want to make the Wavelet tree dynamic). However it has a really high constant factor and it takes 7-8 seconds to run with the full constraints.↵

Here's my code if you're interested (sorry if it's poorly written):↵



<spoiler summary="My Code">↵
```c++↵
#include <bits/stdc++.h>↵
using namespace std;↵

//#define int long long //emergency debug↵

typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef pair<ii,int> iii;↵
#define f first↵
#define s second↵
#define pb push_back↵
#define mp make_pair↵
#define hellnah cout<<"NO\n"↵
#define fuckyeah cout<<"YES\n"↵
#define en '\n'↵


const ll oo = 1e9;↵
const ll mod = 1e9+7;↵

ll Rand(ll l, ll r){↵
    ll res = 0;↵
    for(int i = 0;i<4;i++) res = (res<<15)+ (rand()&((1<<15)-1));↵
    return res%(r-l+1)+l;↵
}↵


struct Treap{↵
    struct Node{↵
        Node* c[2];↵
        int key, pri;↵
        int sz, ma;↵

        Node(int x){↵
            c[0] = c[1] = NULL;↵
            ma = key = x;↵
            sz = 1;↵
            pri = Rand(1,2e9);↵
        }↵
    };↵
    Node* root = NULL;↵

    void recalc(Node* u){↵
        u->ma = u->key;↵
        u->sz = 1;↵
        if(u->c[0]!=NULL) u->ma = max(u->ma, u->c[0]->ma), u->sz+=u->c[0]->sz;↵
        if(u->c[1]!=NULL) u->ma = max(u->ma, u->c[1]->ma), u->sz+=u->c[1]->sz;↵
    }↵

    Node* merge(Node* u, Node* v){↵
        if(u==NULL) return v;↵
        if(v==NULL) return u;↵

        if(u->pri >= v->pri){↵
            u->c[1] = merge(u->c[1], v);↵
            recalc(u);↵
            return u;↵
        }↵
        else{↵
            v->c[0] = merge(u, v->c[0]);↵
            recalc(v);↵
            return v;↵
        }↵
    }↵

    pair<Node*, Node*> split(Node* u, int k){↵

        if(u==NULL) return {NULL, NULL};↵

        if(u->sz==1){↵
            if(u->key<=k) return {u,NULL};↵
            return {NULL,u};↵
        }↵


        if(u->c[0]!=NULL && u->c[0]->ma>=k){↵
            pair<Node*, Node*> tmp = split(u->c[0],k);↵
            u->c[0] = tmp.s;↵
            recalc(u);↵
            return {tmp.f,u};↵
        }↵
        else if(u->key > k){↵
            Node* tmp = u->c[0];↵
            u->c[0] = NULL;↵
            recalc(u);↵
            return {tmp,u};↵
        }↵
        else{↵
            pair<Node*, Node*> tmp = split(u->c[1],k);↵
            u->c[1] = tmp.f;↵
            recalc(u);↵
            return {u, tmp.s};↵
        }↵
    }↵

    void add(int k){↵
        Node* node = new Node(k);↵
        pair<Node*, Node*> tmp = split(root, k);↵
        root = merge(tmp.f, merge(node, tmp.s));↵
    }↵

    void del(int k){↵
        pair<Node*, Node*> tmp = split(root, k-1);↵
        pair<Node*, Node*> tmp2 = split(tmp.s, k);↵
        delete(tmp2.f);↵
        root = merge(tmp.f, tmp2.s);↵
    }↵

    int getpos(int k){↵
        Node* u = root;↵
        int res = 0;↵
        while(u != NULL){↵
            if(u->key<=k) res++;↵
            if(u->c[0]!=NULL){↵
                if(u->c[0]->ma>k) u = u->c[0];↵
                else{↵
                    res+=u->c[0]->sz;↵
                    u = u->c[1];↵
                }↵
            }↵
            else u = u->c[1];↵
        }↵

        return res;↵
    }↵
};↵




int n,q;↵
int a[100005];↵
int unzip[200005];↵
ii abc[200005];↵
iii que[100005];↵

Treap st[800005];↵

void ADD(int id, int l, int r, int val, int pos){↵
    st[id].add(pos);↵
    //return;↵
    if(l==r) return;↵

    int m = l+r>>1;↵
    if(val<=m) ADD(id*2,l,m,val,pos);↵
    else ADD(id*2+1,m+1,r,val,pos);↵
}↵

void DEL(int id, int l, int r, int val, int pos){↵
    st[id].del(pos);↵
    //return;↵
    if(l==r) return;↵

    int m = l+r>>1;↵
    if(val<=m) DEL(id*2,l,m,val,pos);↵
    else DEL(id*2+1,m+1,r,val,pos);↵
}↵

int GET(int L, int R, int k){↵
    int id = 1;↵
    int l = 1, r = n+q;↵
    while(l!=r){↵
        int m = l+r>>1;↵
        int tmp = st[id*2].getpos(R) - st[id*2].getpos(L-1);↵
        if(tmp>=k) id = id*2, r = m;↵
        else k-=tmp, id = id*2+1, l = m+1;↵
    }↵
    return unzip[l];↵
}↵


int32_t main(){↵
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵


    srand(time(0));↵
    cin>>n>>q;↵
    for(int i = 1;i<=n;i++) cin>>abc[i].f, abc[i].s = i;↵

    for(int i = 1;i<=q;i++){↵
        int t; cin>>t;↵
        int x,y,z;↵
        if(t==1){↵
            cin>>x>>y;↵
            que[i].s = -1;↵
            que[i].f.f = x;↵
            abc[i+n] = mp(y, -i);↵
        }↵
        else{↵
            cin>>x>>y>>z;↵
            que[i] = mp(mp(x,y),z);↵
        }↵
    }↵

    sort(abc+1, abc+n+q+1);↵
    int it = 0;↵
    for(int i = 1;i<=n+q;i++){↵
        if(abc[i].f!=abc[i-1].f) ++it, unzip[it] = abc[i].f;↵

        if(abc[i].s<0){↵
            int x = -abc[i].s;↵
            if(que[x].s==-1) que[x].f.s = it;↵
            //else que[x].s = it;↵
        }↵
        else a[abc[i].s] = it;↵
    }↵



    for(int i = 1;i<=n;i++) ADD(1,1,n+q,a[i],i);//, cout<<a[i]<<' '<<i<<en;↵

    for(int i = 1;i<=q;i++){↵
        int x,y,z;↵
        x = que[i].f.f;↵
        y = que[i].f.s;↵
        z = que[i].s;↵

        if(z==-1){↵
            DEL(1,1,n+q,a[x],x);↵
            a[x] = y;↵
            ADD(1,1,n+q,a[x],x);↵
            continue;↵
        }↵

        cout<<GET(x,y,z)<<en;↵
    }↵

    return 0;↵
}↵



//flashbang↵

```↵
</spoiler>↵


It is allowed to do queries offline, and the problem also has a tag of paralel binary search.↵

Can someone please show me the intended solution with paralel binary search (or even optimize my current code) ?



UPDATE: Solution founded :D↵
https://robert1003.github.io/2020/02/05/parallel-binary-search.html#a-hrefhttpacmhdueducnshowproblemphppid5412hdu5412---crb-and-queriesa

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English PUSSY_LICKING_LOLI_69 2024-09-09 03:15:27 171
en1 English PUSSY_LICKING_LOLI_69 2024-09-08 12:28:56 5993 Initial revision (published)