div24ever's blog

By div24ever, 3 years ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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<r;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]<dfs_in[j]&&dfs_in[j]<dfs_out[j]&&dfs_out[j]<dfs_out[i]){
		return true;
	}
	else return false;
}
void deber(){
	for(int i=1;i<=n;i++){
		cout<<dfs_in[i]<<" "<<dfs_out[i]<<"\n";
	}
	for(int i=1;i<4*n;i++){
		cout<<seg[i]<<" ";
	}
	cout<<endl;
	for(int i=1;i<=n;i++)cout<<parxor[i]<<" ";
	cout<<endl;
	cout<<isancesof(5,4)<<endl;
}
void dfs(lli i){
	dfs_in[i]=timer++;
	for(lli j=0;j<(lli)g[i].size();j++){
		k=g[i][j].F;
		v=g[i][j].S;
		if(dfs_in[v]==-1){
			parxor[v]=k;
			dfs(v);
		}
	}
	dfs_out[i]=timer++;
}
 
void solve(){	
	cin>>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<n-1;i++){
		cin>>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<m;i++){
		cin>>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<m;i++){
		cout<<ans[i]<<"\n";
	}
	clearall();
}
 
int main(){
	fastIO;
	int t=1;
	cin>>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   Vote: I like it 0 Vote: I do not like it

    I solved it offline too. Need an online approach. Thanks.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

for each node v store the Xor of numbers lie on path between v and 2^i parent of v

for 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   Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      So you need another approach you alright, i didn't take care about k.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Theres a K factor in query too... How would you inculcate that in this sparse table approach?

»
3 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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] ^= x
2. 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, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +1 Vote: I do not like it

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.