Replace
题面翻译
题目描述
给定一个长为 \(n\) 的序列 \(a_1,\ldots,a_n\)，其中对于任意的 \(i\) 满足 \(1 \leq a_i \leq n\)。
定义一个二元组函数如下：
\[f((l,r))=(\min\{a_l,\ldots,a_r\},\max\{a_l,\ldots,a_r\})(l \leq r) \]你需要回答 \(q\) 次询问，每次给定 \((l_i,r_i)\)，问其最少经过多少次 \(f\) 的调用（即 \((l,r) \rightarrow f((l,r))\)）使得 \((l_i,r_i)\) 变成 \((1,n)\)，若无解请输出 -1。
输入格式
第一行包含两个整数 \(n,q(1 \leq n,q \leq 10^5)\)，表示序列长度和询问次数。
第二行包含 \(n\) 个整数 \(a_i(1 \leq a_i \leq n)\)，表示序列 \(a\)。
接下来 \(q\) 行每行两个整数 \(l_i,r_i(1 \leq l_i \leq r_i \leq n)\)，表示每组询问。
输出格式
对每一个询问，输出其最小次数，或无解输出 -1。
样例解释
第一个样例中，\(a=\{2,5,4,1,3\}\)。
对于第一个询问，\((4,4) \rightarrow (1,1) \rightarrow (2,2) \rightarrow (5,5) \rightarrow (3,3) \rightarrow (4,4) \rightarrow \cdots\)，故无解。
对于第二个询问，已经有 \((l_i,r_i)=(1,n)\)，需要 \(0\) 次。
对于第三个询问，\((1,4) \rightarrow (1,5)\)，需要 \(1\) 次。
对于第四个询问，\((3,5) \rightarrow (1,4) \rightarrow (1,5)\)，需要 \(2\) 次。
对于第五个询问，\((4,5) \rightarrow (1,3) \rightarrow (2,5) \rightarrow (1,5)\)，需要 \(3\) 次。
对于第六个询问，\((2,3) \rightarrow (4,5) \rightarrow (1,3) \rightarrow (2,5) \rightarrow (1,5)\)，需要 \(4\) 次。
题目描述
You are given an integer array $ a_1,\dots, a_n $, where $ 1\le a_i \le n $ for all $ i $.
There's a "replace" function $ f $ which takes a pair of integers $ (l, r) $, where $ l \le r $, as input and outputs the pair \(f((l, r))=\left(\min\{a_l,a_{l+1},\dots,a_r\},\max\{a_l,a_{l+1},\dots,a_r\}\right)\).
Consider repeated calls of this function. That is, from a starting pair \((l, r)\) we get $ f((l, r)) $, then $ f(f((l, r))) $, then $ f(f(f((l,r)))) $, and so on.
Now you need to answer $ q $ queries. For the $ i $-th query you have two integers $ l_i $ and $ r_i $ \((1\le l_i\le r_i\le n)\). You must answer the minimum number of times you must apply the "replace" function to the pair \((l_i,r_i)\) to get $ (1, n) $, or report that it is impossible.
输入格式
The first line contains two positive integers $ n $ , $ q $ ( $ 1\le n,q\le 10^5 $ ) — the length of the sequence $ a $ and the number of the queries.
The second line contains $ n $ positive integers $ a_1,a_2,\ldots,a_n $ ( $ 1\le a_i\le n $ ) — the sequence $ a $ .
Each line of the following $ q $ lines contains two integers $ l_i $ , $ r_i $ ( $ 1\le l_i\le r_i\le n $ ) — the queries.
输出格式
For each query, output the required number of times, or $ -1 $ if it is impossible.
样例 #1
样例输入 #1
5 6
2 5 4 1 3
4 4
1 5
1 4
3 5
4 5
2 3
样例输出 #1
-1
0
1
2
3
4
样例 #2
样例输入 #2
6 3
2 3 4 6 1 2
5 6
2 5
2 3
样例输出 #2
5
1
3
样例 #3
样例输入 #3
5 3
3 2 2 4 1
2 5
1 3
1 5
样例输出 #3
-1
-1
0
提示
In the first example, $ n=5 $ and $ a=[2,5,4,1,3] $ .
For the first query: $ (4,4)\to(1,1)\to(2,2)\to(5,5)\to(3,3)\to(4,4)\to\ldots $ , so it's impossible to get $ (1,5) $ .
For the second query, you already have $ (1,5) $ .
For the third query: $ (1,4)\to(1,5) $ .
For the fourth query: $ (3,5)\to(1,4)\to(1,5) $ .
For the fifth query: $ (4,5)\to(1,3)\to(2,5)\to(1,5) $ .
For the sixth query: $ (2,3)\to(4,5)\to(1,3)\to(2,5)\to(1,5) $ .
有一个关键结论: \(f(l,r)=\bigcup\limits_{i=l}^{r-1}f(i,i+1)\)
证明是显然的。
注意到 \(f(1,n)=[1,n]\)，所以一个区间增到 \([1,n]\) 后不会再变短。具有一定的单调性。
考虑倍增。看着上面的结论，推广出 \(f^k(l,r)=\bigcup\limits_{i=l}^{r-1}f^k(i,i+1)\)（归纳法证明）。所以现在要对于所有 \(2^k\)，求出 \(f^{2^k}(l,r)\)。求并是可以 ST 表的，用 ST 表维护倍增的过程即可。\(f^{2^k}(l,r)=f^k(f^k(l,r))\)。
复杂度 \(O(nlog^2n+qlog n)\)，空间 \(O(nlog^2n)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,a[N],l,r,lg[N];
struct STbiao{
int st[30][N];
void init()
{
for(int i=1;i<=lg[n];i++)
for(int j=1;j+(1<<i)-1<n;j++)
st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-1)]);
}
int ask(int l,int r)
{
int k=lg[r-l+1];
return max(st[k][l],st[k][r-(1<<k)+1]);
}
}g[30],h[30];
int main()
{
scanf("%d%d",&n,&q);
for(int i=2;i<=n;i++)
lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=1;i<n;i++)
{
g[0].st[0][i]=-min(a[i],a[i+1]);
h[0].st[0][i]=max(a[i],a[i+1]);
}
g[0].init(),h[0].init();
for(int i=1;i<=20;i++)
{
for(int j=1;j<n;j++)
{
int l=-g[i-1].st[0][j],r=h[i-1].st[0][j];
if(l==r)
g[i].st[0][j]=-a[l],h[i].st[0][j]=a[l];
else
g[i].st[0][j]=g[i-1].ask(l,r-1),h[i].st[0][j]=h[i-1].ask(l,r-1);
}
g[i].init(),h[i].init();
}
while(q--)
{
scanf("%d%d",&l,&r);
if(l==1&&r==n)
puts("0");
else if(l==r)
puts("-1");
else
{
int ans=0,p,q;
for(int i=20;~i;--i)
if(~g[i].ask(l,r-1)||h[i].ask(l,r-1)^n)
p=-g[i].ask(l,r-1),q=h[i].ask(l,r-1),ans|=1<<i,l=p,r=q;
p=-g[0].ask(l,r-1),q=h[0].ask(l,r-1);
if(p==1&&q==n)
printf("%d\n",ans+1);
else
puts("-1");
}
}
}