abc134E - Sequence Decomposing
题意：给定一个序列，将其划分成若干个不相交的严格上升子序列，求划分的最小的子序列数量。
题解：
我们可以定义严格偏序关系，\(i \prec j\)当\(i< j\)且\(a_i< a_j\)，也就是我们要将整个序列划分成若干个链。
根据 Dilworth’s theorem，最小链覆盖数=最大反链大小，
假设对于两个在反链中的元素i，j不妨假设\(i<j\)
显然有\(a_i \geq a_j\)，也就是说最大反链大小等于最长不上升子序列的长度。
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const ll inf=1ll<<60;
const int N=2e5+5;
int a[N],n,b[N],m,c[N];
int lowbit(int x){
return x&(-x);
}
void upd(int x,int y){
for (;x<N;x+=lowbit(x)) c[x]=max(c[x], y);
}
int ask(int x){
int s=0;
for (;x;x-=lowbit(x)) s=max(s, c[x]);
return s;
}
int main(){
// freopen("data.in","r",stdin);
scanf("%d",&n);
fo(i,1,n) scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+n+1);
m=unique(b+1,b+n+1)-(b+1);
fo(i,1,n) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
int ans=0,x;
fd(i,n,1) {
x=ask(a[i])+1;
upd(a[i],x);
ans=max(ans, x);
}
printf("%d\n",ans);
return 0;
}