Optimal Subsequences (Hard Version) (Codeforces 1227D2)
Tags: Greedy, data structures

This is the harder version of the problem. In this version, $$$1 \le n, m \le 2\cdot10^5$$$. You can hack this problem if you locked it. But you can hack the previous problem only if you locked both problems.You are given a sequence of integers $$$a=[a_1,a_2,\dots,a_n]$$$ of length $$$n$$$. Its subsequence is obtained by removing zero or more elements from the sequence $$$a$$$ (they do not necessarily go consecutively). For example, for the sequence $$$a=[11,20,11,33,11,20,11]$$$:  $$$[11,20,11,33,11,20,11]$$$, $$$[11,20,11,33,11,20]$$$, $$$[11,11,11,11]$$$, $$$[20]$$$, $$$[33,20]$$$ are subsequences (these are just some of the long list);  $$$[40]$$$, $$$[33,33]$$$, $$$[33,20,20]$$$, $$$[20,20,11,11]$$$ are not subsequences. Suppose that an additional non-negative integer $$$k$$$ ($$$1 \le k \le n$$$) is given, then the subsequence is called optimal if:  it has a length of $$$k$$$ and the sum of its elements is the maximum possible among all subsequences of length $$$k$$$;  and among all subsequences of length $$$k$$$ that satisfy the previous item, it is lexicographically minimal. Recall that the sequence $$$b=[b_1, b_2, \dots, b_k]$$$ is lexicographically smaller than the sequence $$$c=[c_1, c_2, \dots, c_k]$$$ if the first element (from the left) in which they differ less in the sequence $$$b$$$ than in $$$c$$$. Formally: there exists $$$t$$$ ($$$1 \le t \le k$$$) such that $$$b_1=c_1$$$, $$$b_2=c_2$$$, ..., $$$b_{t-1}=c_{t-1}$$$ and at the same time $$$b_t<c_t$$$. For example:  $$$[10, 20, 20]$$$ lexicographically less than $$$[10, 21, 1]$$$,  $$$[7, 99, 99]$$$ is lexicographically less than $$$[10, 21, 1]$$$,  $$$[10, 21, 0]$$$ is lexicographically less than $$$[10, 21, 1]$$$. You are given a sequence of $$$a=[a_1,a_2,\dots,a_n]$$$ and $$$m$$$ requests, each consisting of two numbers $$$k_j$$$ and $$$pos_j$$$ ($$$1 \le k \le n$$$, $$$1 \le pos_j \le k_j$$$). For each query, print the value that is in the index $$$pos_j$$$ of the optimal subsequence of the given sequence $$$a$$$ for $$$k=k_j$$$.For example, if $$$n=4$$$, $$$a=[10,20,30,20]$$$, $$$k_j=2$$$, then the optimal subsequence is $$$[20,30]$$$ — it is the minimum lexicographically among all subsequences of length $$$2$$$ with the maximum total sum of items. Thus, the answer to the request $$$k_j=2$$$, $$$pos_j=1$$$ is the number $$$20$$$, and the answer to the request $$$k_j=2$$$, $$$pos_j=2$$$ is the number $$$30$$$.

Input: The first line contains an integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — the length of the sequence $$$a$$$.The second line contains elements of the sequence $$$a$$$: integer numbers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).The third line contains an integer $$$m$$$ ($$$1 \le m \le 2\cdot10^5$$$) — the number of requests.The following $$$m$$$ lines contain pairs of integers $$$k_j$$$ and $$$pos_j$$$ ($$$1 \le k \le n$$$, $$$1 \le pos_j \le k_j$$$) — the requests.

Output: Print $$$m$$$ integers $$$r_1, r_2, \dots, r_m$$$ ($$$1 \le r_j \le 10^9$$$) one per line: answers to the requests in the order they appear in the input. The value of $$$r_j$$$ should be equal to the value contained in the position $$$pos_j$$$ of the optimal subsequence for $$$k=k_j$$$.

Note: In the first example, for $$$a=[10,20,10]$$$ the optimal subsequences are:   for $$$k=1$$$: $$$[20]$$$,  for $$$k=2$$$: $$$[10,20]$$$,  for $$$k=3$$$: $$$[10,20,10]$$$. 

Sample Inputs:
3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3

7
1 2 1 3 1 2 1
9
2 1
2 2
3 1
3 2
3 3
1 1
7 1
7 7
7 4

Sample Outputs:
20
10
20
10
20
10

2
3
2
3
2
3
1
1
3

Solution (Python):
def init(n):
    vals = [[1] * n]
    d = 10
    while d < n:
        (m, r) = (n // d, n % d)
        vals.append([d] * m + ([r] if r > 0 else []))
        d *= 10
    return vals

def dec(vals, x):
    for val in vals:
        val[x] -= 1
        x //= 10

def find(vals, pos):
    (i, j, res) = (0, len(vals) - 1, 0)
    while True:
        val = vals[j]
        while res + val[i] < pos:
            res += val[i]
            i += 1
        if j == 0:
            return i
        i *= 10
        j -= 1
import sys

def main():
    numre = [int(x) for x in sys.stdin.read().split()]
    n = numre[0]
    a = numre[1:n + 1]
    m = numre[n + 1]
    queries = {}
    for i in range(n + 2, n + 2 + 2 * m, 2):
        (k, pos) = (numre[i], numre[i + 1])
        if k in queries:
            queries[k][pos] = None
        else:
            queries[k] = {pos: None}
    b = sorted([(s, -i) for (i, s) in enumerate(a)])
    tr = init(n)
    siz = n
    for (_, i) in b:
        if siz in queries:
            for pos in queries[siz]:
                queries[siz][pos] = find(tr, pos)
        dec(tr, -i)
        siz -= 1
    for i in range(n + 2, n + 2 + 2 * m, 2):
        (k, pos) = (numre[i], numre[i + 1])
        print(a[queries[k][pos]])
main()

Solution (Python):
import math
import random
import time
from decimal import *
from collections import defaultdict
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound

class FenwickTree:

    def __init__(self, x):
        bit = self.bit = list(x)
        size = self.size = len(bit)
        for i in range(size):
            j = i | i + 1
            if j < size:
                bit[j] += bit[i]

    def update(self, idx, x):
        """"""
        while idx < self.size:
            self.bit[idx] += x
            idx |= idx + 1

    def __call__(self, end):
        """"""
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x

    def find_kth(self, k):
        """"""
        idx = -1
        for d in reversed(range(self.size.bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < self.size and self.bit[right_idx] <= k:
                idx = right_idx
                k -= self.bit[idx]
        return (idx + 1, k)

class SortedList:
    block_size = 700

    def __init__(self, iterable=()):
        self.macro = []
        self.micros = [[]]
        self.micro_size = [0]
        self.fenwick = FenwickTree([0])
        self.size = 0
        for item in iterable:
            self.insert(item)

    def insert(self, x):
        i = lower_bound(self.macro, x)
        j = upper_bound(self.micros[i], x)
        self.micros[i].insert(j, x)
        self.size += 1
        self.micro_size[i] += 1
        self.fenwick.update(i, 1)
        if len(self.micros[i]) >= self.block_size:
            self.micros[i:i + 1] = (self.micros[i][:self.block_size >> 1], self.micros[i][self.block_size >> 1:])
            self.micro_size[i:i + 1] = (self.block_size >> 1, self.block_size >> 1)
            self.fenwick = FenwickTree(self.micro_size)
            self.macro.insert(i, self.micros[i + 1][0])

    def pop(self, k=-1):
        (i, j) = self._find_kth(k)
        self.size -= 1
        self.micro_size[i] -= 1
        self.fenwick.update(i, -1)
        return self.micros[i].pop(j)

    def __getitem__(self, k):
        (i, j) = self._find_kth(k)
        return self.micros[i][j]

    def count(self, x):
        return self.upper_bound(x) - self.lower_bound(x)

    def __contains__(self, x):
        return self.count(x) > 0

    def lower_bound(self, x):
        i = lower_bound(self.macro, x)
        return self.fenwick(i) + lower_bound(self.micros[i], x)

    def upper_bound(self, x):
        i = upper_bound(self.macro, x)
        return self.fenwick(i) + upper_bound(self.micros[i], x)

    def _find_kth(self, k):
        return self.fenwick.find_kth(k + self.size if k < 0 else k)

    def __len__(self):
        return self.size

    def __iter__(self):
        return (x for micro in self.micros for x in micro)

    def __repr__(self):
        return str(list(self))

def binary_search(vector, valoarea):
    left = 0
    right = len(vector) - 1
    while left <= right:
        centru = (left + right) // 2
        if vector[centru] < valoarea:
            left = centru + 1
        else:
            right = centru - 1
    return left

def main():
    answ = []
    pp = 10 ** 9
    restul = 1000000007
    for gg in range(1):
        n = int(input())
        vector = list(map(int, input().split()))
        q = int(input())
        copie = vector.copy()
        tupla = []
        for i in range(q):
            (k, pos) = list(map(int, input().split()))
            tupla.append((k, pos - 1, i))
        tupla = sorted(tupla, key=lambda x: x[0])
        answ = []
        vector_sortat = []
        for i in range(n):
            vector_sortat.append((vector[i], i))
        vector_sortat = sorted(vector_sortat, key=lambda x: [x[0], -x[1]])[::-1]
        lista = SortedList()
        k = 0
        for i in range(q):
            to = tupla[i][0]
            for j in range(k, to):
                lista.insert(vector_sortat[j][1])
            k = to
            answ.append((tupla[i][2], copie[lista[tupla[i][1]]]))
        answ = sorted(answ, key=lambda x: x[0])
        for j in answ:
            print(j[1])
main()

Solution (Python):
WIDTH = 10

def index_tree(n):
    levels = [[1] * n]
    size = WIDTH
    while size < n:
        (m, r) = (n // size, n % size)
        levels.append([size] * m + ([r] if r > 0 else []))
        size *= WIDTH
    return levels

def dec_index(levels, i):
    for level in levels:
        level[i] -= 1
        i //= WIDTH

def find_pos(levels, pos):
    (i, l) = (0, len(levels) - 1)
    total = 0
    while True:
        level = levels[l]
        while total + level[i] < pos:
            total += level[i]
            i += 1
        if l == 0:
            return i
        i *= WIDTH
        l -= 1
import sys

def main():
    numbers = [int(x) for x in sys.stdin.read().split()]
    n = numbers[0]
    sequence = numbers[1:n + 1]
    m = numbers[n + 1]
    queries = {}
    for i in range(n + 2, n + 2 + 2 * m, 2):
        (k, pos) = (numbers[i], numbers[i + 1])
        if k in queries:
            queries[k][pos] = None
        else:
            queries[k] = {pos: None}
    sequence1 = sorted([(s, -i) for (i, s) in enumerate(sequence)])
    tree = index_tree(n)
    size = n
    for (_, neg_i) in sequence1:
        if size in queries:
            for pos in queries[size]:
                queries[size][pos] = find_pos(tree, pos)
        dec_index(tree, -neg_i)
        size -= 1
    for i in range(n + 2, n + 2 + 2 * m, 2):
        (k, pos) = (numbers[i], numbers[i + 1])
        print(sequence[queries[k][pos]])
main()