吉首大学2019年程序设计竞赛（重现赛）B：干物妹小埋（树状数组求LIS）

【题解】

树状数组求最长上升子序列：复制原数组，排序去重后，原数组从前往后扫，找到它在去重后数组的位置，树状数组维护最长上升子序列的长度。

【代码】

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) x&-x
const int maxn=2e5+5;
vector <int> v;
int n,a[maxn];
ll c[maxn];
void add(int x,ll y)
{while(x<=n){c[x]=max(c[x],y);x+=lowbit(x);}
}
ll query(ll x)
{ll ans=0;while(x>0){ans=max(ans,c[x]);x-=lowbit(x);}return ans;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);v.push_back(a[i]);}//离散化sort(v.begin(),v.end());int len=unique(v.begin(),v.end())-v.begin();ll ans=0;for(int i=1;i<=n;i++){int p=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;ll y=query(p);int x; scanf("%d",&x);ans=max(ans,x+y);add(p,x+y);}printf("%lld\n",ans);return 0;
}

【题目】

干物妹小埋