### Fype's blog

By Fype, 3 years ago, It's one of the most beautiful dp I ever used. I'm going to explain it with an example.

Problem: 1265E

Solution: suppose $e_i$ equals the expected number of days that we stop.
$e_i = p_i * e_{i + 1} + (1 - p_i) * e_1 + 1$
$e_n = (1 - p_i) * e_1 + 1$

So how to update $e$?! :D
We will change how we show numbers. You know how we show complex numbers (if you don't learn it here), we are going to use the same idea.
Each number consists a part that is $e_1$ and another part that is a Real number(in this problem you can change it to integer when using modulo).
We show each number with $x$ and $y$ such that the number is equal to $x * e_1 + y$. So we use this idea and start updating $e$ backward.
Then we will get $e_1 = x * e_1 + y$ and now we can get $e_1$ as an intiger.
$e_1 = y / (1 - x)$

Any other problem that uses the same idea, please mention. :D #dp,
By Fype, 3 years ago, Hi, let's get straight to the topic.

#### ==================

Problem : given an array a of size n. you are given q queries and in each queries you are given two intigers l and r (${l \le r}$) and you are supposed to print the sum of ${a_l}, {a_{l + 1}}, ..., {a_r}$.
Very easy huh?
First, let's solve it with time complexity $O(q * n)$. why?.
suppose we have a start pointer and an end pointer on the array and a value cur such that cur is equal to the sum of segment $[start, end]$, now we for each query, we are going to reach r with end and reach l with start and change cur such that after reaching both start and end to l and r, cur will be equal to the sum of segment $[l, r]$.

suppose $end < r$ : we can change end to end + 1 and update cur, just add $a_{end + 1}$ to cur.

We can use the same method to decrease end and change start and now we have an algorithm of complexity $O(n * q)$. what if for each query we know that given r will be bigger or equal than the r given before. total complexity will still be $O(n * q)$ but total changes of end will be $O(n)$ and that's good. even if queries didn't give us r in increasing order we could always sort queries base on their r.

now for decreasing the total changes of start what can we do?
let's decompose a to blocks of size S. what if we sort the queries such that for queries in each block have increasing r (You can see HERE for exact sorting method). let's calculate time complexity.

For the i-th block suppose we change end at most $O(n)$ times, so total changes of end will be $O((n / S) * n)$.
Suppose we have $q_i$ queries that have l in the i-th block.
For the i-th block, we change start at most $O(q_i * S)$. so total changes of start will be $O(S * q)$.
We do $O((n / S) * n + S * q)$. with $S = n / \sqrt q$ we get $O(n * \sqrt q)$ and that's really good. now you can apply the method described here with problems that are much harder and good luck.

I suggest before reading Mo with update, you solve some of the problems below.

#### ==================

Problem : The same problem before with diffrence that we have change query. You are given pos and $val$ and that means you have to change $a_{pos}$ to $val$.

What will happen if we use the same method that we used above? We get time complexity $O(q * n * \sqrt(q))$ because before each query we have to do some updates or undo some updates.
That's not good enough. Here is the main idea for what we will do:

Decompose array into blocks of size S.(pretty similar to the last one huh?) and sort queries that ask for some sum, firstly based on the block which l lies in and secondly by the block that r lies in and finally by t. t is the number of the update queries before this query.

now let's calculate the time complexity :

total changes of the start: for the i-th block that l lies in it, the start will change $O(q_i * S)$ ($q_i$ have the same definition as before). So total changes of the start will be $O(S * q)$.
total changes of the end: for the i-th that l lies in it, and for the j-th block that r lies in it, the end changes will be $O(q'_{i, j} * S)$. ($q'_{i, j}$ is number of queries that l of them lies in block i and r of them lies in block j). So the total change of the end for a fixed block for l is $O(S * q)$.
Changes of the end when changing between blocks of l is $O(n)$ and therefore we get total changes between blocks of the end is $O({n ^ 2} / S)$. So the total change will be $O(S * q + {n ^ 2} / S)$.
total updates we have to do and we have undo: because for the i-th block of l and the j-th block of r, t is in increasing order the total changes of t for these two fixed blocks is $O(q * {n ^ 2} / {S ^ 2})$.

TOTAL COMPLEXITY: from above we get total complexity of $O(S * q + S * q + {n ^ 2} / S + q * {n ^ 2} / {S ^ 2})$ and that is equivalent to $O(S * q + q * {n ^ 2} / {S ^ 2})$, If $S = {n ^ {2 / 3}}$ we get $O(q * n ^ {2 / 3})$.

FACT : with S = $(2 * n ^ 2) ^ {1 / 3}$ you will get best complexity.

Here is some problems (Sorry I didn't find many :) ) :
Primitive Queries
Machine Learning (rip)
Candy Park
Any suggestion or problem, please comment :D. By Fype, 3 years ago, Problem : You have an array a of size $n$. for each $i$ (${i \le n}$) you have to find maximum $j$ such that ${1 \le j < i}$ and ${a_j > a_i}$ and if there is no $j$, consider the answer for $i$ equal to $0$, solve the problem with total complexity ${O(n)}$.

Solution 1 : Of course there is an easy solution using stack.

for (int i = 1; i <= n; i++) {
while (s.size() && a[s.top()] <= a[i])
s.pop();
if (s.size())
L[i] = s.top();
s.push(i);
}


Solution 2 : About 2-3 month ago I suggested a dp solution for this problem and i never thought that it would be ${O(n)}$ but here I am sharing it with you :D
${dp_i = }$ answer for i.
So how can we update this dp?!, let's check maximum $j$ that can be the answer for $dp_i$. It's obvious that if ${a_{i - 1} > a_i}$ the answer is $i - 1$.
what if ${a_{i - 1} \le a_i}$ : then the answer isn't in range $(dp_{i - 1}, i]$ so the next number we should check is $dp_{i - 1}$ and if it wasn't answer that we need we should check $dp_{dp_{i - 1}}$, and then $dp_{dp_{dp_{i - 1}}}$ and so on.
Do you see the pattern?! :D

int find_ans(int i, int j) {
if (!j)
return j;
return (a[j] > a[i]? j: find_ans(i, dp[j]));
}
for (int i = 1; i <= n; i++)
dp[i] = find_ans(i, i - 1);


some problems :

Psychos in a Line
These problems aren't necessarily the exact problem but the main idea is same. #dp,
By Fype, 3 years ago,  By Fype, 4 years ago, Hello again :D

Here is my DSU struct in c++ because there isn't any in codeforces. I added some features like making a DSU equal to another or clearing DSU.

use it like :

DSU tmp(n);

Any suggestion comment below :D

UPD1 : I added more features

UPD2 : Now you can merge two DSUs. (like if you want to add every edge in graph A to graph B) https://paste.ubuntu.com/p/Xz3BNBGcN4/ #dsu,
By Fype, history, 4 years ago, Hi, From the first that i started CP i always liked problems that could be solved with some random in it, so i searched a lot but didn't find a random problemset.

now i'm making one :D

https://vjudge.net/contest/323610

UPD1: so after adding many problems the last problemset got filled so here more problems. :D

https://vjudge.net/contest/323731 By Fype, 4 years ago, Here is my bigint struct in c++.

https://paste.ubuntu.com/p/Kb2Cwtk6Bg/ (new link is available)


enjoy it :))

upd1 : I added bitwise operator and shift. here is new link.

https://paste.ubuntu.com/p/FdxZ3QMG9h/


upd2 : I added popcount, ctz and tutorial to how to use change base function :D.

you can use the new code below :

https://paste.ubuntu.com/p/ZcMgDhvRhv/

upd3 : I fixed a bug found by WhaleVomit (thanks for noticing). This new code uses more memory. If you wanted to reduce the memory usage, you can use the previous version and you can use .normalize() function on each variable before each operation. It helps a little and the normalize function is of $O(n)$ where $n$ is the number of digits of the number you are using normalize on.

you can use the new code below :

https://paste.ubuntu.com/p/dzDJHqp5bf/

https://github.com/AriaAshrafi/BigInt/blob/main/BigInt.cpp 