X.CF650D Zip-line
我们考虑在修改一个位置后，新的LIS可能有哪些。
- 就是原序列中的LIS。
设原序列LIS长度为\(len\)。
此时有两种可能：
A.被修改的位置在LIS中不是不可替代的（换句话说，有至少一条LIS不经过此位置）。此时，长度就是\(len\)。
B.被修改的位置在LIS中不可替代（换句话说，所有LIS都经过此位置）。此时，长度是\(len-1\)。
至于如何判断是不是不可替代的吗……可以记录以当前位置开头和结尾的LIS数量，然后与总LIS数量比较。如果开头结尾的LIS数量之积等于总LIS数量，则该位置是不可替代的。
因为LIS数量非常非常大，因此模上一个大数哈希一下即可。
- 不是原序列中的LIS。
则我们要找到所有在它前面且比它小的位置中前缀长度的最大值，以及所有在它后面且比它大的位置中后缀长度的最大值，然后拼在一起完成。
考虑用主席树维护即可。
但是！！！这题卡空间，两棵主席树就是\(40\)倍空间，跑不过去。
被卡的主席树代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define mid ((l+r)>>1)
#define pii pair<int,int>
#define mp make_pair
#define ff first
#define ss second
int n,root1[400100],root2[400100],a[400100],m,lim,cnt;
pii mx;
pii f[400100],g[400100];
vector<int>v;
struct SegTree{
int lson,rson;
pii sum;
}seg[16001000];
pii operator +=(pii&x,const pii&y){
if(x.ff==y.ff)(x.ss+=y.ss),x.ss%=mod;
else if(x.ff<y.ff)x=y;
}
pii operator +(const pii&x,const pii&y){
if(x.ff==y.ff)return make_pair(x.ff,(x.ss+y.ss)%mod);
return max(x,y);
}
void modify(int &x,int y,int l,int r,int P,pii val){
if(l>P||r<P)return;
x=++cnt;
seg[x]=seg[y],seg[x].sum+=val;
if(l!=r)modify(seg[x].lson,seg[y].lson,l,mid,P,val),modify(seg[x].rson,seg[y].rson,mid+1,r,P,val);
}
pii query(int x,int l,int r,int L,int R){
if(l>R||r<L)return mp(0,0);
if(L<=l&&r<=R)return seg[x].sum;
return query(seg[x].lson,l,mid,L,R)+query(seg[x].rson,mid+1,r,L,R);
}
void build(int &x,int l,int r){
x=++cnt;
if(l!=r)build(seg[x].lson,l,mid),build(seg[x].rson,mid+1,r);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin()),lim=v.size();
for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
build(root1[0],1,lim);
for(int i=1;i<=n;i++){
f[i]=query(root1[i-1],1,lim,1,a[i]-1),f[i].first++;
if(f[i].first==1)f[i].second++;
modify(root1[i],root1[i-1],1,lim,a[i],f[i]),mx+=f[i];
}
build(root2[n+1],1,lim);
for(int i=n;i>=1;i--){
g[i]=query(root2[i+1],1,lim,a[i]+1,lim),g[i].first++;
if(g[i].first==1)g[i].second++;
modify(root2[i],root2[i+1],1,lim,a[i],g[i]);
}
for(int i=1,x,y,res;i<=m;i++){
scanf("%d%d",&x,&y);
if(f[x].first+g[x].first-1==mx.first&&1ll*f[x].second*g[x].second%mod==mx.second)res=mx.first-1;
else res=mx.first;
res=max(res,query(root1[x-1],1,lim,1,lower_bound(v.begin(),v.end(),y)-v.begin()).first+1+query(root2[x+1],1,lim,upper_bound(v.begin(),v.end(),y)-v.begin()+1,lim).first);
printf("%d\n",res);
}
return 0;
}
主席树是暴力的思想，但是是在线的。如果我们把它离线下来，就可以在建主席树时直接回答当前位置的询问。而主席树实际上是线段树的前缀和，故直接用线段树维护即可。只需要\(4\)倍空间。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
#define pii pair<int,int>
#define mp make_pair
#define ff first
#define ss second
int n,a[400100],m,lim,res[400100];
pii mx;
pii f[400100],g[400100],seg[1600100];
vector<int>v;
vector<pii>q[400100];
pii operator +=(pii&x,const pii&y){
if(x.ff==y.ff)(x.ss+=y.ss),x.ss%=mod;
else if(x.ff<y.ff)x=y;
}
pii operator +(const pii&x,const pii&y){
if(x.ff==y.ff)return make_pair(x.ff,(x.ss+y.ss)%mod);
return max(x,y);
}
void modify(int x,int l,int r,int P,pii val){
if(l>P||r<P)return;
seg[x]+=val;
if(l!=r)modify(lson,l,mid,P,val),modify(rson,mid+1,r,P,val);
}
pii query(int x,int l,int r,int L,int R){
if(l>R||r<L)return mp(0,0);
if(L<=l&&r<=R)return seg[x];
return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
}
void build(int x,int l,int r){
seg[x]=mp(0,0);
if(l!=r)build(lson,l,mid),build(rson,mid+1,r);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin()),lim=v.size();
for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),q[x].push_back(mp(y,i));
build(1,1,lim);
for(int i=1;i<=n;i++){
f[i]=query(1,1,lim,1,a[i]-1),f[i].first++;
if(f[i].first==1)f[i].second++;
for(auto j:q[i])res[j.second]=query(1,1,lim,1,lower_bound(v.begin(),v.end(),j.first)-v.begin()).first+1;
modify(1,1,lim,a[i],f[i]),mx+=f[i];
}
build(1,1,lim);
for(int i=n;i>=1;i--){
g[i]=query(1,1,lim,a[i]+1,lim),g[i].first++;
if(g[i].first==1)g[i].second++;
int fal=(f[i].first+g[i].first-1==mx.first&&1ll*f[i].second*g[i].second%mod==mx.second?mx.first-1:mx.first);
for(auto j:q[i])res[j.second]+=query(1,1,lim,upper_bound(v.begin(),v.end(),j.first)-v.begin()+1,lim).first,res[j.second]=max(res[j.second],fal);
modify(1,1,lim,a[i],g[i]);
}
for(int i=1;i<=m;i++)printf("%d\n",res[i]);
return 0;
}