需要查询[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;
}