例题
序列u，v 对于[1,ans]上所有的[L,R](1<=L<=R<=ans<=n)
都满足RMQ(u,L,R)=RMQ(v,L,R)
求max(ans);
分析：考虑判断两个序列的前缀笛卡尔树是否相等
注意，如果前缀笛卡尔树相等，则可以判断每一个栈深都相同，想想为什么？、
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
| #include <bits/stdc++.h>
#include<stdint.h>
#define int long long
#define scan(n) scanf("%lld", &(n))
#define scann(n, m) scanf("%lld%lld", &(n), &(m))
#define scannn(a, b, c) scanf("%lld%lld%lld", &(a), &(b), &(c))
#define prin(n) printf("%lld", (n))
#define pb push_back
#define mp make_pair
#define ms(a) memset(a, 0, sizeof(a))
#define fo(i, a, b) for (int i = (a); i <= (b); i++)
#define ro(i, a, b) for (int i = (a); i >= (b); i--)
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e5+100;
int n;
int a[maxn],b[maxn];
int s1[maxn],s2[maxn];
int32_t main() {
while(scan(n)!=EOF){
fo(i,1,n)scan(a[i]);
fo(i,1,n)scan(b[i]);
int head1=1,head2=1,tail1=1,tail2=1;
s1[head1]=s2[head2]=inf;
int maxpos=1;
fo(i,1,n){
while(head1<=tail1&&s1[tail1]>a[i])tail1--;
while(head2<=tail2&&s2[tail2]>b[i])tail2--;
if(tail1!=tail2)break;
s1[++tail1]=a[i],s2[++tail2]=b[i];
maxpos=i;
}
cout<<maxpos<<endl;
}
return 0;
}
|
笛卡尔树习题
http://acm.hdu.edu.cn/showproblem.php?pid=6305
https://blog.csdn.net/zhaiqiming2010/article/details/80245872