题目链接：https://www.luogu.com.cn/problem/P1020
题目大意：
Dilworth定理:偏序集能划分成的最少的全序集个数等于最大反链的元素个数。
例如对于(a[i],b[])和(a[j],b[j])这两个元素,如果我们定义偏序关系为：a[i]<a[j]并且b[i]>b[j]那么它的反链为：a[i]<a[j]并且b[i]<=b[i]对于这道题，我们以下标为a[i],值为b[i]那么偏序关系为:a[i]<a[j]并且b[i]>=b[j]反链为:a[i]<a[j]并且b[i]<b[j]全序集最大大小为：最长不上升子序列最长反链为：最长上升子序列
#include<bits/stdc++.h>
#define LL long long
using namespace std;
struct BitTree
{
int a[2][100005];
int lowbit(int x){
return x&(-x);
}
void update(int x,int d,int op){//a[x]=d//修改a[x]的权值只能增加 0:后缀最大值
if(op==0){
while(x){
a[0][x] = max(a[0][x],d);
x -= lowbit(x);
}
}
else{
while(x <= 100005){
a[1][x] = max(a[1][x],d);
x += lowbit(x);
}
}
}
int query(int x,int op){
int ret = -1e9;
if(op==0){
while(x <= 100005){
ret = max(a[0][x],ret);
x += lowbit(x);
}
}
else {
while(x){
ret = max(ret,a[1][x]);
x -= lowbit(x);
}
}
return ret;
}
}b;
int a[200005];
int main(){
int n=0, ans1=0, ans2=0;
while(scanf("%d", &a[++n])!=EOF);
n--;//读后才判断所以最后一个n没有读到数
for(int i=1; i<=n; i++){//最长不上升子序列
int m=b.query(a[i], 0);
ans1=max(ans1, m+1);
b.update(a[i], m+1, 0);
}
for(int i=1; i<=n; i++){//最长上升子序列
int m=b.query(a[i], 1);
ans2=max(ans2, m+1);
b.update(a[i]+1, m+1, 1);//a[i]+1是因为树状数组的下标最小为1
}
printf("%d\n%d\n", ans1, ans2);
return 0;
}
京公网安备 11010502036488号