【2019牛客多校補題計劃】第一場：A - Equivalent Prefixes

題目連結：

https://ac.nowcoder.com/acm/contest/881/A

題目大意：

兩個長度為 n n n的數組 u u u和 v v v，均由數字 1 − n 1-n 1−n構成，順序不一定相同。求最大的 q q q，滿足以下條件：

• q &lt; = n , n &lt; = 1 e 5 q&lt;=n,n&lt;=1e5 q<=n,n<=1e5
• 對于任意的滿足 1 &lt; = l &lt; = r &lt; = q 1&lt;=l&lt;=r&lt;=q 1<=l<=r<=q的 l l l和 r r r，有 R M Q ( u , l , r ) = R M Q ( v , l , r ) RMQ(u,l,r)=RMQ(v,l,r) RMQ(u,l,r)=RMQ(v,l,r)。
• R M Q ( u , l , r ) RMQ(u,l,r) RMQ(u,l,r)的值表示數組 u u u的 [ l , r ] [l,r] [l,r]區間中最小值的索引。

解題思路：

出現數組中大量的 R M Q RMQ RMQ查詢就可以考慮嘗試笛卡爾樹。笛卡爾樹可以簡單地擷取 R M Q RMQ RMQ的相關資訊，比如已知區間求最小值（或其索引）隻要找到這兩個區間端點的LCA，已知一個值求以這個值為最小值的所有區間，等等。

此題根據樣例嘗試手畫笛卡爾樹，很快發現當 q q q符合條件時，兩棵笛卡爾樹結構是一樣的。

是以隻要二分答案，check中構造笛卡爾樹，構造完判斷樹是否相同即可。

複雜度 O ( N l o n g N ) O(NlongN) O(NlongN)。

AC代碼：

#include <stdio.h>
#include <stdlib.h>
int a[100005],b[100005];

typedef struct node{
	struct node *l;
	struct node *r;
	struct node *p;
	int val;
}node;

node* create_node(node *p,int val)
{
	node *n = (node*)malloc(sizeof(node));
	n->l=NULL;n->r=NULL;
	n->p = p;n->val = val;
	return n;
}

node* tree_insert(node *root,int val)
{
	node *now = root;
	if (val<now->val)
	{
		node *new_node = create_node(NULL,val);
		new_node->l = root;
		return root = new_node;
	}
	else
	{
		while(now->val<val)
		{
			if (now->r==NULL)
			{
				now->r = create_node(now,val);
				return root;
			}
			now = now->r;
		}
		node *new_node = create_node(now->p,val);
		new_node->l = now;
		now->p->r = new_node;
		return root;
	}
}

bool is_same(node *p1,node *p2)
{
	if (p1==NULL&&p2==NULL)
		return 1;
	else if(p1!=NULL&&p2!=NULL)
		return is_same(p1->l,p2->l)&&is_same(p1->r,p2->r);
	else
		return 0;
}

int check(int mid)
{
	int p=1;
	node *root_a = create_node(NULL,a[1]);
	node *root_b = create_node(NULL,b[1]);
	for (p=2;p<=mid;p++)
	{
		root_a = tree_insert(root_a,a[p]);
		root_b = tree_insert(root_b,b[p]);
	}
	if (is_same(root_a,root_b))return 1;
	else return 0;
}

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for (int i=1;i<=n;i++)scanf("%d",&a[i]);
		for (int i=1;i<=n;i++)scanf("%d",&b[i]);
		int l=2,r=n+1,mid;
		while(l<r)
		{
			mid=(l+r)/2;
			if (check(mid))l=mid+1;
			else r=mid;
		}
		printf("%d\n",r-1);
	}
}