P2075 区间 LIS 做题记录

给定一个 $n$ 的排列 $a$，$q$ 次询问，每次查询 $a_{[l_i,r_i]}$ 的 LIS 长度。

$1\le n\le 10^5$，$1\le q\le 10^6$。

考虑求序列 $b$ 的 LIS 长度的经典贪心算法：

维护一个集合 $S$，从前往后遍历 $b$ 的每个元素 $b_i$：

• 找到最小的 $x\in S,x\ge b_i$；
• 若找到了则从 $S$ 中删掉 $x$，找不到就不管；
• 将 $b_i$ 加入 $S$；

最终 $|S|$ 即为 LIS 长度。

原理是最长反链等于最小链覆盖。

设 $S_{[l,r]}$ 对表示 $b=a_{[l,r]}$ 执行上面的过程最终得到的 $S$。

观察发现，$S_{[l+1,r]}\subseteq S_{[l,r]}$，并且 $|S_{[l+1,r]}|$ 和 $|S_{[l,r]}|$ 最多相差 $1$，即最多会新插入一个数。

证明考虑在前面插入一个数后原来 $S$ 中的数肯定不会消失（消失只能是因为被后面的数顶掉），而最多在链覆盖中增加一条链（$S$ 中最多插入一个数）。

那么考虑扫描线，$r$ 从左到右扫描的同时维护每个数 $x$ 在 $l\in[1,r]$ 的多少个 $S_{[l,r]}$ 中出现了，记为 $cnt_x$。注意到 $x$ 肯定是出现在 $S_{[[1,cnt_x],r]}$ 这个前缀的集合中，那么区间 $[l_i,r_i]$ 答案就是 $r$ 扫到 $r_i$ 时 $cnt_x\ge l_i$ 的 $x$ 的个数。

考虑 $r\to r+1$ 对 $cnt$ 的影响，相当于从 $a_{r+1}$ 开始在值域上往后遍历，将前缀最大值的位置 $p_{1},p_2,p_3,\dots,p_k$ 找出来，然后将 $cnt'_{p_1}:= 0,cnt'_{p_2}:=cnt_{p_1},\dots,cnt'_{p_k}:=cnt_{p_{k-1}}$，然后令 $cnt'_{a_{r+1}}:=i$。

这其实是 AT_joisc2016_h 回転寿司 的 $l=a_{r+1},r=n,A=0$ 版本，最后多一步将 $cnt_{a_{r+1}}$ 改为 $i$。而求答案可以用树状数组维护每个 $y$ 在 $cnt$ 数组中出现过 $ct_y$ 次，那么单步扫描线相当于将 $ct_{i}$ 加一，然后将结束后的 $A'$ 的 $ct_{A'}$ 减一。

做法考虑分块，假设块长为 $B$。

对于整块，一个数进入一个块后出来的数显然只和这个块的最大值有关系，那么每个块开个大根堆，每次若 $A$ 比堆顶小则交换一下 $A$ 和堆顶。

对于散块，简单分讨可以发现对于两次对整块的修改 $x,y$，先做 $A=x$ 再做 $A=y$ 和先做 $A=y$ 再做 $A=x$ 的结果是一样的，所以不妨钦定是从小到大操作。具体的，把对整块的操作存进一个小根堆，然后从左往右遍历块内的 $a_i$，若 $a_i$ 比堆顶大，那么就交换 $a_i$ 和堆顶。这样就可以在 $O(B\log n)$ 的复杂度重构某个块，从而暴力进行散块的修改。

那么总复杂度为 $O(\frac{n^2}{B}\log n+nB\log n)$，所以 $B$ 应取 $\sqrt n$。不过由于修改整块常数较小（只用进行至多一次交换堆顶操作），所以 $B$ 可以开小一点。

回到本题，再用树状数组维护 $ct$ 即可做到 $O(n\sqrt n\log n+q\log n)$，也可以用修改 $O(\sqrt n)$ 查询 $O(1)$ 的前缀和分块做到 $O(n\sqrt n\log n+q)$。

代码如下：

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

template<typename T>
inline void read(T &x)
{
	x=0;
	T w=1;
	char c=getchar();
	while(c<'0'||c>'9') w=(c=='-'?-w:w),c=getchar();
	while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
	x*=w;
}

const int S=100005,BS=150,QS=1000005;

int n,q;
int a[S],c[S];
int lb[S/BS+5],rb[S/BS+5];
priority_queue<int> b[S/BS+5],que[S/BS+5];
vector<pair<int,int> > vec[S];
int tr[S],ans[QS];

inline void dwntag(int u)
{
	if(que[u].empty()) return;
	int l=lb[u],r=rb[u];
	for(int i=l;i<=r;i++)
	{
		int x=-que[u].top();
		if(c[i]>x)
		{
			swap(c[i],x);
			que[u].pop();
			que[u].push(-x);
		}
	}
	while(!que[u].empty()) que[u].pop();
}

inline void rebuild(int u)
{
	int l=lb[u],r=rb[u];
	while(!b[u].empty()) b[u].pop();
	for(int i=l;i<=r;i++) b[u].push(c[i]);
}

inline int doit(int l,int x)
{
	int ul=(l-1)/BS+1;
	if(rb[ul]==n)
	{
		dwntag(ul);
		for(int i=l;i<=n;i++) if(c[i]>x) swap(c[i],x);
		rebuild(ul);
		return x;
	}
	dwntag(ul);
	for(int i=l;i<=rb[ul];i++) if(c[i]>x) swap(c[i],x);
	rebuild(ul);
	for(int i=ul+1;i<=(n-1)/BS+1;i++)
	{
		int mx=b[i].top();
		if(mx>x)
		{
			que[i].push(-x);
			swap(mx,x);
			b[i].pop();
			b[i].push(mx);
		}
	}
	return x;
}

inline void addtr(int p,int x){for(int i=p;i<=n;i+=i&-i) tr[i]+=x;}
inline int quetr(int p)
{
	int res=0;
	for(int i=p;i>=1;i-=i&-i) res+=tr[i];
	return res;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	read(n),read(q);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i+=BS)
	{
		int u=(i-1)/BS+1;
		lb[u]=(u-1)*BS+1,rb[u]=min(u*BS,n);
		rebuild(u);
	}
	for(int i=1;i<=q;i++)
	{
		int l,r;
		read(l),read(r);
		vec[r].emplace_back(l,i);
	}
	for(int i=1;i<=n;i++)
	{
		int del=doit(a[i],0);
		int u=(a[i]-1)/BS+1;
		dwntag(u);
		c[a[i]]=i;
		rebuild(u);
		if(del!=0) addtr(n-del+1,-1);
		addtr(n-i+1,1);
		for(auto t:vec[i]) ans[t.second]=quetr(n-t.first+1);
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
	return 0;
}