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
↵
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
