题解：AT_ttpc2015_o 数列色ぬり -数形结合法
前言
数形结合百般好，隔离分家万事非。
——华罗庚
这是一篇用数形结合的思想解决的此问题的题解，也是 官方题解 中的“速い解法（快速解法）”（后面还有一个“速い解法その2”）。
题意
给定一个排列，将该排列染成红色或蓝色，红色的构成上子序列，蓝色的构成下降子序列。求最多能染多少个数。
解法
看到题目描述，很容易联想到最长上升子序列（LIS）。类似地，我们可以定义最长下降子序列（LDS）。显然，LIS 和 LDS 可能不只一个，但长度是唯一的。
为了方便，以下我们记 \(|LIS|\) 为 LIS 的长度，\(|LDS|\) 为 LDS 的长度。
首先一个很理想的情况，我们可以取 \(|LIS|+|LDS|\) 个元素。但分析第一个样例就发现不可以，因为 LIS 可能会与 LDS 有重复元素。
于是我们可以考虑所有 LIS 和 LDS 中至少重复的元素个数。可以证明，这样的元素至多有一个。
证明
假设 LIS 存在两个元素 $a_i,a_j (i\lt j)$，那么由 LIS 的定义， $a_i \lt a_j$，所以 LDS 中一定不可能同时存在 $a_i$ 和 $a_j$。我们可以转换成一个判断性问题，即是否存在一个 LIS 和一个 LDS，使得 \(LIS \cap LDS = \varnothing\)。
一个很自然的想法是将这个排列放到二维平面上，即得到 \((i,a_i)\) 这些点。
为了是问题更加直观，我们把所有 LIS 用红色的折线连接，所有的 LDS 用蓝色的折线连接，如图。
注本图为
10
7 4 2 3 9 6 5 8 1 10
以下我选择以样例一和样例三为例。（为什么？因为第一组的答案是 \(|LIS|+|LDS|-1\)，第三组是 \(|LIS|+|LDS|\)）
样例一
样例三
可以观察到，在样例一的图中红线和蓝线只在端点处相交，样例三的图在红线和蓝线在非端点“十字交叉”了（以下简称“十字交叉”，应该就是官方题解中的“strictに交差”吧）。
由“形”，我们大胆猜测如果答案为 \(|LIS|+|LDS|\)，其充要条件为存在一条红线和蓝线“十字交叉”。这也很好理解，由定义可知，红线斜率为正，蓝线斜率为负，一个 LIS 对应一条红色的折线，一个 LDS 对应一条蓝色的折线。两条折线在某处“十字交叉”，那么其左边的红线上的点纵坐标都比它小，蓝线上的点纵坐标都比它大。右侧同理。
这样我们得到了一个 \(O(N^2)\) 的做法，用朴素的 \(O(N^2)\) 求 LIS 和 LDS，转移时标记一下可以从哪转移，如有多个可以转移的都记录一下。在枚举一下即可。（我没有写，可能实际复杂度会高一些）
考虑优化，以上做法慢的重要原因是总共可能牵出 \(O(N^2)\) 条线，这个我们就接受不了。我们需要减少线的数量。
由 LIS 和 LDS 的定义可知，在以某一条红线或蓝线为对角线，与 \(x\) 轴和 \(y\) 轴平行的矩形中不存在其他点，如下图。
因此，红线和蓝线相交等价于两个矩形相交（相切不算相交）。
而两个矩形相交只有如下两种情况：
进一步转化为两条线段（下图中的实线）相交。
这样一个点只会向两个方向牵出线段，我们只用保留最长的即可。这样总线段数就是 \(O(N)\)。
为了方便实现，我们还是将样例一中的图画一下。
这种情况红线转移端点 \(\min{i}\)，蓝线端点 \(\max{a_i}\)。
这种情况红线转移端点 \(\max{a_i}\)，蓝线端点 \(\max{i}\)。
然后就是蓝线和红线是否相交的问题，因为所有线都与坐标轴平行，用扫描线和树状数组即可。
至于求 LIS，我用的是树状数组优化 DP。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename tp> inline void cmax(tp &a,tp b){(a<b)&&(a=b);}
template<typename tp> inline void cmin(tp &a,tp b){(a>b)&&(a=b);}
template<typename tp> inline tp pmin(tp a,tp b){return a<b?a:b;}
template<typename tp> inline tp pmax(tp a,tp b){return a>b?a:b;}
bool _a;
const int N=1e5+10;
int n;
int a[N];
int f[N],ffr[N];//LIS
int g[N],gfr[N];//LDS
int rf[N],rfr[N],rg[N],rgr[N];
//反着求LIS 、 LDS。
bool onlis[N],onlds[N];
class BIT{//DP转移用的树状数组
private:
pii tr[N];//第一关键字为DP值，第二关键字为下标
pii merge(pii x,pii y){
return x.first!=y.first?pmax(x,y):make_pair(x.first,pmin(x.second,y.second));
}//dp 值不同取 dp较大的，相同取下标更小的
pii mg(pii &x,pii y){
return x=merge(x,y);
}
public:
void init(int tt){
fill(tr+1,tr+n+1,make_pair(0,tt));
}
void upd(int x,pii t){
for(int i=x;i<N;i+=i&(-i)){
mg(tr[i],t);
}
}
pii qry(int x){
pii t={0,0};
for(int i=x;i;i-=i&(-i)){
mg(t,tr[i]);
}
return t;
}
};
BIT T;
struct line{//扫描线
int op,x,y1,y2;
//查询形如{0,x,y1,y2}
//修改形如{1,x,y,0} 和{-1,x,y,0}
bool operator<(line o)const{
if(x!=o.x) return x<o.x;
else return op>o.op;//保证先增再查最后删，避免出错
}
}ls[N*3];//一条红线对应两次修改，一条蓝线对应一次查询
struct BIT2{//反正树状数组不难写，再写一遍
int tr[N];
void init(){
memset(tr,0,sizeof tr);
}
void upd(int x,int t){
for(int i=x;i<N;i+=i&(-i)){
tr[i]+=t;
}
}
int qry(int x){
int t=0;
for(int i=x;i;i-=i&(-i)){
t+=tr[i];
}
return t;
}
}T2;
int tot=0;
bool is_xiangjiao(){//判断相交的
sort(ls+1,ls+tot+1);
T2.init();
for(int i=1;i<=tot;i++){
if(ls[i].op==0){
int l=ls[i].y1,r=ls[i].y2;
if(T2.qry(r)-T2.qry(l-1)>0) {
return true;
}
}else{
T2.upd(ls[i].y1,ls[i].op);
}
}
return false;
}
void solve(){
memset(onlis,0,sizeof onlis);
memset(onlds,0,sizeof onlds);
T.init(0);
for(int i=1;i<=n;i++){//树状数组
pii res=T.qry(a[i]);
f[i]=res.first+1;
ffr[i]=res.second;
T.upd(a[i],make_pair(f[i],i));
}
T.init(0);
for(int i=1;i<=n;i++){
pii res=T.qry(n-a[i]+1);
g[i]=res.first+1;
gfr[i]=-res.second;//很常见的办法吧，相反数的最小值 <=> 最大值的相反数
T.upd(n-a[i]+1,make_pair(g[i],-a[i]));
}
T.init(0);
for(int i=n;i>=1;i--){
pii res=T.qry(n-a[i]+1);
rf[i]=res.first+1;
rfr[i]=-res.second;
T.upd(n-a[i]+1,make_pair(rf[i],-a[i]));//求后缀的LIS，一是为了判断点是否在LIS上，二是为例求处点后缀的 max{a_i}，为下面扫描线做准备。
}
T.init(0);
for(int i=n;i>=1;i--){
pii res=T.qry(a[i]);
rg[i]=res.first+1;
rgr[i]=-res.second;
T.upd(a[i],make_pair(rg[i],-i));
}
int lis=0,lds=0;//lis,lds的长度
for(int i=1;i<=n;i++){
cmax(lis,f[i]);
cmax(lds,g[i]);
}
for(int i=1;i<=n;i++){
if(f[i]+rf[i]-1==lis) onlis[i]=1;//判断是否 在LIS上，别忘了减去本身
if(g[i]+rg[i]-1==lds) onlds[i]=1;
}
//红线： (ffr[i],a[i]) - (i,a[i])
//蓝线： (i,a[i]) - (i,gfr[i])
//选定从左往右进行扫描，注意端点处不算
bool F=0;
tot=0;
for(int i=1;i<=n;i++){
if(!onlis[i]||ffr[i]==0) continue;
if(ffr[i]==i-1) continue;
ls[++tot]={1,ffr[i]+1,a[i],0};
ls[++tot]={-1,i-1,a[i],0};
}
for(int i=1;i<=n;i++){
if(!onlds[i]||gfr[i]==0) continue;
if(a[i]==gfr[i]-1) continue;
ls[++tot]={0,i,a[i]+1,gfr[i]-1};
}
F=is_xiangjiao();
if(F) goto out;//已经相交了，没必要在检查了，直接输出
//第二种情况：
//红线 (i,a[i])-(i,rfr[i])
//蓝线 (i,a[i])-(rgr[i],a[i])
tot=0;
for(int i=1;i<=n;i++){
if(!onlis[i]||rfr[i]==0) continue;
if(rfr[i]==a[i]+1) continue;
ls[++tot]={0,i,a[i]+1,rfr[i]-1};
}
for(int i=1;i<=n;i++){
if(!onlds[i]||rgr[i]==0) continue;
if(rgr[i]==i+1) continue;
ls[++tot]={1,i+1,a[i],0};
ls[++tot]={-1,rgr[i]-1,a[i],0};
}
F|=is_xiangjiao();
out:;
if(F) printf("%d\n",lis+lds);
else printf("%d\n",lis+lds-1);
}
bool _b;
int main(){
int _T;
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
ios::sync_with_stdio(0);cin.tie(0);
// cin>>_T;
_T=1;
while(_T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
solve();
}
return 0;
}
代码有点长，但写起来不难。最后放上在 ATcoder 上的 AC 记录。
至于“速い解法その2”，可以参考别人的题解。
浙公网安备 33010602011771号