Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

CFR 86 D. Powerful array ( Mo's Algorithm, Math )

Problem - D - Codeforces題意: 給一個長度為 N 的數列 A[]。T 筆詢問,問對 [ L, R ] 中存在的所有相異數值 s,SUM( K[ s ] * K[ s ] * s ) 是多少。K[ s ] 代表 [ L, R ] 區間中,s 出現的次數。資料規模: First line contains two integers n and t (1 …

CFR 220 B. Little Elephant and Array ( Mo's Algorithm )

Problem - B - Codeforces題意: 給 N 個元素的序列,M 筆詢問,問考慮 A[ L, R ] 有多少不同的數字 A[ x ] 出現恰好 A[ x ] 次。資料規模: The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 1e5) — the size of array a and the…

CFR Educational 2 E. Lomsat gelral ( Smaller to Larger or Time stamp + Mo's Algorithm )

Problem - E - Codeforces The official solution is to simply merge subtrees from the leaves to the root. Using the smaller to larger strategy, where we always merge the smaller subtree towards the larger, the overall time complexity is O( (…

CF 617E XOR and Favorite Number ( Mo's Algorithm )

Problem - E - Codeforces For a range query [ ql, qr ], we are asked to find the number of distinct pairs that XOR to a given number K. Since it is a range XOR problem, we will consider precomputing prefix XOR pa for the original array a. N…

Range Mex

Mex ( minimum excludant ), has an interesting property in game theory, where an sprague grundy value of a state in a fair game can be deduced from the mex of the sg-values of all the states it could reach in the next step.The definition of…

Introduction to Mo's Algorithm

Range Mode Query: http://zerojudge.tw/ShowProblem?problemid=b417 Given N numbers, M queries for ( ql, qr ), output the maximum frequency and the count of the maximum frequency in range [ ql, qr ] of the N numbers. ( 1 <= N <= 1e5, 1 <= M <…