#define endl “\n” did the work for me for subtask 2 .It went from tle to 1.65
exactly the other way around
3 Likes
ufff
as i said…i read this sometime back. Sorry for the wrong info 
Can anyone note if i am making any mistake-
Firstly i thought of making a bfs order for the tree and make the persistent seg tree on this bfs order array i.e i mean if the ith index of pst array is 1 it indicates the last occurence of the value
in the node which has i as bfs order index-
now i am intended to build pst for every node and for each query i will query on the given nodes pst
Then just applied the dsu on trees trick that is firstly recursively build the pst s for small child nodes with keep=0 that is when it will return it will not have any effect of the small child nodes on the pst array then similarly i will call the dfs on the big child with keep=1; then will now go to the small child nodes and make updates due to these nodes on the pst of the bigchild. By update i mean if the current node (which i am using to update) value’s previous occurence is somewhere greater than the bfs order index of current node then i will update the current node’s bfs order index to 1 in the pst and set the prev occurence index value in pst to 0 , similarly if the current value has’nt occured previously then will just update current node bfs order index in pst to 1.
This way after all the updates the current version will be the pst for the processing node.
Now the thing is how will i query for different heights of a given node-
Well for this what i thought of doing is to make a sum query call on the pst of the given node from 0 to number of nodes till height( query node’s height+given query height)'th index
Wont it be correct?
I cant find any mistake with this approach
We need maximum two updates to add a node (say v). One is "add 1 to v". After this update, only ancestors of v that already have another node with same value as v will be incorrect because they will count this node’s value twice. If such a node exists we need another update. If the closest ancestor to v that has another node with same value is a, "add -1 to a". This will correct all the incorrect ancestors because for each we subtracted 1, all other subtrees are unaffected.
I prefer these kinds of editorials, I could easily follow the idea and I don’t think it can be any more concise and be so. Also if I hadn’t solved it, I would have taken some of the hints and tried to solve it from there. (Actually in this case my O(n \lg^2 n + q \lg n) didn’t pass so I would have been irritated and not read the editorial at all, but otherwise I would have done that)
1 Like
If you read through the editorial, I have linked resources as and when you need it while doing a particular step.
1 Like
Too long editorial. Waiting for your video solution. After that I will come back to this post.
1 Like
My O(nlog^2n + qlogn) solution passed quite easily in 2.53s ( with pragma) ans 2.86s(without pragma). Here’s the link: CodeChef: Practical coding for everyone. Though I had to use a hash table during merge.
1 Like
@rajarshi_basu Can you please provide the links to learn the persistence data structure fully? It would be really helpful.
1 Like
What i actually did was to change the question to find the no of elements smaller then l in the range l to r,so this made it much time efficient.
you can do this by saving the position of previous occurrence of that number in the current position of the number, if it occurs first time then 0 in its place.
I was able to solve this only after contest ends. But I’d like to share my approach, because It looks easier than editorial, no merge.
Using DSU find for each node v some parent node u containing node x in its subtree with a[x]==a[v] and depth[x]<depth[v]. So that node x cancels v contribution for trees having root above or equal to u.
Then build persistent segment tree for each height of original tree starting from the root. Add +1 at position of v and -1 at position of u in euler tour.
2 Likes
Wow nice, I know there was back_inserter in c++, this is more easier to remember, as compared to back_inserter, thanks.
wow thats a very nice idea. I will add it to the edi