Cut and Stick (Codeforces 1514D)
Tags: Greedy, binary search

Baby Ehab has a piece of Cut and Stick with an array $$$a$$$ of length $$$n$$$ written on it. He plans to grab a pair of scissors and do the following to it:  pick a range $$$(l, r)$$$ and cut out every element $$$a_l$$$, $$$a_{l + 1}$$$, ..., $$$a_r$$$ in this range;  stick some of the elements together in the same order they were in the array;  end up with multiple pieces, where every piece contains some of the elements and every element belongs to some piece. More formally, he partitions the sequence $$$a_l$$$, $$$a_{l + 1}$$$, ..., $$$a_r$$$ into subsequences. He thinks a partitioning is beautiful if for every piece (subsequence) it holds that, if it has length $$$x$$$, then no value occurs strictly more than $$$\lceil \frac{x}{2} \rceil$$$ times in it.He didn't pick a range yet, so he's wondering: for $$$q$$$ ranges $$$(l, r)$$$, what is the minimum number of pieces he needs to partition the elements $$$a_l$$$, $$$a_{l + 1}$$$, ..., $$$a_r$$$ into so that the partitioning is beautiful.A sequence $$$b$$$ is a subsequence of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deleting some (possibly zero) elements. Note that it does not have to be contiguous.

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 3 \cdot 10^5$$$) — the length of the array $$$a$$$ and the number of queries.The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n}$$$ ($$$1 \le a_i \le n$$$) — the elements of the array $$$a$$$.Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the range of this query.

Output: For each query, print the minimum number of subsequences you need to partition this range into so that the partitioning is beautiful. We can prove such partitioning always exists.

Note: In the first query, you can just put the whole array in one subsequence, since its length is $$$6$$$, and no value occurs more than $$$3$$$ times in it.In the second query, the elements of the query range are $$$[3,2,3,3]$$$. You can't put them all in one subsequence, since its length is $$$4$$$, and $$$3$$$ occurs more than $$$2$$$ times. However, you can partition it into two subsequences: $$$[3]$$$ and $$$[2,3,3]$$$.

Sample Inputs:
6 2
1 3 2 3 3 2
1 6
2 5

Sample Outputs:
1
2

Solution (Python):
""""""

def main():
    (n, q) = readIntArr()
    a = readIntArr()
    indexes = [[] for _ in range(max(a) + 1)]
    prefix_bit_cnts = [0] * (n * 19)
    for (i, x) in enumerate(a):
        indexes[x].append(i)
        for bit in range(19):
            if x & 1 << bit > 0:
                prefix_bit_cnts[bit * n + i] = 1
    for i in range(1, n):
        for bit in range(19):
            prefix_bit_cnts[bit * n + i] += prefix_bit_cnts[bit * n + i - 1]

    def query_bit_cnt(l, r, bit):
        ans = prefix_bit_cnts[bit * n + r]
        if l - 1 >= 0:
            ans -= prefix_bit_cnts[bit * n + l - 1]
        return ans

    def query_x_cnt(l, r, x):
        if x >= len(indexes):
            return 0
        arr = indexes[x]
        arrn = len(arr)
        (lo, hi) = (-1, arrn - 1)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if arr[mid] < l:
                lo = mid
            else:
                hi = mid - 1
        left = lo
        (lo, hi) = (-1, arrn - 1)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if arr[mid] <= r:
                lo = mid
            else:
                hi = mid - 1
        right = lo
        return right - left

    def calc_segments(cnt, gap):
        ans = max(1, gap - 2 * (gap - cnt))
        return ans
    ans = []
    for _ in range(q):
        (l, r) = readIntArr()
        l -= 1
        r -= 1
        gap = r - l + 1
        most_common_element = 0
        for bit in range(19):
            if query_bit_cnt(l, r, bit) * 2 >= gap:
                most_common_element |= 1 << bit
        cnt = query_x_cnt(l, r, most_common_element)
        segments = calc_segments(cnt, gap)
        ans.append(segments)
    multiLineArrayPrint(ans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_right, bisect_left
from random import randrange
mod = 10 ** 9 + 7
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
d = [[] for _ in range(n + 1)]
for (i, v) in enumerate(a):
    d[v].append(i + 1)
s = [randrange(10 ** 7) for __ in range(23)]
for _ in range(q):
    (l, r) = map(int, input().split())
    tot = r - l + 1
    ans = 0
    ck = set()
    for j in s:
        i = a[j % (r - l + 1) + l - 1]
        if len(d[i]) <= (r - l) // 2 + 1 or i in ck:
            continue
        ck.add(i)
        rig = bisect_right(d[i], r)
        lef = bisect_left(d[i], l)
        if rig - lef > (r - l) // 2 + 1:
            ans = rig - lef
            break
        tot -= rig - lef
        if tot <= (r - l) // 2 + 1:
            break
    if ans:
        print(2 * ans - r + l - 1)
    else:
        print(1)

Solution (Python):
""""""

def test_generator(n, q, a_max):
    from random import randint
    a = [randint(1, a_max) for _ in range(n)]
    queries = [tuple(sorted([randint(0, n - 1) for _ in range(2)])) for __ in range(q)]
    return (a, queries)

def test_solutions_correctness(n, q, a, queries):
    solutions = solve(n, q, a, queries)
    from collections import Counter
    for i in range(q):
        (l, r) = queries[i]
        max_cnt = 0
        cnt = Counter()
        for j in range(l, r + 1):
            cnt[a[j]] += 1
            max_cnt = max(max_cnt, cnt[a[j]])
        gap = r - l + 1
        for n_seg in range(1, max_cnt + 1):
            if max_cnt - (n_seg - 1) <= ceil((gap - (n_seg - 1)) / 2):
                min_n_seg = n_seg
                break
        if min_n_seg != solutions[i]:
            print(f'a={a} queries={queries} i={i} min_n_seg={min_n_seg} solution={solutions[i]}')
            raise Exception('Wrong answer')
    print(f'Solution Ok.')

def test_solution_time(n, q, a, queries):
    from datetime import datetime
    start = datetime.now()
    solutions = solve(n, q, a, queries)
    end = datetime.now()
    print(f'Time={end - start}')

def run_tests():
    for _ in range(10):
        (n, q) = (10, 10)
        (a, queries) = test_generator(n, q, 2)
        test_solutions_correctness(n, q, a, queries)
        (a, queries) = test_generator(n, q, 10)
        test_solutions_correctness(n, q, a, queries)
        (n, q) = (300000, 300000)
        (a, queries) = test_generator(n, q, 2)
        test_solution_time(n, q, a, queries)
        (a, queries) = test_generator(n, q, 100)
        test_solution_time(n, q, a, queries)
        (a, queries) = test_generator(n, q, 300000)
        test_solution_time(n, q, a, queries)

def solve(n, q, a, queries):
    guess_cnt = 40
    positions = [[] for _ in range(max(a) + 1)]
    query_order = list(range(q))
    query_order.sort(key=lambda i: queries[i][1])
    solutions = [-1] * q
    R = -1
    for i_q in query_order:
        (l, r) = queries[i_q]
        while R + 1 <= r:
            R += 1
            positions[a[R]].append(R)
        gap = r - l + 1
        if gap == 1:
            solutions[i_q] = 1
            continue
        guess_cnt2 = min(guess_cnt, gap)
        delta = (gap - 1) / (guess_cnt2 - 1)
        i = l
        ans = 1
        min_cnt = ceil(gap / 2) + 1
        while i <= r:
            x = a[floor(i)]
            arr = positions[x]
            m = len(arr)
            if min_cnt <= m and arr[m - min_cnt] >= l:
                (lo, hi) = (-1, m - 1)
                while lo < hi:
                    mid = (lo + hi + 1) // 2
                    if arr[mid] < l:
                        lo = mid
                    else:
                        hi = mid - 1
                cnt = m - lo - 1
                ans = gap - 2 * (gap - cnt)
                break
            i += delta
        solutions[i_q] = ans
    return solutions

def main():
    (n, q) = readIntArr()
    a = readIntArr()
    queries = []
    for _ in range(q):
        (l, r) = readIntArr()
        l -= 1
        r -= 1
        queries.append((l, r))
    solutions = solve(n, q, a, queries)
    multiLineArrayPrint(solutions)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()