Optimal Subsequences (Hard Version) (Codeforces 1261B2)
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):
from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_trie():
    (G0, G1, cnt) = ([-1], [-1], [0])
    return (G0, G1, cnt)

def insert(x, l):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] += 1
        if x & pow2[i]:
            if G1[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G1[j] = len(cnt) - 1
            j = G1[j]
        else:
            if G0[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G0[j] = len(cnt) - 1
            j = G0[j]
    cnt[j] += 1
    return

def kth_min(k, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if not G0[j] == -1 and cnt[G0[j]] >= k:
            j = G0[j]
        else:
            ans += pow2[i]
            if not G0[j] == -1:
                k -= cnt[G0[j]]
            j = G1[j]
    return ans
n = int(input())
a = [0] + list(map(int, input().split()))
d = defaultdict(lambda : [])
for i in range(n, 0, -1):
    d[a[i]].append(i)
m = int(input())
x = [[] for _ in range(n + 5)]
for i in range(m):
    (k, pos) = map(int, input().split())
    x[k].append((pos, i))
pow2 = [1]
l = 20
for _ in range(l):
    pow2.append(2 * pow2[-1])
(G0, G1, cnt) = binary_trie()
c = 0
ans = [0] * m
for i in sorted(d.keys(), reverse=True):
    while len(d[i]):
        insert(d[i].pop(), l)
        c += 1
        for (u, v) in x[c]:
            ans[v] = a[kth_min(u, l)]
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter

def updatebit(BITTree, n, i, v):
    while i <= n:
        BITTree[i] += v
        i += i & -i

def bisect_left(val):
    sum_ = 0
    pos = 0
    bit_length = (n + 1).bit_length()
    for i in range(bit_length, -1, -1):
        k = pos + (1 << i)
        if k < n + 1 and sum_ + l[k] < val:
            sum_ += l[k]
            pos += 1 << i
    return pos
n = int(input())
l = [0] * (n + 1)
a = [int(i) for i in input().split() if i != '\n']
empty = []
for i in range(len(a)):
    empty.append([a[i], i + 1])
empty.sort(key=lambda x: x[1])
empty.sort(key=lambda x: x[0], reverse=True)
m = int(input())
info = [list(map(int, input().split())) + [i] for i in range(m) if i != '\n']
info = sorted(info, key=itemgetter(0))
(bit, ans, cnt) = ([0] * (n + 1), [0] * m, 0)
for i in range(m):
    (k, pos, ind) = info[i]
    while cnt < k:
        updatebit(l, n, empty[cnt][1], 1)
        cnt += 1
    ans[ind] = a[bisect_left(pos)]
for i in ans:
    sys.stdout.write(str(i) + '\n')

Solution (Python):
from bisect import bisect_left, bisect_right, insort_right

class SquareSkipList:

    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        inf = float('inf')
        self.square = square
        if values is None:
            self.rand_y = seed
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y ^= (y & 524287) << 13
                y ^= y >> 17
                y ^= (y & 134217727) << 5
                if y % square == 0:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer1.append(inf)
            layer0.append(l0)
            self.rand_y = y

    def add(self, x):
        y = self.rand_y
        y ^= (y & 524287) << 13
        y ^= y >> 17
        y ^= (y & 134217727) << 5
        self.rand_y = y
        if y % self.square == 0:
            (layer1, layer0) = (self.layer1, self.layer0)
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1 + 1, layer0_idx1[idx0:])
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(self.layer1, x)
            insort_right(self.layer0[idx1], x)

    def remove(self, x):
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del self.layer1[idx1]
            self.layer0[idx1] += self.layer0.pop(idx1 + 1)
        else:
            del layer0_idx1[idx0]

    def search_higher_equal(self, x):
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):
        idx1 = bisect_right(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:
            return self.layer1[idx1 - 1]
        return layer0_idx1[idx0 - 1]

    def pop(self, idx):
        layer0 = self.layer0
        s = -1
        for (i, l0) in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s == idx:
            layer0[i] += layer0.pop(i + 1)
            return self.layer1.pop(i)
        else:
            return layer0[i].pop(idx - s)

    def __getitem__(self, item):
        layer0 = self.layer0
        s = -1
        for (i, l0) in enumerate(layer0):
            s += len(l0) + 1
            if s >= item:
                break
        if s == item:
            return self.layer1[i]
        else:
            return layer0[i][item - s]

    def print(self):
        print(self.layer1)
        print(self.layer0)
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
M = int(input())
Ans = [-1] * M
KP = [list(map(int, input().split())) for _ in range(M)]
Idx_query = list(range(M))
Idx_query.sort(key=lambda x: KP[x][0])
Idx = list(range(N))
Idx.sort(key=lambda x: A[x], reverse=True)
n = 0
st = SquareSkipList()
for idx_query in Idx_query:
    (k, pos) = KP[idx_query]
    while n < k:
        idx = Idx[n]
        st.add(idx)
        n += 1
    Ans[idx_query] = A[st[pos - 1]]
print('\n'.join(map(str, Ans)))