Help me with this data structure problem pls!

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	djm03178	152

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

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

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

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

Abito

3 месяца назад, # |

You can solve it using persistent segment tree

→ Ответить

PUSSY_LICKING_LOLI_69

3 месяца назад, # ^ |

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

Sorry I didn't notice.

Meron3r

-36

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)

+18

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

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.

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.

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

sojabhai

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

BiggestOtaku

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

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

soham_c04

You can use MergeSort Tree and then binary search or in this case use a ordered_multiset (since it also suports order_of_key() operation) for update queries. But since, binary search takes up extra $$$O(logN)$$$ time we can use fractional cascading to precompute this at the cost of extra memory by storing the iterators of lower_bound in the right and left child of current node in the Segment Tree, along with the element values.

Thus, each time we query we get a $$$O(logN)$$$ complexity. However, building the update function will be trickier here.

I think combining this with this should work.

pikamonstruosa

Holy username. I couldn't help but laugh at it. Definitely a normal and not sussy at all name.

tangdong_

+13

Here's the intended solution, I think? https://robert1003.github.io/2020/02/05/parallel-binary-search.html#a-hrefhttpacmhdueducnshowproblemphppid5412hdu5412---crb-and-queriesa

thanks for sharing this :D

I updated the blog with the solution

Auto comment: topic has been updated by PUSSY_LICKING_LOLI_69 (previous revision, new revision, compare).

jatrophalouvre

Alternative: we can try using a Splay tree. Updates is just updating the value of the node, and for querying, we first splay(l-1), then splay(r+1). Then, binary searching on $$$[l, r]$$$ gives us the answer in $$$O(N\log N)$$$, albeit with a pretty high constant.

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