0w1

Mo's Algorithm

HR Nominating Group Leaders ( Mo's Algorithm, Sqrt Decomposition )

Programming Problems and Competitions :: HackerRank題意: N 個人排成一排,每個人對人投一個票。Q 筆詢問,問 [ L, R ] 中,是否有恰好得到 X 票的人,如果有,輸出其中編號最小的。制約: 1 ≤ T ≤ 5 1 ≤ N, Q ≤ 1e5 N 的總和和 Q 的總和不超過 3e5。解…

HE Dexter's Random Generator ( LCA, Persistent, Trie, XOR or Mo's ( TLE ) )

Dexter's Random Generator | Trie (Keyword Tree) & Data Structures Practice Problems | HackerEarth題意: 給一棵節點帶權的樹。每次詢問一條路徑,問路徑其中一個端點和路徑中任意節點的最大 XOR 值是多少。制約: 1 ≤ N, Q ≤ 1e5 1 ≤ A[ i ] ≤ 1e9解法…

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 <…