题目描述
Two arrays u and v each with m distinct elements are called equivalent if and only if RMQ(u,l,r)=RMQ(v,l,r) for all 1≤l≤r≤m1≤l≤r≤m
where RMQ(w,l,r) denotes the index of the minimum element among wl,wl+1,…,wr.
Since the array contains distinct elements, the definition of minimum is unambiguous.
Bobo has two arrays a and b each with n distinct elements. Find the maximum number p≤n where{a1,a2,…,ap} and {b1,b2,…,bp} are equivalent.
输入描述:
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains an integer (n.)
The second line contains (n) integers (a1,a2,…,an)
The third line contains (n) integers (b1,b2,…,bn)
- (1≤n≤10^5)
- (1≤ai,bi≤n)
- ({a1,a2,…,an}) are distinct.
- ({b1,b2,…,bn}) are distinct.
- The sum of n does not exceed (5×10^5).
输出描述:
For each test case, print an integer which denotes the result.
题解
考虑一个数(a_i)会对哪些区间的(RMQ)造成影响，显然是向左直到第一个比它小的数的位置为止的区间都有影响，那么就有一种判定方法，顺次枚举(i)，判断(a_i)和(b_i)向左能影响到的区间，如果能影响到的区间不是完全相同的那么肯定有一个(RMQ)不同。
所以现在的问题就变成了维护一个数据结构，可以求出前缀(max)。显然单调栈，单调队列，BIT都可以维护（BIT的话以数值为BIT的下标，原数组下标为储存的值，问题就变成了前缀(max)）
用BIT的话是(O(nlog n))的。单调队列和单调栈的话是(O(n))的。
标算是单调队列，还提供了另一个做法：
题中的“equivalent”等价于笛卡尔树相同，
二分答案，比较两个前缀的笛卡尔树 (O(n log n))
题解中对单调队列的做法的证明也用了笛卡尔树。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], b[N];
int n;
/*
需要一个数据结构，往前找找到第一个数比它小的，返回位置
*/
namespace BIT {
int c[N][2];
#define lowbit(i) (i & -i)
void add(int x, int v, int id) {
for(int i = x; i <= n; ++i) c[i][id] = max(c[i][id], v);
}
int query(int x, int id) {
int ans = 0;
for(int i = x; i; i -= lowbit(i)) ans = max(ans, c[i][id]);
return ans;
}
} using namespace BIT;
int main() {
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; ++i) c[i][0] = c[i][1] = 0;
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 1; i <= n; ++i) scanf("%d", &b[i]);
int i;
for(i = 1; i <= n; ++i) {
int l = query(a[i], 0), r = query(b[i], 1);
if(l != r) break;
add(a[i], i, 0); add(b[i], i, 1);
}
printf("%d
", --i);
}
}