Help me with this data structure problem pls!

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3773
3	Radewoosh	3646
4	ecnerwala	3624
5	jqdai0815	3620
5	Benq	3620
7	orzdevinwang	3612
8	Geothermal	3569
8	cnnfls_csy	3569
10	gyh20	3447

№	Пользователь	Вклад
1	cry	161
2	awoo	160
2	maomao90	160
4	atcoder_official	157
5	-is-this-fft-	155
5	nor	155
7	adamant	153
8	maroonrk	152
8	Um_nik	152
10	djm03178	146

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):

My Code

#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

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) ?

Комментарии (16)

Написать комментарий?

Abito

4 часа назад, # |

You can solve it using persistent segment tree

→ Ответить

PUSSY_LICKING_LOLI_69

4 часа назад, # ^ |

How would you handle the update queries? I can do it with persistent segment tree if there are no updates

3 часа назад, # ^ |

Sorry I didn't notice.

Meron3r

-17

Here’s a simpler way to tackle the problem:

Use a Segment Tree: Think of it like a big tree where each node covers a part of the array and keeps a sorted list of the numbers in that part.

For Updates: When you change a number in the array, you update the sorted lists in the parts of the tree that cover that number.

For Queries: To find the k-th smallest number in a range, you collect and merge the sorted lists from the relevant parts of the tree, then pick the k-th smallest from the merged list.

This method is pretty efficient and manages both updates and queries well.

← Rev. 2 →

I remember doing this for a similar problem without updates and small k constraint, but this problem has larger constraints for k, which is up to n. I can be mistaken but it seems your solution has a time complexity of O(n^2*log^2)

It's probably chatgpt solution

mustard_with_fries69420

This approach is O(nq), since merging the lists take O(n).

How would you merge the lists to find the kth quickly?

Rimuru

3 часа назад, # |

Could you give the problem link?

let me know if you solve it ;)

https://marisaoj.com/problem/343

Brovko

You can use segment tree or Fenwick tree where $$$t[i]$$$ is ordered_set of indices $$$j$$$ such that value $$$a[j]$$$ is in the $$$i$$$-th segment of segment/Fenwick tree.

2 часа назад, # ^ |

I think that it is similar to my solution, but i used treaps instead of ordered sets. This is the first time I've heard about it and it seems pretty powerful. I wonder if it is allowed to be used in competitions, as it is pretty wild for a pre implemented data structure.

111 минут назад, # ^ |

Tried the oredered_set out and it runs 1s slower than treap with full constraints :(

sojabhai

2 часа назад, # |

Use a merge sort tree and on each node use an ordered set for updates

BiggestOtaku

117 минут назад, # ^ |

That was also my first though but how are you getting kth smallest number in O(logn^2).

67 минут назад, # ^ |

My bad yeah the query will take O(logn ^ 3)

Блог пользователя PUSSY_LICKING_LOLI_69