UOJ180 【UR #12】实验室外的攻防战

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！

题目链接：http://uoj.ac/problem/180

正解：线段树维护区间最值

解题报告：

考场上面，大胆猜了一发结论，只要a、b这两个序列的同一个值之间的最小值=这个值，则有解，否则无解，就变成了数据结构大裸题QAQ…

具体证明就略辣...

//It is made by ljh2000

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <set>

#include <string>

#include <complex>

using namespace std;

typedef long long LL;

#define RG register

const int MAXN = 1000011;

const int inf = (1<<30);

int n,a[MAXN],b[MAXN],c[MAXN],minl,ql,qr;

struct node{

	int minl;

}A[MAXN*3];

inline int getint(){

    RG int w=0,q=0; RG char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();

    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;

}

inline void build(RG int root,RG int l,RG int r){

	if(l==r) { A[root].minl=a[l]; return ; }

	RG int mid=(l+r)>>1; RG int lc=root*2,rc=lc+1;

	build(lc,l,mid); build(rc,mid+1,r);

	A[root].minl=min(A[lc].minl,A[rc].minl);

}

inline void query(RG int root,RG int l,RG int r){

	if(ql<=l && r<=qr) {

		minl=min(minl,A[root].minl);

		return ;

	}

	RG int mid=(l+r)>>1; RG int lc=root*2,rc=lc+1;

	if(ql<=mid) query(lc,l,mid);

	if(qr>mid) query(rc,mid+1,r);

}

inline void update(RG int root,RG int l,RG int r){

	if(l==r) {

		A[root].minl=inf;

		return ;

	}

	RG int lc=root*2,rc=lc+1; RG int mid=(l+r)>>1;

	if(qr<=mid) update(lc,l,mid); else update(rc,mid+1,r);

	A[root].minl=min(A[lc].minl,A[rc].minl);

}

inline void work(){

	n=getint(); RG int x;

	for(int i=1;i<=n;i++) a[i]=getint(),c[a[i]]=i;

	for(int i=1;i<=n;i++) b[i]=getint();

	build(1,1,n);

	for(int i=1;i<=n;i++) {

		x=b[i]; ql=1; qr=c[x]; minl=inf; query(1,1,n);

		if(minl!=x) { puts("NO"); return ; }

		update(1,1,n);

	}

	puts("YES");

}

int main()

{

    work();

    return 0;

}