### im_115's blog

By im_115, history, 16 months ago,

Problem link — 1354D - Мультимножество
Solution link — 143561353

I am using segment tree. The time complexity of the code is O( n * ( (logN)^2 ) ) which should pass the time limit. I am also using ios_base::sync_with_stdio(0);cin.tie(0); for fast IO.

• -6

 » 16 months ago, # | ← Rev. 2 →   +3 The time complexity of the code is O( n * ( (logN)^2 ) ) which should pass the time limit It should not pass the time limit. For $n =10^6$, $n *(logN)^2 = 4*10^8$. This should only pass only if the solution was some dp with simple recurrence like multiplying a couple of other dps, not for a high constant algorithm like segtree, and even then it would probably be tight on this 1.5 second time limit.
•  » » 16 months ago, # ^ |   0 Is Fenwick tree faster than segment tree? Also i am using a class for segment tree. So does using a class makes the program slow?
 » 16 months ago, # |   0 The complexity sounds right, but a segment tree has a relatively high overhead that won't make it work in this case. You can use the same algorithm with a Fenwick tree, which has the same complexity as a segment tree but uses less memory and is faster. For reference: my solution
•  » » 16 months ago, # ^ |   0 Is Fenwick tree faster than segment tree? Also i am using a class for segment tree. So does using a class makes the program slow?
•  » » » 16 months ago, # ^ | ← Rev. 2 →   +3 No, classes don't necessarily make your program slower. In fact, in my solution I'm using a class for my Fenwick (well, a struct, but it's just a class with default public access).A Fenwick is definitely faster than a segment tree (look at how simple the update and query operations are), but it's not as versatile. In particular, you can only do range queries if the operation you're using is invertible — so a sum is ok, but a maximum is not. In the restricted case of only querying for a prefix, you can also do maximum queries, but you loose the ability to query arbitrary ranges.Additionally, a fenwick also uses less memory than a segment tree (fenwick N+1 items, segment ~2N)
•  » » » » 16 months ago, # ^ |   0 Ok thanks.
•  » » » » » 16 months ago, # ^ |   +8 Extra credit: not needed in this case, but you can solve the problem quite elegantly in O(NlogN) by doing the search directly "inside" of the fenwick tree, as explained here.(see: my solution)