题目
题目描述
众所周知，数学组有一个神犇叫做 HSY。
一天他对 XYK 说：“听说你数学很好，那我出一道数学题考考你。”
“给定一个包含 $n$ 个互不相同的数的序列 $a$，定义序列 $b$ 为 $b_i=\max\limits_{j<i,a_j<a_i}b_j+1$，且 $b_1=1$。”
“定义‘$k$ 号序列’为：满足对应的 $b$ 序列为连续自然数的长度为 $k$ 的字典序最小的 $a$ 的子序列。”
“给定 $m$ 次询问，每次询问 $i$ 号序列与 $j$ 号序列的最长公共子序列长度。”
XKY 冥思苦想也没能想出，在听到题解后觉得自己是个傻逼。
现在他想用这道题考考你。
输入格式
第一行两个正整数 $n,m$。
第二行 $n$ 个整数表示 $a$。
接下来 $m$ 行每行两个正整数 $i,j$ 表示询问。
输出格式
$m$ 行，每行一个整数表示答案。
输入输出样例 #1
输入 #1
1
2
3
4
7 2
2 6 7 3 4 5 1
3 4
3 1
输出 #1
1
2
3
0
说明/提示
样例解释
$a$ 对应的序列 $b$ 为 $\langle1,2,3,2,3,4,1\rangle$。
$3$ 号序列为 $\langle2,3,4\rangle$。
$4$ 号序列为 $\langle2,3,4,5\rangle$。
$1$ 号序列为 $\langle1\rangle$。
数据范围
对于 $10\%$ 的数据，$n,m\leq10$。
对于 $20\%$ 的数据，$n,m\leq1000$。
对于 $100\%$ 的数据，$n,m\leq500000$。
附件下载
题解
题意分析
首先分析序列 $b$，显然就是求最长上升子序列，$b_i$ 表示以 $a_i$ 结尾的最长上升子序列的长度。
而所谓“$k$ 号序列”，即字典序最小的长度为 $k$ 的上升子序列。
不妨令上升子序列中，$a_i$ 接在 $a_j$ 后面，则可以就此关系画出一个森林。
原来的 $b_i$ 此时便成为了节点 $i$ 的深度。
那么询问 $x,y$ 时，只需要找到一个深度为 $x$ 的节点 $id_x$ 和一个深度为 $y$ 的节点 $id_y$，求出其 LCA 的深度即可。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=500000,M=500000;
int n,m,a[N+1],b[N+1],id[N+1],f[N+1][__lg(N+1)+1];
//dp[i]:长度为 i 的lis结尾的数
int len,dp[N+1];
//倍增 LCA
int lca(int u,int v){
if(b[u]<b[v]){
swap(u,v);
}
for(int i=__lg(b[u]-b[v]);i>=0;i--){
if(b[f[u][i]]>=b[v]){
u=f[u][i];
}
}
if(u==v){
return u;
}
for(int i=__lg(b[u]);i>=0;i--){
if(f[u][i]!=f[v][i]){
u=f[u][i],v=f[v][i];
}
}
return f[u][0];
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
}
//b:即求 lis
for(int i=1;i<=n;i++){
b[i]=lower_bound(dp+1,dp+len+1,a[i])-dp;
len=max(len,b[i]);
dp[b[i]]=a[i];
}
for(int i=1;i<=n;i++){
//id[x]:x最晚出现的位置,保障字典序最小
id[b[i]]=i;
f[i][0]=id[b[i]-1];
}
for(int i=1;(1<<i)<=n;i++){
for(int x=1;x<=n;x++){
f[x][i]=f[f[x][i-1]][i-1];
}
}
while(m--){
int x,y;
scanf("%d %d",&x,&y);
//将出现的位置做成一个树,公共子序列即求lca。
printf("%d\n",b[lca(id[x],id[y])]);
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
