2019牛客多校第一场 A.Equivalent Prefixes

题目描述

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(n\log 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\n", --i);

	}

}

巴特西

2019牛客多校第一场 A.Equivalent Prefixes

题目描述

输入描述:

输出描述:

题解

最新文章

热门文章