### div24ever's blog

By div24ever, 3 years ago, ,

Given 3 types of queries

1. Insert element 'x' into multiset
2. Delete element 'x' from multiset
3. Find xor of all elements present in multiset which are less than 'k' (k is not fixed)

I required above solution in this problem. But I was unable to solve it this way. How to solve this?

• +9

 » 3 years ago, # | ← Rev. 2 →   0 Well i solved it during the contest. well you need to be versed with few concepts: 1. Tree linearisation- doing dfs to get in and out time and get a linear tree. 2. Offlining the queries. 3. Sorting queries based on 'k' 4. Building segment tree on the linearised tree. graph g;//Adjlist vi dfs_in,dfs_out,parxor;//Properties while DFS edgeL edg;//my edgelist lli timer=0; lli n,m,u,v,k; lli seg[400010],q1,q2; void build(){ for(lli i=1;i<=n;i++){ seg[2*n+dfs_in[i]]=parxor[i]; seg[2*n+dfs_out[i]]=parxor[i]; } for(lli i=2*n-1;i>0;i--){ seg[i]=seg[i<<1]^seg[i<<1|1]; } } void modify(lli p){ for(seg[p+=2*n]=0;p>1;p>>=1){ seg[p>>1]=seg[p]^seg[p^1]; } } void updater(lli i){ modify(dfs_in[i]); modify(dfs_out[i]); } lli query(lli l,lli r){ lli res=0; for(l+=2*n,r+=2*n;l>=1,r>>=1){ if(l&1)res^=seg[l++]; if(r&1)res^=seg[--r]; } return res; } void clearall(){ g.clear(); dfs_in.clear(); dfs_out.clear(); parxor.clear(); edg.clear(); } bool isancesof(lli i,lli j){ if(dfs_in[i]>n; memset(seg,0,sizeof seg); g.resize(n+1); edg.resize(n-1); dfs_in.assign(n+1,-1); dfs_out.assign(n+1,-1); parxor.assign(n+1,0); for(lli i=0;i>u>>v>>k; g[u].PB(MP(k,v)); g[v].PB(MP(k,u)); edg[i].F=k; edg[i].S.F=u; edg[i].S.S=v; } timer=0; dfs(1); cin>>m; build(); //deber(); sort(edg.begin(),edg.end()); lli now=n-2; querytype arr[m]; for(lli i=0;i>u>>v>>k; arr[i].F=k; arr[i].S.F=i; arr[i].S.S.F=u; arr[i].S.S.S=v; } lli ans[m]; sort(arr,arr+m); for(lli q=m-1;q>=0;q--){ while(now>=0&&edg[now].F>arr[q].F){ if(isancesof(edg[now].S.F,edg[now].S.S))updater(edg[now].S.S); else updater(edg[now].S.F); now--; } if(now==-1){ ans[arr[q].S.F]=0; } else{ q1=query(0,dfs_in[arr[q].S.S.F]+1); q2=query(0,dfs_in[arr[q].S.S.S]+1); ans[arr[q].S.F]=q1^q2; } } for(lli i=0;i>t; while(t--){ solve(); } } My code is enough moduler to understand what every function does. In my segment tree i just make the values 0 fore those edges that are no longer required after sorting and using sorted k.There are Persistent tree approaches also available.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I solved it offline too. Need an online approach. Thanks.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 For online, you will definitely need Persistent tree i guess, or something similar. Well these two problems are more or less comparable to offline and online. KQUERY and KQUERYO on spoj... check them out. Well if you don't want to use Persistent tree then see the solution of KQUERYO.The Solution uses the Mergesort tree approach on segment tree storing the whole sorted elements of the segment tree at each node for its range. Querying one node takes O(Logn) time. Hope this helps.
 » 3 years ago, # | ← Rev. 2 →   0 for each node v store the Xor of numbers lie on path between v and 2^i parent of vfor each query find the LCA(u, v), then find Xor path(u, LCA) let it's X, path(v, LCA) let it's Y, in log(n) so the answer is (X xor Y)
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 k is not fixed and we don't need to find lca because xoring path from u to root and v to root will cancel out path from lca to root.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 So you need another approach you alright, i didn't take care about k.
•  » » 3 years ago, # ^ |   0 Theres a K factor in query too... How would you inculcate that in this sparse table approach?
 » 3 years ago, # | ← Rev. 2 →   +17 You can mantain all the values in a binary balanced tree(BBT) [such as treap(aka. cartesian tree)]. Operations 1. and 2. are natural of BBT. For operation 3. you can store on each node of the tree the xor of all elements on the subtree, and to compute the xor of all elements less than a k you can perform binary search on the tree [notice that I mean traverse the tree which is almost the same as doing binary search] or a simpler [probably slower option] split the tree into two trees, all elements less than k in one tree A and the remaining elements in the other tree B, then the value you are looking for is the xor stored on the root of the tree A. Overall complexity is log(n) per query.Note: Since the query operation is xor and a^a = 0 both operations 1. and 2. are the same operation: Change the parity of the frequency of the element x in the multiset. This is not too relevant though.
 » 3 years ago, # | ← Rev. 3 →   0 If x, k is in friendly range, you can just use Binary Indexed Tree.1. Insert x: for(int i = x; i <= maxX; i += i & -i) BIT[i] ^= x2. Delete x: Same as Insert. As XOR-ing again is same as removing it.3. Query k: for(int i = k-1; i > 0; i -= i & -i) ans ^= BIT[i]; In the problem you linked, You can compress all x and k first, so they will be in range [1, n + q]. Then you can do update(compressed[x], x) and query(compressed[k]).In the problem XOR of path (u, v) is actually same as XOR of path (root, u) and (root, v). XOR of path (root, lca(u, v)) will be cancelled by XOR-ing twice. Here is my submission — 14527601
 » 3 years ago, # |   0 Use something like a skiplist... As n,m<=10^5,a list like this can be also OK: ~~~~~ int prefix_xor[317]; struct node{ int data; list *next,*prev,*next317; } ~~~~~
 » 3 years ago, # | ← Rev. 3 →   +1 Online approach using persistent segment tree suggested by fazlerahmanejazi.This solution is for arrays and can be extended to your problem.1. Make a sorted array of unique array elements.2. Initialize segment tree to be all zeroes. This version of the segment tree is S0.3. Take the first element of the sorted array. Let it be x. Update the segment tree S0 with value x at all indices where the array has value x. This version of segment is S1.4. Similarly, form segment tree Si from Si - 1.5. For query k, find the index i of sorted array element that is just smaller than k. Query on Si.