2022杭电多校九 1003-Fast Bubble Sort（倍增+单调栈）

题目链接：杭电多校九 - Virtual Judge

题目：

 样例输入：

1
10 5
3 7 9 2 6 4 5 8 10 1
1 10
2 6
7 9
4 9
3 3

样例输出：

2
1
0
1
0

题意：给定任何一个长度为𝑁的数组𝐴 = (𝑎1, 𝑎2, . . . , 𝑎𝑛),令𝐵(𝐴)表示对𝐴进行一次bubble sort循环之后得到的数组。令𝑛𝑢𝑚(𝐴)表示从𝐴到𝐵(𝐴)最少需要移动元素(数组区间循环移位)的次数。给定一个1 − 𝑛的排列𝑃以及𝑞组1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛，求𝑛𝑢𝑚(𝑃 [𝑙, 𝑟])。

分析：现在假如我们有t个数a1,a2,……,at,我们对区间[1,t]进行一次循环左移，就相当于先用a1和a2换位，再用a1和a3换位……,再用a1和at换位，这个操作非常像我们冒泡排序的过程，通过分析这个我们就不难发现假如我们要询问num(P[l,r])，那么就先找到一个区间[l,x]进行一次循环左移，其中x是l后面第一个大于a[l]的数的前一个，前提是x不能等于l，也就是说区间[l,x]的长度至少是1，那么我们就可以定义一个不同于数学中的极值点，第i个点为极大值点的充分必要条件就是a[i]>a[i+1]。数学中的极大值点定义还要求a[i]>a[i-1]，这里不作要求，那么通过模拟不难发现𝑛𝑢𝑚(𝑃 [𝑙, 𝑟])就是[l,r]中递增极值点的个数。不妨假设递增极值点个数为n，那么这n个递增极值点就是我们的循环左移区间的左边界，这个模拟不难得到，那我们怎么求解一个区间中递增极大值点的个数呢？就是先用一个数组记录每一个位置后面出现的第一个极大值点，不妨记为f[i]吧。一开始写的是用单调栈记录每一个数后面第一个大于他的数的位置，然后倒着进行判断，如果第一个大于他的数的位置是当前数的后一个，那么这种情况就对应着区间长度为1的情况，我们就直接令f[i]=f[i+1]，否则f[i]就是i后面第一个大于等于i的数的位置，然后直接暴力跳，但是这样会超时，所以我们就需要对这种方式进行优化，这个时候我们就会想到倍增，也就是说设f[i][j]记录第i个位置的数后面第2^j个递增极大值点所在的位置，那么我们用倍增判断[l,r]内有多少个递增极大值点的复杂度就变为logn，这样复杂度就够了，需要注意的一个点是我们在倍增过程中的退出条件是f[l][i]<=r,有可能从l出发一次跳的比r大，这种状态对应的是两种情况，一种是区间[l,r]是递增的，那么这种情况下本身就不需要考虑，但是还有一种情况我们不得不考虑，就是[l,r]中存在一个极大值点，从这个极大值点找到下一个大于当前极大值点的位置是大于等于r的，如果我们不考虑这种情况我们就会少算答案。所以那这种情况怎么办呢？我们f[i][0]记录的是i后面能够跳到的第一个递增极大值点，这是不包含第i个位置的，而刚才这种情况我们是需要考虑到i这个位置的，所以我们需要新开一个ne[i]表示i后面（包含i）的第一个极大值点出现的位置，这样就可以O（1）判断倍增后的区间[l,r)中是否还有极大值点了。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
int st[N],tt,a[N];
int f[N][21];//f[i][j]记录第i个位置的数后面第2^j个递增极大值点所在的位置 
int mp[N],ne[N];//ne[i]记录第i个数及之后的数中出现的第一个极大值点的位置 
//注意：此处的极大值与数学中的极大值略有不同，此处的第i个位置为极大值点当且仅当a[i]>a[i+1],不要求a[i]>a[i-1] 
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,q;
		scanf("%d%d",&n,&q);
		tt=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			mp[a[i]]=i;
		}
		for(int i=n;i>=1;i--)//单调栈求每个数后面第一个比他大的数的位置 
		{
			while(tt&&a[i]>st[tt]) tt--;
			if(!tt) f[i][0]=n+1;
			else f[i][0]=mp[st[tt]];
			st[++tt]=a[i];
		}
		ne[n]=n+1;//后面没有极大值就默认极大值出现的位置是n+1 
		for(int i=n-1;i>=1;i--)
			if(f[i][0]==i+1)
			{
				f[i][0]=f[i+1][0];
				ne[i]=ne[i+1]; 
			}
			else ne[i]=i;
		for(int i=n-1;i>=1;i--)//倍增预处理 
		for(int j=1;j<=20;j++)
			f[i][j]=f[f[i][j-1]][j-1];
		while(q--)
		{
			int ans=0,l,r;
			scanf("%d%d",&l,&r);
			for(int i=20;i>=0;i--)
			{
				if(f[l][i]&&f[l][i]<=r)
				{
					l=f[l][i];
					ans+=1<<i;
				}
			}
			if(ne[l]<r) ans++;//如果区间[l,r-1]之间还有一个极大值，那么就还需要一次转移 
			printf("%d\n",ans);
		}
	}
	return 0;
}