Segment Tree Problem!

→ Обратите внимание

До соревнования
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
30:40:31
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	Benq	3676
2	jiangly	3670
3	Kevin114514	3657
4	maroonrk	3355
5	Um_nik	3353
6	squareOf105	3346
7	tourist	3343
8	strapple	3324
9	heuristica	3322
10	jiangbowen	3291

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	Qingyu	158
2	nik_exists	150
2	maspy	150
4	AmShZ	143
5	Um_nik	142
6	Errichto	139
7	adamant	137
8	BledDest	135
9	maroonrk	133
10	qwexd	130

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Segment Tree Problem!

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

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
11 лет назад
12

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

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

allllekssssa

11 лет назад, скрыть # |

First is Mo algorithm ...

→ Ответить

Mhammad1

11 лет назад, скрыть # ^ |

Please explain how it can be done by Mo algorithm?

→ Ответить

Archazey

11 лет назад, скрыть # ^ |

← 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

11 лет назад, скрыть # ^ |

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

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

→ Ответить

Archazey

11 лет назад, скрыть # ^ |

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

11 лет назад, скрыть # ^ |

can you please provide some problems that needs Mo algorithm.

→ Ответить

percywtc

11 лет назад, скрыть # ^ |

Yandex.Algorithm 2011 Round 2 Problem D

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

→ Ответить

novitiate

11 лет назад, скрыть # |

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

→ Ответить

Mhammad1

11 лет назад, скрыть # ^ |

← 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

11 лет назад, скрыть # |

+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

11 лет назад, скрыть # ^ |

← 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

→ Ответить

Mhammad1

11 лет назад, скрыть # |

Auto comment: topic has been updated by Mhammad1 (previous revision, new revision, compare).

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 16.10.2026 10:54:29 (f1).

Десктопная версия, переключиться на мобильную.

При поддержке