专栏文章

题解：P2075 区间 LIS

云云浅知处はなび
P2075题解参与者 4已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@mip44alq
此快照首次捕获于
2025/12/03 05:51
3 个月前
此快照最后确认于
2025/12/03 05:51
3 个月前
查看原文
首先，求一个序列 p1,⋯ ,pnp_1,\cdots,p_n 的 LIS 有一个经典的算法：维护一个集合 SS，初始为空，依次扫描 i=1,2,⋯ ,ni=1,2,\cdots,n，每次如果 SS 中所有数都 <pi<p_i，则令 S←S∪{pi}S\leftarrow S\cup\{p_i\}；否则把 SS 中最小的 >pi>p_i 的数变为 pip_i。这样最后 ∣S∣|S| 就是 LIS 的长度（注意 SS 中的数并不一定构成 LIS）。
这可以解释为，对 j=1,2,⋯ ,nj=1,2,\cdots,n 维护了 fjf_j 表示所有长度为 jj 的 LIS 中，最小的结尾元素是多少。初始，所有 fi=+∞f_i=+\infty。那么往末尾添加一个元素 pip_i 对 ff 的影响就是，如果本来的 fj<pif_j<p_i，则存在一个长度为 j+1j+1 的结尾为 pip_i 的元素，即我们需要令 fj+1←min⁡(fj+1,pi)f_{j+1}\leftarrow \min(f_{j+1},p_i)。可以发现 ff 是递增的，所以只有唯一的那个 fj<pi<fj+1f_j<p_i<f_{j+1} 的位置会发生改变，那么造成的影响就和之前说的过程等价了：SS 中维护的本质上是所有 fi<+∞f_i<+\infty 的 fif_i，每次就是把最小的 >pi>p_i 的元素改成 pip_i；如果最大的元素都 <pi<p_i，那么就把 pip_i 插入进去。答案自然也就是最大的 ii 使得 fi<+∞f_i<+\infty，即 ∣S∣|S|。
现在我们考虑区间询问怎么做，设 Sl,rS_{l,r} 表示从空集开始，依次按照上述方法插入 pl,pl+1,⋯ ,prp_l,p_{l+1},\cdots,p_r 得到的最终集合。那么，对任意 l<rl<r，我们总有 Sl+1,r⊆Sl,rS_{l+1,r}\subseteq S_{l,r}。证明可以考虑如果当前 A⊆BA\subseteq B，我们往 A,BA,B 中同时按上述方法加入 xx（即，找到第一个 >x>x 的变成 xx，不存在则直接插入）造成的影响。手玩一下可以发现，不论 xx 如何取，操作结束后得到的新集合 A′,B′A',B' 总是仍然满足 A′⊆B′A'\subseteq B'。那么对于前面所述的命题，由于初始 Sl+1,l+1S_{l+1,l+1} 肯定是 Sl,l+1S_{l,l+1} 的子集，所以对任意的 r>lr>l 都有 Sl+1,r⊆Sl,rS_{l+1,r}\subseteq S_{l,r}。
既然如此，我们要求出 l,rl,r 的答案，就可以这样做：扫描线扫 r=1,2,⋯ ,nr=1,2,\cdots,n，对每个 xx，它总是在 ll 取一段前缀的 Sl,rS_{l,r} 中出现。我们考虑维护 qxq_x 表示最大的 ll 使得 x∈Sl,rx\in S_{l,r}，即 xx 出现在 S1,r,⋯ ,Sqx,rS_{1,r},\cdots,S_{q_x,r} 中，不出现在 Sqx+1,r,⋯ ,Sr,rS_{q_x+1,r},\cdots,S_{r,r} 中。那么对于一次询问 l,rl,r，只需要查询有多少个 xx，使得 qx≥lq_x\ge l。
现在只需要考虑：在 r→r+1r\to r+1 时，如何维护序列 qq，以及如何维护形如「查询全局有多少个 ≤l\le l 的元素」这样的询问。
我们先来考虑 r→r+1r\to r+1 时序列 qq 是如何变化的。设 v=pr+1v=p_{r+1}，首先，对任意的 ll，不论 Sl,rS_{l,r} 原先是什么样的，vv 总会要么替换掉一个元素，要么直接插入进去，从而出现在 Sl,r+1S_{l,r+1} 里，即必然有 qv=r+1q_v=r+1。接下来考虑 qv+1q_{v+1}，我们发现 v+1v+1 如果在某个 Sl,rS_{l,r} 中出现过，那么插入 vv 之后必然会被替换掉，所以 qv+1q_{v+1} 必然会变成 00。那么 v+2v+2 呢？发现只有当 v+1v+1 出现过的时候才能帮它挡掉这一次操作的影响，否则他也会被替换掉。于是，如果原本序列中 qv+2>qv+1q_{v+2}>q_{v+1}，那么新的 qv+2′q'_{v+2} 就是原本的 qv+1q_{v+1}；否则 qv+2q_{v+2} 不变。
以此类推，读者想必已经看出：r→r+1r\to r+1 造成的影响可以用以下代码描述：（其中代码里的 v=pr+1v=p_{r+1}）
CPP
q[v]=r+1,now=0
for(int i=v+1;i<=n;i++)if(q[i]>now)swap(q[i],now)
此时，如果你做过回转寿司，那么这个题的解法已经呼之欲出了。
考虑到这部分也并不算简单，我在这里也详细描述一下这部分是怎么做的。
我们先考虑一个简单的情形：每次操作，我们都是完整地枚举 ii 从 11 到 nn（而非 v+1v+1 到 nn），以及给定初值 nownow（不一定为 00，尽管本题中总有 now=0now=0，也不可能真的从 11 枚举到 nn），然后每次如果 qi>nowq_i>now，则 swap(qi,now)\text{swap}(q_i,now)。可以发现，由于我们在查询的时候只关注 {qi}i=1n\{q_i\}_{i=1}^n 这个可重集（因为只关注多少个 qx≥lq_x\ge l），而操作对 {qi}i=1n\{q_i\}_{i=1}^n 这个可重集造成的影响一定恰好是：如果 nownow 大于 qq 的最大值则无事发生，否则就是在可重集中删除最大值，然后插入 nownow。那么我们可以简单用一个堆来维护。
现在我们的 vv 不一定是从 11 开始的，那么考虑分块，每个块维护一个堆表示块内元素的可重集。对于整块，只需要每次把 nownow 和当前块里的最大值 mxmx 比较，如果 mx>nowmx>now，则从当前块中删除 mxmx，插入 nownow，然后 nownow 从这一块出去的时候的新值就是 mxmx；如果 mx≤nowmx\le now 则无事发生。现在剩下的问题就是，对于散块的部分，该如何快速地知道这个块内的元素 x1,⋯ ,xBx_1,\cdots,x_B 经历一系列操作 y1,⋯ ,yky_1,\cdots,y_k（「经历一个操作 yiy_i」指的是枚举 j=1,2,⋯ ,Bj=1,2,\cdots,B，如果 xj>yix_j>y_i 则交换二者）后分别变成了多少。注意这里我们必须还原出完整的序列。
我们不妨先来考虑第一个元素 q1q_1，它经历一系列操作 x1,⋯ ,xkx_1,\cdots,x_k 之后，如果 q1>min⁡xiq_1>\min x_i，肯定会变成 min⁡xi\min x_i，否则无事发生；然后这一个操作序列 x1,⋯ ,xkx_1,\cdots,x_k 对 q2q_2 的影响是什么呢，发现相当于把第一个 <q1<q_1 的 xix_i 变成 q1q_1，然后把 xix_i 后面第一个 <xi<x_i 的变为 xix_i，以此类推。这是和原本的操作非常对称的一个操作，只不过 chkmax 变成了 chkmin。同理我们发现由于只关注 min⁡\min，可以拿一个堆来维护当前的操作序列 xx。于是，我们便可以在 O(Blog⁡n)O(B\log n) 的时间内重构这个块了。
综上，我们得到一个 O((nB+B)log⁡n)O((\frac{n}{B}+B)\log n) 单次操作的算法，取 B=nB=\sqrt{n}，总的复杂度就是 O(nnlog⁡n+qlog⁡n)O(n\sqrt{n}\log n+q\log n)。
CPP
#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

#define gc getchar
inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=1e5+5;
int a[N],q[N],n,ans[N],m;
vector<pair<int,int> >ques[N];

struct BIT{
	int c[N];
	int lowbit(int x){return x&(-x);}
	void add(int x,int v){x++;for(int i=x;i<=n+1;i+=lowbit(i))c[i]+=v;}
	int sum(int x){int res=0;for(int i=x+1;i;i-=lowbit(i))res+=c[i];return res;}
}T;

const int B=250;
const int NB=N/B+5;

priority_queue<int>P[NB],Q[NB];
int L[NB],R[NB],bl[N];
void rebuild(int p){
	if(Q[p].size()==0)return ;
	int l=L[p],r=R[p];
	for(int i=l;i<=r;i++)if(q[i]>-Q[p].top()){
		int cur=-Q[p].top();
		Q[p].pop(),Q[p].push(-q[i]),q[i]=cur;
	}
	priority_queue<int>().swap(Q[p]);
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=m;i++){
		int l=read(),r=read();
		ques[r].emplace_back(mk(l,i));
	}

	int S=sqrt(n);memset(L,63,sizeof(L));
	for(int i=1;i<=n;i++)bl[i]=(i-1)/S+1,cmin(L[bl[i]],i),cmax(R[bl[i]],i);
	for(int i=1;i<=bl[n];i++)for(int j=L[i];j<=R[i];j++)P[i].push(0);

	T.add(0,n);
	for(int i=1;i<=n;i++){
		int v=a[i],now=0;
		
		if(v+1<=n){
			int p=bl[v+1];rebuild(p);
			for(int j=v+1;j<=R[p];j++)if(q[j]>now)swap(now,q[j]);
			priority_queue<int>().swap(P[p]);
			for(int j=L[p];j<=R[p];j++)P[p].push(q[j]);
			
			for(int j=p+1;j<=bl[n];j++)if(P[j].top()>now){
				int cur=P[j].top();
				P[j].pop(),P[j].push(now),Q[j].push(-now),now=cur;
			}
			T.add(now,-1),T.add(0,1);
		}
		
		rebuild(bl[v]);
		T.add(q[v],-1),q[v]=i,T.add(q[v],1);
		priority_queue<int>().swap(P[bl[v]]);
		for(int j=L[bl[v]];j<=R[bl[v]];j++)P[bl[v]].push(q[j]);

		for(auto [l,id]:ques[i])ans[id]=T.sum(n)-T.sum(l-1);
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';

	return 0;
}

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...