http://uoj.ac/contest/25/problem/180

从前往后对比串A,B

当$A_i,B_i$不相同时找到$B_i$在A中的位置j

若$min{A_1,A_2,A_3......A_{j-1}}<A_j$说明$A_j$无法交换到位置i,就GG惹

否则把$A_j$设为INF

线段树维护区间取min,单点修改

#include<cstdio>
#include<iostream>
#include<algorithm>
using std::cin;
using std::cout;
using std::min;
using std::max;
#define INF 0x7fffffff
const int maxn = ;
int n;
inline int read() {
int x=,f=;
char c=getchar();
while(c<''||c>'') {
if(c=='-')f=-;c=getchar() ;
}
while(c<=''&&c>='')x=x*+c-'',c=getchar();
return x*f;
}
int a[maxn],b[maxn];
int pos[maxn];
int minn[(maxn<<)+] ;
void merge(int rt) {
minn[rt]=min(minn[rt<<],minn[rt<<|]);
}
void build(int l,int r,int rt) {
if(l==r) {
minn[rt]=a[l];return;
}
int mid = l+r>>;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
merge(rt);
}
int query(int l,int r,int rt,int tl,int tr) {
if(tl<=l&&tr>=r) {
return minn[rt];
}
int mid=l+r>>;
int ans=INF;
if(tl<=mid) ans=min(ans,query(l,mid,rt<<,tl,tr));
if(tr>mid) ans=min(ans,query(mid+,r,rt<<|,tl,tr));
return ans;
}
void modify(int l,int r,int rt,int pos) {
if(l==r) {
minn[rt]=INF;return;
}
int mid= l+r>>;
if(mid>=pos)modify(l,mid,rt<<,pos);
else if(mid<pos)modify(mid+,r,rt<<|,pos);
merge(rt);
}
int main() {
n=read();
for(int i=;i<=n;++i) a[i]=read(),pos[a[i]]=i;
for(int i=;i<=n;++i) b[i]=read();
build(,n,);
for(int i=;i<=n;++i) {
//if(a[i]!=b[i]) {
int p=pos[b[i]];
int tmp=query(,n,,,p);
if(tmp<b[i]) {
cout<<"NO"<<std::endl;return ;
}
else modify(,n,,p);
// }
}
cout<<"YES"<<std::endl;
return ;
}
05-19 17:24
查看更多