Company: Ivyleague csforall_18oct
Difficulty: medium
Frequency Subarray Updates Problem Description You monitor a long timeline of packet tags. Each second has one tag (an integer). Engineers want to keep some frequency bands "balanced" inside subsegments of the timeline. You are given an integer array `a` of length `n`. You must process `m` operations of two types: Query 1 l r k Find the smallest non-negative integer `T` such that there exist `k` distinct tag values `x_1, ..., x_k` which all appear at least once in the subarray `a[l...r]`, and if `cnt_i` is the number of occurrences of `x_i` inside `a[l...r]`, then |cnt_i - cnt_j| <= T for all 1 <= i, j <= k . If it is impossible to choose `k` distinct values that appear in `a[l...r]`, print -1. Point update 2 p x Set a[p] := x . You must answer every query of the first type. Input The first line contains two integers `n` and `m`. The second line contains `n` integers `a_1, ..., a_n`. Each of the next `m` lines contains an operation in one of the two formats: 1 l r k 2 p x Outp