[ARC149B] Two LIS Sum

在我的博客园中查看本文

Key Observation：让 \(a_i\) 排好序，然后统计 \(b_i\) 的 LIS 长度，这样就是最优答案了。

为什么可以这样呢？考虑每一次交换，\(a_i\) 一定会减少一个逆序对（即让 LIS 的长度减少 \(1\)），然后 \(b_i\) 可能会增加一个逆序对或不会增加，所以把 \(a_i\) 从小到大排序的过程中 LIS 长度之和是单调不增的。

需要会一个 \(O(n \log n)\) 的贪心求 LIS 做法。考虑记录长度为 \(i\) 的 LIS 末尾元素，显然末尾元素越小越好，因为越小的才有可能接上更多的数。具体可以参考 NOIP 导弹拦截。

参考代码：https://atcoder.jp/contests/arc149/submissions/78359919

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=3e5+7;
int n,a[N],b[N];
vector<int> lis;  //长度为i+1的lis的末尾元素为lis[i]
int main()
{
//	freopen("neuvillette.in","r",stdin);
//	freopen("neuvillette.out","w",stdout);cin.tie(0)->sync_with_stdio(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[a[i]];for(int i=1;i<=n;i++){auto p=lower_bound(lis.begin(),lis.end(),b[i]);if(p==lis.end()) lis.push_back(b[i]);else *p=b[i];}cout<<n+(int)lis.size();cout.flush();return 0;
}
/*
注意到如果将a排好序的话，每次交换，a的LIS会+1，然后b的LIS肯定不会减少超过1
所以把a排好序的话是最优的
实现方面：b对应的a就是b在排序后数组的排名
用nlogn的LIS算法
*/