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

Hi, let's get straight to the topic.

MO whithout Update

==================

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?.
It's gonna help you to understand Mo's algorithm better.
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.

Powerful array
XOR and Favorite Number
Ann and Books
Little Elephant and Array
Chef and Problems

MO with update

==================

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

Unable to parse markup [type=CF_MATHJAX]

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.

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 :

Task Postering (pla)
Psychos in a Line
Task Little Bird (pta)
These problems aren't necessarily the exact problem but the main idea is same.

I gathered up a lot of Segment problems :) -->

upd1 : more segment :D
upd2 : now there is e-olymp problems. thanks to dmkz.

codeforces :
Xenia and Bit Operations
Knight Tournament
Bash and a Tough Math Puzzle
Pashmak and Parmida's problem
Enemy is weak
Circular RMQ
REQ
Lucky Queries
XOR on Segment
Sereja and Brackets
Ant Colony
Babaei and Birthday Cake
A Simple Task
Frogs and mosquitoes
Copying Data
Lucky Array
Vika and Segments
Misha and Permutations Summation
Little Elephant and Inversions
One Occurrence
Optimize!
Yaroslav and Divisors
TorCoder
New Year Domino
Pillars
On Changing Tree
Infinite Inversions
Interesting Array
Alphabet Permutations
DZY Loves Fibonacci Numbers
Points
Function
Eyes Closed
Tree and Queries
Valera and Queries
Nikita and stack
Linear Kingdom Races
Camping Groups
Little Girl and Problem on Trees
Domino Principle
Water Tree
Propagating tree
Kefa and Watch
Jeff and Removing Periods
Drazil and Morning Exercise
Subsequences
SUM and REPLACE
Tree or not Tree
The Child and Sequence
Encryption (hard)
Hot is Cold
Developing Game
Drazil and Park
Board Game
The Untended Antiquity
Danil and a Part-time Job
More Queries to Array...
Cow Tennis Tournament
Coins Exhibition
Till I Collapse
Editor
Serge and Dining Room
Subarray Sorting
Physical Education Lessons
Alyona and towers
Sasha and Array
New Year and Old Subsequence
Timofey and our friends animals
Souvenirs
Yash And Trees
Legacy
Periodic RMQ Problem
Leha and security system
Vladik and Entertaining Flags
MEX Queries
The Bakery
Nauuo and Bug
Duff in the Army
Fools and Roads

codeforces gym :
Queries
Letter Array
Hacker Cups and Balls
Reflection
Rectangles
Colonial Mansions
Colors Overflow
Running a penitentiary
Subsequence Sum Queries

spoj :

BGSHOOT — Shoot and kill
HORRIBLE — Horrible Queries
GSS1 — Can you answer these queries I
GSS3 — Can you answer these queries IV
GSS5 — Can you answer these queries V
KGSS — Maximum Sum
POSTERS — Election Posters
BRCKTS — Brackets
LITE — Light Switching
KQUERYO — K-Query Online
CNTPRIME — Counting Primes
MULTQ3
IOPC1207 — GM plants
QUERYIT — SLIS
ADACABAA — Ada and Species
DQUERY — D-query
PATULJCI — Snow White and the N dwarfs
ADAGF — Ada and Greenflies
ADATREE — Ada and Trees
Mass Change Queries
PRMQUER — Prime queries
NAJ0001 — Divisible Number Sum
DCEPC11I — Impossible Boss
PERMPATT — Check 1324
THRBL — Catapult that ball
MON2012 — Monkey and apples
GOODE — Good Debugging SBO — MAXIMUM RARITY

lightoj :

1082 — Array Queries
1080 — Binary Simulation
1112 — Curious Robin Hood

e-olymp :
In the Country of Unlearned Lessons
In a country of Unlearned Lessons 2
The kid who learned to count
Investigation by koloboks
Цветик-Семицветик
Cheburashka and Crocodile Gena
Винни-Пух
Винни-Пух 2
Карлсон, который живет на крыше
Ну, погоди!
Three from Prostokvashino
Трое из Простоквашино 2
Трое из Простоквашино 3
Золотой ключик или приключения Буратино
Приключения кота Леопольда
Adventures of Dunno and His Friends
38 попугаев
Возвращение блудного попугая
Сказка о попе и работнике его Балде
Чипполино
you can use google translate for the problems written in russian.

any suggestion ? :D

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/

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

password : abcd

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

https://vjudge.net/contest/323731

any suggestion please comment :))

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

(any suggestion please comment)