【Codeforces 650D】Zip-line
分治
题目大意：
给定一个数列 $a_1,a_2,a_3,\ldots,a_n$。
每次询问会替换序列的一个数，并问你此时的最长严格上升子序列长度。
询问独立，即每次询问不会实际替换掉那个数。
题解：
记 $f_i$ 表示以 $i$ 结尾的最长严格上升子序列长度，$g_i$ 表示以 $i$ 开头的最长严格上升子序列长度。
求 $f$ 和 $g$ 就是一个普通的 LIS 问题，可以使用单调队列等做法，时间复杂度 $O(n\log n)$。
对于每一个询问 $u,v$，它会修改掉一个数。那么我们考虑两种情况：LIS 中包含这个数，或者 LIS 中不包含这个数。
包含的情况。
这种情况较好处理。我们只要能求出在 $u$ 之前结尾且结尾的数小于 $v$ 的 LIS 长度 $a$，以及在 $u$ 之后开头且开头的数大于 $v$ 的 LIS 长度 $b$，那么 $a+b+1$ 就是其贡献。
将询问离线以后，在求 $f$ 和 $g$ 的同时按照一样的方法就可以得到 $a$ 和 $b$。
时间复杂度 $O(m\log n)$。
不包含的情况。
令 $h_i$ 表示不包含 $i$ 时原序列的 LIS，那么对于询问 $u,v$，答案只需要对 $h_u$ 取 $\max$ 就好了。
那么如何求出 $h_i$ 呢？
对于 $h_i$，我们要找到 $u,v$ 满足 $u\lt i\lt v$，$a_u\lt a_v$，并且 $f_u+g_v$ 最大。
考虑分治。令当前中点为 $x$。我们考虑对每个在 $[l,x]$ 中的 $f$，找到一个在 $[x+1,r]$ 中的 $g$ 并使结果最大。这样可以更新 $h_{l..x}$。右半边同理可得。
那么我们可以枚举 $i\in[l,x]$，在 $[x+1,r]$ 中二分出第一个满足 $a_i\lt a_k$ 的 $k$，然后对 $g_{k..r}$ 求最大值 $g_0$。然后 $f_i+g_0$ 的结果可以更新到 $h_{i+1..x}$，这个可以直接更新到 $h_{i+1}$ 上然后求后缀最大值得到。
需要排序和二分，那么时间复杂度就是 $O(n\log^2 n)$。
考虑进一步优化。
首先这个排序可以分治的同时进行归并。
然后这个二分也可以省。我们按 $a_i$ 从大到小枚举 $i$，那么 $a_k$ 也是不断变小的，双指针维护即可。$g$ 的最值也可以直接维护。
于是时间复杂度为 $O(n\log n)$。
算法的总时间复杂度为 $O((n+m)\log n)$，空间复杂度为 $O(n+m)$。
Code：
#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
const int N=4e5+10;
int pre[N],suf[N],n,m,a[N],ans[N],res[N];
vector<pair<int,int> >vc[N];
int sta[N],top,cov[N];
pair<int,int>d[N],tmp[N];
void solve(int l,int r){
if(l==r){
return;
}
const int mid=(l+r)/2;
solve(l,mid),solve(mid+1,r);
for(int i=mid,nw=0,it=r;i>=l;--i){
while(it>mid&&d[i].first<d[it].first)nw=max(nw,suf[d[it--].second]);
cov[d[i].second+1]=pre[d[i].second]+nw;
}
for(int i=l+1;i<=mid;++i)cov[i]=max(cov[i],cov[i-1]);
for(int i=l;i<=mid;++i)res[i]=max(res[i],cov[i]);
for(int i=l;i<=mid+1;++i)cov[i]=0;
for(int i=mid+1,nw=0,it=l;i<=r;++i){
while(it<=mid&&d[i].first>d[it].first)nw=max(nw,pre[d[it++].second]);
cov[d[i].second-1]=suf[d[i].second]+nw;
}
for(int i=r-1;i>mid;--i)cov[i]=max(cov[i],cov[i+1]);
for(int i=mid+1;i<=r;++i)res[i]=max(res[i],cov[i]);
for(int i=mid;i<=r;++i)cov[i]=0;
int itL=l,itR=mid+1,it=l;
while(itL<=mid&&itR<=r)
if(d[itL]<d[itR])tmp[it++]=d[itL++];else tmp[it++]=d[itR++];
while(itL<=mid)tmp[it++]=d[itL++];
while(itR<=r)tmp[it++]=d[itR++];
for(int i=l;i<=r;++i)d[i]=tmp[i];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",a+i);
for(int i=1;i<=m;++i){
int p,x;
scanf("%d%d",&p,&x);
vc[p].emplace_back(x,i);
ans[i]=1;
}
for(int i=1;i<=n;++i){
res[i]=top;
for(auto it:vc[i]){
int v=it.first,id=it.second;
int len=lower_bound(sta,sta+top+1,v)-sta-1;
ans[id]+=len;
}
int t=lower_bound(sta,sta+top+1,a[i])-sta;
if(t>top)sta[++top]=a[i];
else sta[t]=min(sta[t],a[i]);
pre[i]=t;
}
sta[top=0]=1e9+7;
for(int i=n;i;--i){
res[i]=max(res[i],top);
for(auto it:vc[i]){
int v=it.first,id=it.second;
int len=lower_bound(sta,sta+top+1,v,greater<int>())-sta-1;
ans[id]+=len;
}
int t=lower_bound(sta,sta+top+1,a[i],greater<int>())-sta;
if(t>top)sta[++top]=a[i];
else sta[t]=max(sta[t],a[i]);
suf[i]=t;
}
for(int i=1;i<=n;++i)d[i]=make_pair(a[i],i);
solve(1,n);
for(int i=1;i<=n;++i)
for(auto it:vc[i])ans[it.second]=max(ans[it.second],res[i]);
for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
return 0;
}