Segment Tree Problem!

Блог пользователя Mhammad1

Автор Mhammad1, история, 9 лет назад, По-английски

Hello every one

I've solved this problem but I have different questions about this problem:

The link : Frequent Values

The questions:

1 — How can I solve this problem if the values not sorted?

2 — How can I solve this problem online?

3 — How can I solve this problem if the values not sorted and online?

Edit: The link for the first question is here: values not sorted

segment tree, sqrt_decomposition

Mhammad1
9 лет назад
12

Комментарии (12)

Написать комментарий?

allllekssssa

9 лет назад, # |

First is Mo algorithm ...

→ Ответить

Mhammad1

9 лет назад, # ^ |

Please explain how it can be done by Mo algorithm?

→ Ответить

Archazey

9 лет назад, # ^ |

← Rev. 2 →

So for online method you can use BIT and make a new array b(b[i]=the numers of number from left of i with value a[i]).Now for query [L,R] take maximal from range :)

If values not sorted ,use Mo's algorithm.Read http://blog.anudeep2011.com/mos-algorithm/ . He has an example where he uses frequencies.U have to make the same but ,let's say we have an element with frequency x stored,we wanna keep an array and put 1 for every i(1<=i<=x).So in general,if you decrease the frequenct of an element from x to x-1,you decrease 1 at position x,if you increase,you increase 1 at position x+1.

Now for every query you binary search the last element in that array which is >0(hence there is a frequency existent).Or you can remove binary search and keep maximal 1 in the array,and update it when you decrease 1.

Total complexity O(N*sqrt(n)+Q*sqrt(n)+Q*log(n))) or O((N+Q)*sqrt(n)) The other solution is to keep a seg tree but it takes O(N*sqrt(n)+Q*sqrt(n)*log(n)),worse performane

For the 3rd problem,I wait myself for a solution...

→ Ответить

Mhammad1

9 лет назад, # ^ |

Thanks for the link and explanation, but I have another question:

Is every problem solvable by BIT can be solved by Segment Tree?

→ Ответить

Archazey

9 лет назад, # ^ |

BIT can be used for sum (in every case),and for maximal,minimal element when for a position ,every time you update the element,is better or equal than the previous value.Also can be used for multiplication when element is updated just once.

Seg tree can be used for a lot more things(gcd,multiplication-every time),lazy propagations,progressions,but it is more inefficient..

→ Ответить

OmaeWaMouShenDeiru

9 лет назад, # ^ |

can you please provide some problems that needs Mo algorithm.

→ Ответить

percywtc

9 лет назад, # ^ |

Yandex.Algorithm 2011 Round 2 Problem D

here: http://codeforces.com/problemset/problem/86/D

→ Ответить

novitiate

9 лет назад, # |

how did you solve this problem??using segment trees??

→ Ответить

Mhammad1

9 лет назад, # ^ |

← Rev. 2 →

It's a RMQ problem, you can build the tree of the frequency of every value, so every query can be done by O(log n) , but you have to handle the corner cases when a[i] != a[j] so the answer is:

`ans = max(start[a[i]] + cnt[a[i]] - i, j-start[a[j]], QUERY(a[i]+1, a[j]-1))`

So you have to keep track of the counter and the first appearance of every value.

→ Ответить

yeputons

9 лет назад, # |

+25

For the third problem (online + arbitrary values):

Let's find the most frequent value as well as number of its occurrences.
Let's suppose that we can get amount of occurrences of number X in segment [L, R] in $\text{[math]}$ . Can be done with map from value to list of positions + binary search. Or, what is better, compress all numbers in the array first and then use array instead of map. We will use that we have small numbers only in the future.
Observation: if we know answer for segment [L, R] (say, it's value X), then the most frequent value for segment [L', R'] (where L' ≤ L ≤ R ≤ R') is either X or it lies in $\text{[math]}$ .
That is, if we know answer for [L, R] we can find answer for [L', R'] in $\text{[math]}$ by combining previous points.

Next idea is sqrt decomposition. For a fixed L we can calculate answers for all possible Rs in O(N) (just keeping current amount of occurrences for each number in an array). Unfortunately, we cannot precalculate answers for all segments (it would be O(N²), to let's do it for K uniformly distributed Ls, it will be O(NK).

Then, we have some queries incoming. Suppose we have query [L, R]. Then we know that we can "shift" L for not more than $\text{[math]}$ elements and get a precalculated query. With the power of point 3 we now can answer query in $\text{[math]}$ .

The only thing left is to chose K wisely. We can let $\text{[math]}$ and have $\text{[math]}$ precalc and $\text{[math]}$ per query. Or we can minimize $\text{[math]}$ , where Q is amount of queries, and it's minimal when $\text{[math]}$ (just take a derivative). That way we have $\text{[math]}$ for precalculation and $\text{[math]}$ per query. When N ≈ Q we have $\text{[math]}$ for precalc and $\text{[math]}$ per query, which sums up to $\text{[math]}$

→ Ответить

Archazey

9 лет назад, # ^ |

← Rev. 3 →

Also I want to add an approach which is based on this idea but is faster.Overall complexity O(N*k+Q*(n/k)).So you can choose k=sqrt(Q) for the best complexity.

You can find it in this editorial https://discuss.codechef.com/questions/66188/qchef-editorial ,it's big but not so hard. Even if there the problem wants something else, you can change the meaning of last[i][j] from last position of j to number of positions equal to j and it's all done.

Also this problem uses same approach. https://www.codechef.com/problems/QCHEF

→ Ответить