在线求助大佬!!!!!!!!!!!

2021-02-24 08:40发布

【问题描述】 Captain正在精心构造两个序列并且让它们相似。我们令两个长度为n的序列u、v为相似的,当且仅当对于所有的1<=l<=r<=n,满足RMQ(u,l,r)=RMQ(v,l,r),其中RMQ(u,l,r)表示u序列中l到r这段区间的最小值所处的位置。那么相应的,captain构造出的序列中所有元素都是不相同的,但是有个小孩过来捣乱,他将两个序列后面分别添加了一些元素使得他们变成了两个排列。Captain非常生气,他想找回原来的序列,但是如果求出原来的序列最长能是多少就更好了。简要题意:给定两个排列A和B,求出它们的最大前缀p,满足a1,a2…ap、b1,b2…bp两个序列相似。

【输入描述】第一行一个整数n代表A、B数列的长度。第二行n个整数表示A序列。第三行n个整数表示B序列。数据保证A和B分别为两个1-n排列。

【输出描述】一行一个整数表示最大前缀长度p。

【样例输入】

[样例1]32 1 33 1 2

[样例2]53 1 5 2 45 2 4 3 1

【样例输出】

[样例1]3

[样例2]4

【数据范围】

对于20%的测试数据,n<=200

对于40%的测试数据,n<=2000

对于80%的测试数据,n<=100000

对于100%的测试数据,n<=500000

1条回答
拍乐云Pano
1楼-- · 2021-02-24 09:15

这个要用st表。