Find the Different Ones! (Codeforces 1927D)
Tags: Greedy, dsu

You are given an array $$$a$$$ of $$$n$$$ integers, and $$$q$$$ queries.Each query is represented by two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$). Your task is to find, for each query, two indices $$$i$$$ and $$$j$$$ (or determine that they do not exist) such that:  $$$l \le i \le r$$$;  $$$l \le j \le r$$$;  $$$a_i \ne a_j$$$. In other words, for each query, you need to find a pair of different elements among $$$a_l, a_{l+1}, \dots, a_r$$$, or report that such a pair does not exist.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The descriptions of the test cases follow.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the array $$$a$$$.The third line of each test case contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.The next $$$q$$$ lines contain two integers each, $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$) — the boundaries of the query.It is guaranteed that the sum of the values of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$. Similarly, it is guaranteed that the sum of the values of $$$q$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each query, output two integers separated by space: $$$i$$$ and $$$j$$$ ($$$l \le i, j \le r$$$), for which $$$a_i \ne a_j$$$. If such a pair does not exist, output $$$i=-1$$$ and $$$j=-1$$$.You may separate the outputs for the test cases with empty lines. This is not a mandatory requirement.


Sample Inputs:
5
5
1 1 2 1 1
3
1 5
1 2
1 3
6
30 20 20 10 10 20
5
1 2
2 3
2 4
2 6
3 5
4
5 2 3 4
4
1 2
1 4
2 3
2 4
5
1 4 3 2 4
5
1 5
2 4
3 4
3 5
4 5
5
2 3 1 4 2
7
1 2
1 4
1 5
2 4
2 5
3 5
4 5

Sample Outputs:
2 3
-1 -1
1 3

2 1
-1 -1
4 2
4 6
5 3

1 2
1 2
2 3
3 2

1 3
2 4
3 4
5 3
5 4

1 2
4 2
1 3
2 3
3 2
5 4
5 4

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict, deque, Counter
import bisect
t = 1
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    li = [-1]
    temp = 0
    for i in range(1, n):
        if a[i] == a[i - 1]:
            li.append(li[-1])
        else:
            li.append(i - 1)
    q = int(input())
    for i in range(q):
        (l, r) = map(int, input().split())
        if li[r - 1] == -1 or li[r - 1] < l - 1:
            print(-1, -1)
        else:
            print(li[r - 1] + 1, r)

Solution (Python):
from __future__ import annotations
import bisect
import heapq
import math
import sys
from collections import Counter, defaultdict, deque
from copy import deepcopy
from itertools import permutations
from functools import lru_cache
from typing import Iterator
user_input = sys.stdin.readline
sys.setrecursionlimit(2 * 10 ** 9)
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack:
                    break
                to = stack[-1].send(to)
        return to
    return wrappedfunc

def get_int() -> int:
    return int(user_input())

def line_integers() -> list[int]:
    return list(map(int, user_input().split()))

def get_string(as_list: bool=False) -> str | list[str]:
    input_string = user_input()
    if as_list:
        return list(input_string[:len(input_string) - 1])
    else:
        return input_string[:len(input_string) - 1]

def invr() -> Iterator[int]:
    return map(int, user_input().split())

def partitions(partitions_n: int):
    partitions_a = [0 for _ in range(partitions_n + 1)]
    k_ = 1
    y_ = partitions_n - 1
    while k_ != 0:
        x_ = partitions_a[k_ - 1] + 1
        k_ -= 1
        while 2 * x_ <= y_:
            partitions_a[k_] = x_
            y_ -= x_
            k_ += 1
        l_ = k_ + 1
        while x_ <= y_:
            partitions_a[k_] = x_
            partitions_a[l_] = y_
            yield partitions_a[:k_ + 2]
            x_ += 1
            y_ -= 1
        partitions_a[k_] = x_ + y_
        y_ = x_ + y_ - 1
        yield partitions_a[:k_ + 1]
if __name__ == '__main__':
    n_tests: int = get_int()
    for _ in range(n_tests):
        n: int = get_int()
        a: list[int] = line_integers()
        q: int = get_int()
        l: list[int] = []
        r: list[int] = []
        for k in range(q):
            (l_, r_) = invr()
            l.append(l_)
            r.append(r_)
        last_non_equal: list[int] = [-1 for _ in range(n)]
        for k in range(1, n):
            if a[k] != a[k - 1]:
                last_non_equal[k] = k - 1
            else:
                last_non_equal[k] = last_non_equal[k - 1]
        for k in range(q):
            left: int = l[k] - 1
            right: int = r[k] - 1
            if last_non_equal[right] < left:
                print('-1 -1')
            else:
                print(f'{last_non_equal[right] + 1} {right + 1}')
        print(' ')

Solution (Python):
from typing import List

def get_precalculate_left(arr: List[int]):
    p_arr = []
    p_arr.append(-1)
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            p_arr.append(i - 1)
        else:
            p_arr.append(p_arr[-1])
    return p_arr

def solve(p_arr: List[int], l: int, r: int):
    actual_left = p_arr[r - 1]
    if actual_left + 1 >= l:
        print(f'{actual_left + 1} {r}')
    else:
        print(f'-1 -1')
if __name__ == '__main__':
    t = input()
    for i in range(int(t)):
        n = input()
        arr = input().split()
        m = input()
        queries = []
        for j in range(int(m)):
            (l, r) = input().split()
            queries.append((int(l), int(r)))
        p_arr = get_precalculate_left(arr)
        for q in queries:
            solve(p_arr, q[0], q[1])
        print()