# | User | Rating |
---|---|---|

1 | tourist | 3372 |

2 | mnbvmar | 3345 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | Radewoosh | 3230 |

5 | scott_wu | 3189 |

6 | Benq | 3187 |

7 | LHiC | 3171 |

8 | Um_nik | 3155 |

9 | V--o_o--V | 3152 |

10 | Petr | 3139 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 191 |

2 | Errichto | 172 |

3 | rng_58 | 159 |

4 | neal | 156 |

5 | Um_nik | 154 |

5 | tourist | 154 |

7 | Ashishgup | 151 |

7 | Petr | 151 |

7 | PikMike | 151 |

10 | 300iq | 150 |

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/17/2018 06:42:15 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Maybe try reserving the size of HashMap to prevent rehashing? This will make your program quite a bit faster.

I think that the problem is your update query, because every time you go up in the segment tree you merge the left and right child with complexity O(n). Thus your complexity per update is something like O(n*log(n)) which gives you time limit.

Yeah oorviziel is right, instead of "merging them" think of it as a path going down, and you do mp[thing]++ for every node in the path.

And now I'm looking at his code again. He does the same thing in his query function. So again the complexity for both update and query function is O(n*log(n)).

Can you please explain your solution in a bit detail , I am starting to learn Segment trees and need some help.:(

without merging 2 child map in parent map at every node,you can assign the larger map in parent(coming from left/right child) then merge the other map with the parent node

I don't understand how that will reduce the time complexity sire

You can take e look at this tutorial by Arpa where he told about how this reduce complexity

You have to code it faster.

The sky is blue.

nope it is blue during the day

how to do so??

Can someone help me it's been 9 days since I posted this?

Interesting problem. Will try it later, maybe tomorrow. Hopefully, I would be able to help you.

Let's try to define the structure of each node in the segment tree. Consider the node responsible for the segment from

LtoR. We can keep two data structures for the elements in this segment:1. A map

map1 of frequencies calledfreq, wherefreq[x] stores the no. of timesxis present in the segment. The key in this map is the elementx.2. A map

map2 of elements with a specified frequency. The key in this map is the frequencyfreq[x] of elementx, and the corresponding value is a set of all elementsxwith this frequency.All queries of type 1 will update both these maps efficiently.

How will we find the dominator in a single node in the segment tree? We simply look at the largest key in

map2, and if this key is at least (R-L+2)/2, we say that this segment has a dominator. Therefore, we figured how to find whether or not a dominator is present in a single node.The situation is complicated for type 2 queries, because while querying the segment tree for arbitrary segments, multiple nodes are reached, and checking only the largest key isn't enough, as the elements corresponding to largest frequency will change from node to node. Notice that each query in a segment tree executes the terminating condition at most log(n) times.

~~Therefore, we only need to check log(n) largest keys in~~map2. As there are log(n) nodes, and log(n) keys are checked per node, we run the queries in log^2(n), which should be sufficiently good.Notice that as the keys of map2 denote distinct frequencies, it's size can be at most sqrt(length of segment). Why? Because, the smallest distinct sizes having only 1 element each are 1,2,3,....,sqrt(R-L+1) such that their sum is R-L+1.

As there are log(n) nodes, the total complexity is Q * log(n) sqrt(n)

Notice that

map2 actually gives the value of the dominator itself. Since the problem only asks for Yes/No answers, we can just keep a count of elements with that particular frequency(the key in map2) as value inmap2 instead of a set as value.