F - Prefix LIS Query
Source: atcoder
Difficulty: 500

Problem Statement
You are given a sequence
A = (A_1, A_2, \dots, A_N)
of length
N
.
Answer
Q
queries. The
i
-th query (
1 \leq i \leq Q
) is as follows:
You are given integers
R_i
and
X_i
. Consider a subsequence (not necessarily contiguous) of
(A_1, A_2, \dots, A_{R_i})
that is strictly increasing and consists only of elements at most
X_i
. Find the maximum possible length of such a subsequence.
It is guaranteed that
X_i \geq \min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace
.
Constraints
1 \leq N,Q \leq 2 \times 10^5
1 \leq A_i \leq 10^9
1 \leq R_i \leq N
\min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace\leq X_i\leq 10^9
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
Q
A_1
A_2
\dots
A_N
R_1
X_1
R_2
X_2
\vdots
R_Q
X_Q
Output
Print
Q
lines. The
i
-th line should contain the answer to the
i
-th query.
Sample Input 1
5 3
2 4 1 3 3
2 5
5 2
5 3
Sample Output 1
2
1
2
1st query: For the sequence
(2,4)
, the longest strictly increasing subsequence with all elements at most
5
has length
2
.
Specifically,
(2,4)
qualifies.
2nd query: For the sequence
(2,4,1,3,3)
, the longest strictly increasing subsequence with all elements at most
2
has length
1
.
Specifically,
(2)
and
(1)
qualify.
3rd query: For the sequence
(2,4,1,3,3)
, the longest strictly increasing subsequence with all elements at most
3
has length
2
.
Specifically,
(2,3)
and
(1,3)
qualify.
Sample Input 2
10 8
2 5 6 5 2 1 7 9 7 2
7 8
5 2
2 3
2 6
7 3
8 9
9 6
8 7
Sample Output 2
4
1
1
2
1
5
3
4

C++ solution:
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long int;
using u64 = unsigned long long;
using pll = pair<ll, ll>;
// #include <atcoder/all>
// using namespace atcoder;
#define REP(i, a, b) for (ll i = (a); i < (b); i++)
#define REPrev(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(coll) (coll).begin(), (coll).end()
#define SIZE(v) ((ll)((v).size()))
#define REPOUT(i, a, b, exp, sep) REP(i, (a), (b)) cout << (exp) << (i + 1 == (b) ? "" : (sep)); cout << "\n"

// @@ !! LIM(f:>>)

// ---- inserted function f:>> from util.cc
template <typename T1, typename T2>
istream& operator>> (istream& is, pair<T1,T2>& p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T1, typename T2, typename T3>
istream& operator>> (istream& is, tuple<T1,T2,T3>& t) {
  is >> get<0>(t) >> get<1>(t) >> get<2>(t);
  return is;
}

template <typename T1, typename T2, typename T3, typename T4>
istream& operator>> (istream& is, tuple<T1,T2,T3,T4>& t) {
  is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
  return is;
}

template <typename T>
istream& operator>> (istream& is, vector<T>& v) {
  for (size_t i = 0; i < v.size(); i++) { is >> v[i]; }
  return is;
}

template <typename T>
vector<T> read_vector_n(istream& is, size_t n) {
  vector<T> ret(n);
  for (size_t i = 0; i < n; i++) {
    is >> ret[i];
  }
  return ret;
}

template <typename T>
vector<T> read_vector(istream& is) {
  size_t n; is >> n;
  return read_vector_n<T>(is, n);
}

// This is a very ad-hoc implementation...
istream& operator>>(istream& is, __int128& o) {
  string s; is >> s;
  o = 0;
  int sign = 1;
  for (int i = 0; i < ssize(s); i++) {
    if (s[i] == '-') {
      if (i == 0) sign = -1;
      else throw runtime_error(">>: misplaced minus sign");
    }else {
      int d = s[i] - '0';
      if (0 <= d and d <= 9) {
        o = 10 * o + d;
      }else throw runtime_error(">>: not a digit");
    }
  }
  o = sign * o;
  return is;
    
}

// ---- end f:>>

// @@ !! LIM -- end mark --

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N, Q; cin >> N >> Q;
  // @InpVec(N, A) [h9lYzKab]
  auto A = vector(N, ll());
  for (int i = 0; i < N; i++) { ll v; cin >> v; A[i] = v; }
  // @End [h9lYzKab]
  using sta = tuple<ll, ll, ll>;
  auto RXI = vector(Q, sta());
  for (int i = 0; i < Q; i++) {
    ll r, x; cin >> r >> x;
    RXI[i] = sta(r, x, i);
  }
  sort(ALL(RXI));
  vector<ll> ans(Q);
  vector<ll> vec;
  ll idx = 0;
  for (auto [r, x, i] : RXI) {
    for (; idx < r; idx++) {
      auto k = lower_bound(ALL(vec), A[idx]) - vec.begin();
      if (k == ssize(vec)) vec.push_back(A[idx]);
      else vec[k] = A[idx];
    }
    ll m = lower_bound(ALL(vec), x + 1) - vec.begin();
    ans[i] = m;
  }
  REPOUT(i, 0, Q, ans[i], "\n");
  

  return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func out(x ...interface{}) {
	fmt.Fprintln(wr, x...)
}

func outSlice[T any](s []T) {
	if len(s) == 0 {
		return
	}
	for i := 0; i < len(s)-1; i++ {
		fmt.Fprint(wr, s[i], " ")
	}
	fmt.Fprintln(wr, s[len(s)-1])
}

func getI() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getF() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getI()
	}
	return ret
}

func getS() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// min for n entry
func nmin(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = min(ret, e)
	}
	return ret
}

// max for n entry
func nmax(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = max(ret, e)
	}
	return ret
}

func chmin(a *int, b int) bool {
	if *a < b {
		return false
	}
	*a = b
	return true
}

func chmax(a *int, b int) bool {
	if *a > b {
		return false
	}
	*a = b
	return true
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

type tuple struct {
	r, x, idx int
}

const inf = int(1e18)

func lis(a []int) int {
	n := len(a)
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = inf
	}
	for i := 0; i < n; i++ {
		pos := lowerBound(dp, a[i])
		dp[pos] = a[i]
		out(dp)
	}
	pos := lowerBound(dp, inf)
	return pos
}

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt32)
	// this template is new version.
	// use getI(), getS(), getInts(), getF()
	N, Q := getI(), getI()
	a := getInts(N)

	q := make([]tuple, Q)
	for i := 0; i < Q; i++ {
		q[i] = tuple{getI(), getI(), i}
	}
	sort.Slice(q, func(i, j int) bool {
		return q[i].r < q[j].r
	})

	n := len(a)
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = inf
	}

	idx := 0

	ans := make([]int, Q)

	for i := 0; i < N; i++ {
		pos := lowerBound(dp, a[i])
		dp[pos] = a[i]

		for idx < Q && q[idx].r == i+1 {
			pos := lowerBound(dp, q[idx].x+1)
			// out(i, q[idx], "pos", pos)
			ans[q[idx].idx] = pos
			idx++
		}
		// out(dp)
	}

	for _, e := range ans {
		out(e)
	}
}

Java solution:
import java.io.*;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner();
        int n = sc.nextInt();
        int q = sc.nextInt();
        PriorityQueue<Event> queue = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            queue.add(new Event(i, sc.nextInt()));
        }
        for (int i = 0; i < q; i++) {
            queue.add(new Event(sc.nextInt() - 1, sc.nextInt(), i));
        }
        int[] ans = new int[q];
        int[] lis = new int[n + 1];
        int max = 0;
        Arrays.fill(lis, Integer.MAX_VALUE);
        lis[0] = 0;
        while (queue.size() > 0) {
            Event x = queue.poll();
            if (x.type == 0) {
                int left = 0;
                int right = max + 1;
                while (right - left > 1) {
                    int m = (left + right) / 2;
                    if (lis[m] < x.value) {
                        left = m;
                    } else {
                        right = m;
                    }
                }
                max = Math.max(max, right);
                lis[right] = x.value;
            } else {
                int left = 1;
                int right = max + 1;
                while (right - left > 1) {
                    int m = (left + right) / 2;
                    if (lis[m] <= x.value) {
                        left = m;
                    } else {
                        right = m;
                    }
                }
                ans[x.idx] = left;
            }
        }
        System.out.println(Arrays.stream(ans).mapToObj(String::valueOf).collect(Collectors.joining("\n")));
    }
    
    static class Event implements Comparable<Event> {
        int type;
        int right;
        int value;
        int idx;
        
        public Event(int right, int value) {
            type = 0;
            this.right = right;
            this.value = value;
        }
        
        public Event(int right, int value, int idx) {
            type = 1;
            this.right = right;
            this.value = value;
            this.idx = idx;
        }
        
        public int compareTo(Event another) {
            return right == another.right ? type - another.type : right - another.right;
        }
    }
}

class FastScanner {
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer, bytesRead;
    private static final int BUFFER_SIZE = 1 << 16; // 65,536 バイト

    public FastScanner() {
        din = new DataInputStream(System.in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    private byte read() {
        try {
            if (bufferPointer == bytesRead) {
                bytesRead = din.read(buffer, 0, BUFFER_SIZE);
                if (bytesRead == -1) return -1;
                bufferPointer = 0;
            }
            return buffer[bufferPointer++];
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public String next() {
        byte b = read();
        // 空白文字を読み飛ばす
        while (isSpaceChar(b)) {
            b = read();
        }
        StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b)) {
            sb.append((char) b);
            b = read();
        }
        return sb.toString();
    }

    public int nextInt() {
        int ret = 0;
        byte c = read();
        while (isSpaceChar(c)) c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return neg ? -ret : ret;
    }

    public long nextLong() {
        long ret = 0;
        byte c = read();
        while (isSpaceChar(c)) c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10L + c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return neg ? -ret : ret;
    }

    public double nextDouble() {
        double ret = 0, div = 1;
        byte c = read();
        while (isSpaceChar(c)) c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
            c = read();
        } while (!isSpaceChar(c) && c != '.');
        if (c == '.') {
            while (!isSpaceChar(c = read())) {
                ret += (c - '0') / (div *= 10);
            }
        }
        return neg ? -ret : ret;
    }

    private boolean isSpaceChar(byte c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public void close() {
        try {
            if (din != null) din.close();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}

JavaScript solution:
function Main(input) {
    input = input.split("\n").map((line) => line.trim());
    const [N, Q] = input[0].split(" ").map(Number);
    const A = input[1].split(" ").map(Number);
    
    const [R, X] = [[], []];
    for (let i = 0; i < Q; i++)
        [R[i], X[i]] = input[i + 2].split(" ").map(Number);
        
    const query = [];
    for (let i = 0; i < Q; i++) query.push([R[i], X[i], i]);
    query.sort((a, b) => a[0] - b[0]);
    
    const ans = Array(Q).fill(0);
    const L = [];
    let pos = 0;
    for (let i = 0; i < N; i++) {
        if (L.length === 0) L.push(A[i]);
        else {
            let pos = lower_bound(L, A[i]);
            if (pos === L.length) L.push(A[i]);
            else L[pos] = A[i];
        }

        while (pos < Q && query[pos][0] <= i + 1) {
            const [r, x, idx] = query[pos];
            let res = lower_bound(L, x + 1);
            ans[idx] = res;
            pos++;
        }
    }
    console.log(ans.join("\n"));
}
const isOK = (arr, mid, key) => arr[mid] >= key;
const lower_bound = (arr, key) => {
    let ng = -1;
    let ok = arr.length;

    while (ok - ng > 1) {
        let mid = Math.floor((ok + ng) / 2);
        if (isOK(arr, mid, key)) ok = mid;
        else ng = mid;
    }
    return ok;
};

Main(require("fs").readFileSync(0, "utf8"));

Python solution:
import sys
input = lambda:sys.stdin.readline().strip()
from bisect import bisect_left, bisect_right

n, m = map(int, input().split())
q = [[] for _ in range(n)]

a = list(map(int, input().split()))

for i in range(m):
    r, x = map(int, input().split())
    q[r - 1].append((x, i))

f = [float('-inf')]
len_f = 0
ans = [0] * m

for i in range(n):
    if a[i] > f[-1]:
        f.append(a[i])
    else:
        index = bisect_left(f, a[i])
        f[index] = a[i]

    for x, idx in q[i]:
        ans[idx] = bisect_right(f, x) - 1

for x in ans: print(x)

Ruby solution:
N, Q = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)

B = Q.times.map{ q = gets.split.map(&:to_i); q[0] -= 1; q }
C = Array.new(Q)
q_seq = Q.times.sort_by{|i| B[i][0] }

dp = [0]
A.each_with_index do |a, i|
  dp[dp.bsearch_index{|x| x >= a }||dp.size] = a
  until q_seq.empty? || B[q_seq[0]][0] > i
    k = q_seq.shift
    x = B[k][1]
    z = (dp.bsearch_index{|y| y > x } || dp.size) - 1
    C[k] = z
  end
end
puts C