需要查询[1, i - 1]中w[j]>w[i]的f[j]的最大值 值域分块O(nsqrt(K))

// Problem: P1020 [NOIP1999 普及组] 导弹拦截
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1020
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e5 + 10;

int n, m, K, A[N], len, L[N], R[N], lz[N], pos[N], S;
int f[N], h[N], w[N];

int query(int l) {
    int res = 0;
    for (int i = l; i <= R[pos[l]]; i ++ ) chkmax(res, A[i]);
    for (int i = pos[l] + 1; i <= S; i ++ ) chkmax(res, lz[i]);
    return res;
}

void add(int x, int v) {
    chkmax(A[x], v);
    chkmax(lz[pos[x]], v);
}

int main() {
    int x;
    int K = 0;
    while (cin >> x) w[ ++ n] = x, chkmax(K, x);
    int cnt = 0;
    len = sqrt(K); S = (K + len - 1) / len;
    for (int i = 1; i <= S; i ++ ) L[i] = R[i - 1] + 1, R[i] = len * i; R[S] = K;
    for (int i = 1; i <= S; i ++ ) for (int j = L[i]; j <= R[i]; j ++ ) pos[j] = i;
    memset(h, 0x3f, sizeof h);
    for (int i = 1; i <= n; i ++ ) {
        f[i] = 1;
        chkmax(f[i], query(w[i]) + 1);
        int c = 1;
        while (h[c] < w[i]) c ++ ;
        if (c > cnt) h[ ++ cnt] = w[i];
        else h[c] = w[i];
        add(w[i], f[i]);
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ ) chkmax(res, f[i]);
    cout << res << '\n' << cnt << '\n';
    return 0;
}