Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

FairyWinx's blog

By FairyWinx, 3 months ago, translation, In English

The following task is given: an array of integer $$$a_1, \ldots, a_n$$$ is given, as well as $$$q$$$ queries of one of two types:

  1. $$$a_i+=x$$$, where $$$l \leq i \leq r$$$.
  2. find out the number of indexes $$$i$$$, where $$$l\leq i\leq r$$$ and $$$a_j < a_i$$$, for all $$$j:$$$ $$$l \le j < i$$$. (Or humanly — the number of prefix maxima on the segment)

We want to solve this faster than for $$$O(sqrt(n))$$$ per request.

Let's consider an easier option when we don't have change requests. Then we can make a just Segment Tree, where a sorted list of prefix maxima is stored at the vertex, if our segment is the segment corresponding to the vertex of the segment tree. Then we should just make an algorithm, anological Merge Sort Tree, only we should consider the vertices into which we split the query from left to right and store the maximum among the previous elements on a suitable segment, and add to the answer the number of elements in the vertex larger than the maximum before, and then update the maximum.

It works for $$$O(log(n)^2)$$$ per request, as well as $$$O(n log(n))$$$ memory and time to build.


Note that this can be redone so that there are change requests. Then we only need to learn how to combine such lists and add value to them. And for this, for example, a persistent treap is suitable. Then we will store a persistent treap of all prefix maxima at the vertex. Then, when updating, if the vertex segment lies completely inside the query, then we will simply add the desired value to our treap (well, of course, we will push this value down). And to combine the lists, you just need to copy the values from the left subtree, and also select the desired suffix from the right subtree and copy it as well, and then combine these trees.

This already works for $$$O(log(n)^2)$$$ per request, but in this case there will be build for $$$O(nlog(n)^2)$$$, and, most importantly, memory will be $$$O((n +q)log(n)^2)$$$ at total.


Now the normal solution is for $$$O(n)$$$ memory and $$$O(log(n)^2)$$$ per request.

Let there be a just tree segment (the vertex $$$v$$$ has a left subtree — this is $$$v.l$$$, and the right one is $$$v.r$$$), then let us, for each vertex $$$v$$$, learn to count two values $$$cnt_v$$$ — the number of prefix maxima, if our segment is the segment corresponding to the vertex $$$v$$$, and $$$max_v$$$ is the maximum on the same segment.

Then we implement the function $$$f(v, x)$$$, which will count the number of prefix maxima of strictly large $$$x$$$ on the segment of the vertex $$$v$$$.

We have only three cases:

  1. If $$$v$$$ is a leaf, then everything is simple, you need to compare the value of this element with $$$x$$$.
  2. If $$$x\geq max_{v.l}$$$, then note that there are no exactly finding elements in the left subtree (since they are less than or equal to $$$x$$$), then we are only interested in the right subtree, that is, $$$f(v, x) = f(v.r, x)$$$.
  3. If $$$x <max_{v.l}$$$, then we are no longer interested in the value of $$$f(v.r, x)$$$, since the element with the value $$$max_{v.l}$$$ will definitely be among in the prefix maxima, so the number of prefix maxima on the right will be the same as and in the absence of a limit on $$$x$$$, and we already know this number — this is $$$cnt_v - cnt_{v.l}$$$, since we need the number of maxima on the right, and that's all except those on the left (logical, isn't it) (and it's not $$$cnt_{v.l}$$$, since in this case there may be elements less than $$$max_{v.l}$$$). So $$$f(v, x) = f(v.l, x) + cnt_v - cnt_{v.l}$$$.

This function works for $$$O(log(n))$$$, since each time we descend into exactly one subtree, and the depth of the tree of segments is just the logarithm.

It is clear that it is easy to solve the problem with this function, we can solve the problem, just like in the first case, only we will need to do not $$$lowerbound$$$ according to the list, but simply run this function. Building and the like is also trivial with this function. (All the subtleties can be found in the code)

implementation

Also thanks to Um_nik, who, in fact, came up with the last solution in a problem that boiled down to this and made it much more interesting)))

As well as examples of tasks for this technique 1, 2.

Read more »

 
 
 
 
  • Vote: I like it
  • +140
  • Vote: I do not like it

By FairyWinx, 5 months ago, translation, In English

Task A. Idea FairyWinx

Hint 1
Hint 2
Solution
Code

Задача B. Idea FairyWinx

Hint 1
Hint 2
Solution
Code

Задача C. Idea FairyWinx

Hint 1
Hint 1
Hint 2
Solution
Code

Задача D. Idea FairyWinx

An important fact
Hint 1.1
Hint 1.2
Hint 1.3
Solution 1
Code
Hint 2.1
Solution 2 (which almost everyone wrote)
Реализация

Задача E. Idea FairyWinx

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Реализация

Задача F. Idea Igorbunov

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Реализация

Read more »

 
 
 
 
  • Vote: I like it
  • +81
  • Vote: I do not like it

By FairyWinx, 5 months ago, translation, In English

Привки, Кодефорсес (ノ◕ヮ◕)ノ*:・゚✧

(Hello, Codeforces on Russian)

Igorbunov and I are happy to invite you to participate in Codeforces Round #777 (Div. 2), all the tasks of which will be about a little girl Madoka. It will take place on Mar/11/2022 17:35 (Moscow time). The round will be rated for all participants with rating strictly lower than 2100. You will have 2 hours to solve 6 problems.

I would also like to express my gratitude to the following people:

I wish you high rating, and I also hope that I will help you to distract from bad news at least a little ( ❤ ω ❤ )

Scoring distribution: 500 — 1250 — 1500 — 2000 —2500 — 3000

UPD1: Editorial

UPD2: Congratulations to the contest winners

Div 1+2

1 MiracleFaFa 9457
2 Geothermal 9219
3 rainboy 8649
4 I_Love_LE 8529
5 kshitij_sodani 8250

Div 2

1 shnirelman 6955
2 zzfzzfzzfzzf 6558
3 Kaname-Madoka 6539
4 peuch 6317
5 rsy 6301

Read more »

 
 
 
 
  • Vote: I like it
  • +808
  • Vote: I do not like it

By FairyWinx, history, 20 months ago, In English

Fun fact one: Another account can liked comment in draft block, and it will get contribution.

Fun fact two: in one-two hour considred real contribution on comment/post from like.

And i'm conducted an experiment: call different color, and we put like on comment. And now i can tell: Blue get 3 contribution. Purple get 5 contribution. Yellow (2100-2299) get 8 contribution. Red (2400-2599) get 10 contribution. I don't know, this considered from now rating or max rating, and i don't get information for another color.

Read more »

 
 
 
 
  • Vote: I like it
  • +223
  • Vote: I do not like it