Optimal Subsequences (Hard Version) (Codeforces 1262D2)
Tags: Greedy, binary search

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):
import sys
import heapq
from collections import deque
import copy
input = sys.stdin.readline
INF = 10 ** 9
n = int(input())
bit = [0] * (n + 10)

def bit_init():
    for i in range(1, n):
        if i + (i & -i) > n:
            continue
        bit[i + (i & -i)] += bit[i]

def bit_add(x, w):
    while x <= n:
        bit[x] += w
        x += x & -x

def bit_sum(x):
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= x & -x
    return ret
bit_init()
a = [int(item) for item in input().split()]
m = int(input())
query = [[] for _ in range(n + 1)]
for i in range(m):
    (k, pos) = [int(item) for item in input().split()]
    query[k].append((i, pos))
aa = []
for (i, item) in enumerate(a):
    aa.append((item, -i))
aa.sort(reverse=True)
ans = [0] * m
k = 0
for i in range(n):
    a_id = -aa[i][1]
    bit_add(a_id + 1, 1)
    k += 1
    if len(query[k]) > 0:
        for (index, val) in query[k]:
            l = 0
            r = n + 1
            while r - l > 1:
                mid = (l + r) // 2
                if bit_sum(mid) < val:
                    l = mid
                else:
                    r = mid
            ans[index] = a[r - 1]
for item in ans:
    print(item)

Solution (Python):
from bisect import bisect_right, bisect_left

class BITbisect:

    def __init__(self, InputProbNumbers):
        self.ind_to_co = [-10 ** 18]
        self.co_to_ind = {}
        for (ind, num) in enumerate(sorted(list(set(InputProbNumbers)))):
            self.ind_to_co.append(num)
            self.co_to_ind[num] = ind + 1
        self.max = len(self.co_to_ind)
        self.data = [0] * (self.max + 1)

    def __str__(self):
        retList = []
        for i in range(1, self.max + 1):
            x = self.ind_to_co[i]
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    retList.append(x)
        return '[' + ', '.join([str(a) for a in retList]) + ']'

    def __getitem__(self, key):
        key += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1 << i) <= self.max:
                if s + self.data[ind + (1 << i)] < key:
                    s += self.data[ind + (1 << i)]
                    ind += 1 << i
        if ind == self.max or key < 0:
            raise IndexError('BIT index out of range')
        return self.ind_to_co[ind + 1]

    def __len__(self):
        return self._query_sum(self.max)

    def __contains__(self, num):
        if not num in self.co_to_ind:
            return False
        return self.count(num) > 0

    def _query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def _add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i

    def push(self, x):
        if not x in self.co_to_ind:
            raise KeyError('The pushing number didnt initialized')
        self._add(self.co_to_ind[x], 1)

    def delete(self, x):
        if not x in self.co_to_ind:
            raise KeyError('The deleting number didnt initialized')
        if self.count(x) <= 0:
            raise ValueError('The deleting number doesnt exist')
        self._add(self.co_to_ind[x], -1)

    def count(self, x):
        return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x] - 1)

    def bisect_right(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_right(self.ind_to_co, x) - 1
        return self._query_sum(i)

    def bisect_left(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_left(self.ind_to_co, x)
        if i == 1:
            return 0
        return self._query_sum(i - 1)
import sys
input = sys.stdin.readline
from operator import itemgetter
N = int(input())
A = list(map(int, input().split()))
M = int(input())
Query = [list(map(int, input().split())) for _ in range(M)]
S = []
for (i, a) in enumerate(A):
    S.append((i, a))
S.sort(key=itemgetter(0))
S.sort(key=itemgetter(1), reverse=True)
ind_to_seq = [None] * N
seq_to_ind = [None] * N
for (i, (ind, _)) in enumerate(S):
    ind_to_seq[ind] = i
    seq_to_ind[i] = ind
bit = BITbisect(list(range(N + 1)))
tmp_query = []
for (i, (k, pos)) in enumerate(Query):
    tmp_query.append((i, k, pos))
tmp_query.sort(key=itemgetter(1))
ans = [None] * M
now_k = 0
for (ind, k, pos) in tmp_query:
    while now_k <= k - 1:
        bit.push(seq_to_ind[now_k])
        now_k += 1
    ans[ind] = A[bit[pos - 1]]
print(*ans, sep='\n')

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()

class SegmentTree:

    def __init__(self, n, p, unit, f):
        self.n = n
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [unit] * (self.num * 2)
        for i in range(n):
            self.seg[self.num + i] = p[i]
        for i in range(self.num - 1, 0, -1):
            self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1) + 1])
        self.unit = unit
        self.f = f

    def update(self, i, x):
        i += self.num
        self.seg[i] = x
        while i:
            i >>= 1
            self.seg[i] = self.f(self.seg[i << 1], self.seg[(i << 1) + 1])

    def query(self, l, r):
        ansl = ansr = self.unit
        l += self.num
        r += self.num - 1
        if l == r:
            return self.seg[l]
        while l < r:
            if l & 1:
                ansl = self.f(ansl, self.seg[l])
                l += 1
            if ~r & 1:
                ansr = self.f(self.seg[r], ansr)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            ansl = self.f(ansl, self.seg[l])
        return self.f(ansl, ansr)

    def max_right(self, l, g):
        l += self.num
        ll = l // (l & -l)
        ans = self.unit
        while g(self.f(ans, self.seg[ll])):
            ans = self.f(ans, self.seg[ll])
            ll += 1
            while ~ll & 1:
                ll >>= 1
            if ll == 1:
                return self.n
        while ll < self.num:
            ll <<= 1
            if g(self.f(ans, self.seg[ll])):
                ans = self.f(ans, self.seg[ll])
                ll += 1
        return ll - self.num
n = int(input())
seg = SegmentTree(n, [0] * n, 0, lambda x, y: x + y)
a = list(map(int, input().split()))
aa = [(-a[i], i) for i in range(n)]
aa.sort()
q = int(input())
query = [[] for _ in range(n + 1)]
for i in range(q):
    (k, p) = map(int, input().split())
    k -= 1
    query[k].append((p, i))
ans = [0] * q
for k in range(n):
    (_, i) = aa[k]
    seg.update(i, 1)
    for (p, i) in query[k]:
        ans[i] = a[seg.max_right(0, lambda x: x < p)]
for i in ans:
    print(i)