2019 牛客多校 第一场 A、Equivalent Prefixes
题意，如果两个序列中所有子区间的最小值的下标都相等的话，我们就认为他们是这两个序列是相等的。
给你两个长度为 
1、首先考虑二分，那么我们如何判断这个区间是否相等？
2、线段树 or RMQ 找区间最小值，判断一下下标是否相等，如果不相等，直接return false;
3、如果相等呢？我们考虑在一个区间中取数。
a、两个数字都在最小值的左边/右边，那么我们只需要对左区间/右区间递归。
b、两个数字一个不大于最小值，一个不小于最小值，因为最小值一定是我们之前找到的最小值，所以这种取法显然成立。
4、如果区间长度为1，直接return true，防止爆栈
所以我们找的最小值就是下图
虽然这样可以过这个题，但似乎并不是最好的时间复杂度。
那么我们重新考虑一下，递归找最小值的过程，似乎和笛卡尔树建树差不多？并且笛卡尔树的建树似乎是 
但出题人似乎给出了
（先解释一下使用到的名词 极右端点：右儿子的右儿子的右儿子…… 极右链：右儿子和右儿子的右儿子和……组成的链）
1、笛卡尔树，每次插入一个元素大概可以分为两种情况：
a、这个元素的值大于极右端点，那么他就直接放在极右端点的右儿子上，并且极右端点变成这个节点。（此时极右链长度+1
（如上图，当我们插入18的时候，由于他大于15，所以他直接接在15的右儿子上）
b、这个元素的值小于极右端点，那么我们沿着极右端点找到第一个小于他的点（这个点在极右链上），并且取代他成为第一个小于他的点的右儿子，第一个小于他的点只前的右儿子就变成这个节点的左儿子。（此时极右链长度-n
（如上图，最后一个插入5的时候，依次找了 18 15 10 8 1，知道找到1，才发现了一个比5小的数字，所以此时，5变成1的有节点，之前的右节点变成5的左节点，并且此时，笛卡尔树的极右链长度是 1 5，长度为2）
2、总的来说，如果插入这个节点之后，笛卡尔树的极右链的长度还是不变的话，说明他们插入一个节点后，两个笛卡尔树的结构还是相等的。
3、每次插入一个节点，节点位置不同会导致极右链的长度也不同，并且他们是一对一的映射关系。
4、所以可以直接遍历建树，如果在某次插入节点后两个笛卡尔树的极右链的长度不同，说明加入的这个点不满足题意，所以答案是这个节点的下标减一。
------------------------------------------------
遍历建树（只维护极右链），O(n)做法：
语言：C++14 代码长度：570 运行时间： 156 ms 占用内存：2156K
#include <bits/stdc++.h>
using namespace std;
int a[100005], b[100005];
int pa[100005], pb[100005];
int main()
{
int n;
while (scanf("%d", &n) > 0)
{
int ans = n;
int cnta = 0, cntb = 0;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &b[i]);
for (int i = 1; i <= n; i++)
{
while (cnta && pa[cnta] > a[i])
cnta--;
pa[++cnta] = a[i];
while (cntb && pb[cntb] > b[i])
cntb--;
pb[++cntb] = b[i];
if (cnta != cntb)
{
ans = i - 1;
break;
}
}
printf("%d\n", ans);
}
} 二分+递归+线段树查最小值下标是否相等做法：
语言：C++ 代码长度：2357 运行时间： 727 ms 占用内存：9436K
#include <bits/stdc++.h>
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
#define ll long long
using namespace std;
struct node
{
int l;
int r;
int minn;
int index;
}que1[100005 * 4], que2[100005 * 4];
int a[100005];
int b[100005];
int n, ql, qr, val;
void up(int k)
{
if (que1[k << 1].minn < que1[k << 1 | 1].minn)
{
que1[k].minn = que1[k << 1].minn;
que1[k].index = que1[k << 1].index;
}
else
{
que1[k].minn = que1[k << 1 | 1].minn;
que1[k].index = que1[k << 1 | 1].index;
}
if (que2[k << 1].minn < que2[k << 1 | 1].minn)
{
que2[k].minn = que2[k << 1].minn;
que2[k].index = que2[k << 1].index;
}
else
{
que2[k].minn = que2[k << 1 | 1].minn;
que2[k].index = que2[k << 1 | 1].index;
}
}
void build(int left = 1, int right = n, int k = 1)
{
que1[k].l = left;
que1[k].r = right;
que2[k].l = left;
que2[k].r = right;
if (left == right)
{
que1[k].minn = a[left];
que1[k].index = left;
que2[k].minn = b[left];
que2[k].index = left;
return;
}
imid;
build(lson);
build(rson);
up(k);
}
struct in
{
int num;
int index;
};
in query1(int left = 1, int right = n, int k = 1)
{
if (qr < left || right < ql)
return in{ 999999,0 };
if (ql <= left && right <= qr)
return in{ que1[k].minn,que1[k].index };
imid;
in q = query1(lson);
in w = query1(rson);
if (q.num < w.num)
return q;
return w;
}
in query2(int left = 1, int right = n, int k = 1)
{
if (qr < left || right < ql)
return in{ 999999,0 };
if (ql <= left && right <= qr)
return in{ que2[k].minn,que2[k].index };
imid;
in q = query2(lson);
in w = query2(rson);
if (q.num < w.num)
return q;
return w;
}
bool judge(int left, int right)
{
if (left >= right)
return true;
int indexa = -1, indexb = -1;
ql = left; qr = right;
indexa = query1().index;
indexb = query2().index;
if (indexa != indexb)
return false;
bool ans = false;
if (judge(left, indexa - 1) && judge(indexa + 1, right))
ans = true;
return ans;
}
int main()
{
while (scanf("%d", &n) > 0)
{
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &b[i]);
}
build();
int l = 1, r = n;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (judge(1, mid))
l = mid;
else
r = mid;
}
if (judge(1, r))
l = r;
printf("%d\n", l);
}
} 
查看10道真题和解析