Diverse Segments (Codeforces 1684F)
Tags: Others, two pointers

You are given an array $$$a$$$ of $$$n$$$ integers. Also you are given $$$m$$$ subsegments of that array. The left and the right endpoints of the $$$j$$$-th segment are $$$l_j$$$ and $$$r_j$$$ respectively.You are allowed to make no more than one operation. In that operation you choose any subsegment of the array $$$a$$$ and replace each value on this segment with any integer (you are also allowed to keep elements the same).You have to apply this operation so that for the given $$$m$$$ segments, the elements on each segment are distinct. More formally, for each $$$1 \le j \le m$$$ all elements $$$a_{l_{j}}, a_{l_{j}+1}, \ldots, a_{r_{j}-1}, a_{r_{j}}$$$ should be distinct.You don't want to use the operation on a big segment, so you have to find the smallest length of a segment, so that you can apply the operation to this segment and meet the above-mentioned conditions. If it is not needed to use this operation, the answer is $$$0$$$.

Input: The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the size of the array and the number of segments respectively.The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of $$$a$$$.Each of the next $$$m$$$ lines contains two integers $$$l_j$$$, $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — the left and the right endpoints of the $$$j$$$-th segment.It's guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case output a single integer — the smallest length of a segment you can apply an operation on making the elements on all given segments distinct. If it is not needed to use the operation, output $$$0$$$.

Note: In the first test case you can perform the operation on the segment $$$[1, 2]$$$ and make $$$a = [5, 6, 2, 1, 3, 3, 5]$$$. Then the elements on each segment are distinct.  On the segment $$$[1, 4]$$$ there are $$$[5, 6, 2, 1]$$$.  On the segment $$$[4, 5]$$$ there are $$$[1, 3]$$$.  On the segment $$$[2, 4]$$$ there are $$$[6, 2, 1, 3]$$$. This way on each of the given segments all elements are distinct. Also, it is impossible to change any single integer to make elements distinct on each segment. That is why the answer is $$$2$$$.In the second test case the elements on each segment are already distinct, so we should not perform the operation.In the third test case we can replace the first $$$5$$$ by $$$1$$$. This way we will get $$$[1, 7, 5, 6]$$$ where all elements are distinct so on each given segment all elements are distinct.

Sample Inputs:
5
7 3
1 1 2 1 3 3 5
1 4
4 5
2 4
5 2
10 1 6 14 1
4 5
2 4
4 5
5 7 5 6
2 2
1 3
2 4
3 3
3 4
7 3
2 2 2 7 8 2 2
4 4
4 4
5 5
1 1
123
1 1

Sample Outputs:
2
0
1
0
0

Solution (Python):
import sys
from sys import stdin
import heapq
from collections import deque
import random
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
    (n, m) = map(int, stdin.readline().split())
    aa = list(map(int, stdin.readline().split()))
    XOR = random.randint(1, 10 ** 9)
    compdic = {}
    complis = []
    for i in range(n):
        na = XOR ^ aa[i]
        if na not in compdic:
            compdic[na] = 0
            complis.append(na)
    random.shuffle(complis)
    cnt = 0
    for xx in complis:
        compdic[xx] = cnt
        cnt += 1
    a = [compdic[i ^ XOR] for i in aa]
    lr = []
    lind = [[] for i in range(n)]
    rind = [[] for i in range(n)]
    for i in range(m):
        (l, r) = map(int, stdin.readline().split())
        l -= 1
        r -= 1
        lr.append((l, r))
        lind[l].append(i)
        rind[r].append(i)
    enable = [False] * m
    lq = []
    numqueue = {}
    NEWLR = []
    for i in range(n):
        for ind in lind[i]:
            enable[ind] = True
            heapq.heappush(lq, (lr[ind][0], ind))
        while lq and enable[lq[0][1]] == False:
            heapq.heappop(lq)
        if lq:
            nowl = lq[0][0]
        else:
            nowl = None
        if nowl != None and a[i] in numqueue:
            while numqueue[a[i]] and numqueue[a[i]][0] < nowl:
                numqueue[a[i]].popleft()
            if numqueue[a[i]]:
                NEWLR.append((numqueue[a[i]][-1], i))
                NEWLR.append((numqueue[a[i]][0], i))
        else:
            numqueue[a[i]] = deque()
        numqueue[a[i]].append(i)
        for ind in rind[i]:
            enable[ind] = False
    m = len(NEWLR)
    if m == 0:
        ANS.append('0')
        continue
    L = [[] for i in range(n)]
    R = [[] for i in range(n)]
    exist = [False] * m
    cnt = 0
    for tup in NEWLR:
        L[tup[0]].append(cnt)
        R[tup[1]].append(cnt)
        cnt += 1
    allcnt = 0
    ans = n
    LRQ = deque()
    for i in range(n):
        for ind in L[i]:
            exist[ind] = True
            allcnt += 1
            LRQ.append((i, ind))
        for ind in R[i]:
            exist[ind] = False
            LRQ.append((i, None))
        if allcnt == m:
            while LRQ and LRQ[0][1] != None and (exist[LRQ[0][1]] == False):
                LRQ.popleft()
            if LRQ:
                ans = min(ans, i - LRQ[0][0] + 1)
            else:
                ans = min(ans, 1)
    ANS.append(ans)
print('\n'.join(map(str, ANS)))

Solution (Python):
from collections import Counter, defaultdict, deque
import itertools
import re
import math
from functools import reduce
import operator
import bisect
from heapq import *
import functools
mod = 998244353
import sys
import os
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')
INF = 1 << 31

def compress(mylist):
    B = list(set(mylist))
    B.sort()
    D = {v: i for (i, v) in enumerate(B)}
    return list(map(lambda v: D[v], mylist))

def solve():
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    a = compress(a)
    ma = max(a)
    prv = [-1] * (ma + 1)
    cnt = [[] for _ in range(ma + 1)]
    fli = [-1] * n
    now = -1
    for i in range(n):
        if prv[a[i]] == -1:
            prv[a[i]] = i
        else:
            now = max(now, prv[a[i]])
            prv[a[i]] = i
        fli[i] = now
        cnt[a[i]].append(i)
    mi = INF
    chk = [INF] * n
    for _ in range(m):
        (l, r) = map(int, input().split())
        if fli[r - 1] < l - 1:
            continue
        else:
            chk[r - 1] = min(chk[r - 1], l - 1)
            idx = bisect.bisect_left(fli, l - 1)
            mi = min(mi, idx)
    if mi == INF:
        print(0)
        return
    for i in range(n - 1)[::-1]:
        chk[i] = min(chk[i], chk[i + 1])
    ans = n - mi
    for i in range(n - 1)[::-1]:
        idx = bisect.bisect_right(cnt[a[i + 1]], i + 1)
        if idx != len(cnt[a[i + 1]]):
            tmp = chk[cnt[a[i + 1]][idx]]
            if tmp <= i + 1:
                break
        if idx > 1:
            tmp = chk[i + 1]
            midx = bisect.bisect_left(cnt[a[i + 1]], tmp)
            if midx < len(cnt[a[i + 1]]):
                mi = min(mi, cnt[a[i + 1]][midx])
        ans = min(ans, i + 1 - mi)
    print(ans)
    return 0
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
from collections import Counter, defaultdict, deque
import itertools
import re
import math
from functools import reduce
import operator
import bisect
from heapq import *
import functools
mod = 998244353
import sys
import os
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')
import typing

class SegTree:

    def __init__(self, op: typing.Callable[[typing.Any, typing.Any], typing.Any], e: typing.Any, v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e
        if isinstance(v, int):
            v = [e] * v
        self._n = len(v)
        self._log = self._n.bit_length()
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)
        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n
        p += self._size
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n
        return self._d[p + self._size]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        sml = self._e
        smr = self._e
        left += self._size
        right += self._size
        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1
        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def max_right(self, left: int, f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert f(self._e)
        if left == self._n:
            return self._n
        left += self._size
        sm = self._e
        first = True
        while first or left & -left != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not f(self._op(sm, self._d[left])):
                while left < self._size:
                    left *= 2
                    if f(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1
        return self._n

    def min_left(self, right: int, f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= right <= self._n
        assert f(self._e)
        if right == 0:
            return 0
        right += self._size
        sm = self._e
        first = True
        while first or right & -right != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not f(self._op(self._d[right], sm)):
                while right < self._size:
                    right = 2 * right + 1
                    if f(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)
        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
INF = 1 << 31

def compress(mylist):
    B = list(set(mylist))
    B.sort()
    D = {v: i for (i, v) in enumerate(B)}
    return list(map(lambda v: D[v], mylist))

def solve():
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    a = compress(a)
    ma = max(a)
    prv = [-1] * (ma + 1)
    cnt = [[] for _ in range(ma + 1)]
    fli = [-1] * n
    now = -1
    for i in range(n):
        if prv[a[i]] == -1:
            prv[a[i]] = i
        else:
            now = max(now, prv[a[i]])
            prv[a[i]] = i
        fli[i] = now
        cnt[a[i]].append(i)
    mi = INF
    seg = SegTree(min, INF, n)
    for _ in range(m):
        (l, r) = map(int, input().split())
        if fli[r - 1] < l - 1:
            continue
        else:
            tmp = seg.get(r - 1)
            if tmp > l - 1:
                seg.set(r - 1, l - 1)
            idx = bisect.bisect_left(fli, l - 1)
            mi = min(mi, idx)
    if mi == INF:
        print(0)
        return
    ans = n - mi
    for i in range(n - 1)[::-1]:
        idx = bisect.bisect_right(cnt[a[i + 1]], i + 1)
        if idx != len(cnt[a[i + 1]]):
            tmp = seg.prod(cnt[a[i + 1]][idx], n)
            if tmp <= i + 1:
                break
        if idx > 1:
            tmp = seg.prod(i + 1, n)
            midx = bisect.bisect_left(cnt[a[i + 1]], tmp)
            if midx < len(cnt[a[i + 1]]):
                mi = min(mi, cnt[a[i + 1]][midx])
        ans = min(ans, i + 1 - mi)
    print(ans)
    return 0
t = int(input())
for _ in range(t):
    solve()