首页 > 代码库 > UOJ【UR #12】实验室外的攻防战
UOJ【UR #12】实验室外的攻防战
题意：
给出一个排列$A$,问是否能够经过以下若干次变换变为排列$B$
变换：若${A_i> A_i+1}$,可以${swap(A_i,A_i+1)}$
考虑一个数字从A排列到B排列连出来的路径与其他数字是否相交，相交就表示大小关系需要判断，(类似于二维偏序)用线段树维护区间最小值即可。
权值为1，2的线分别与权值为4的线相交，而且4在它们左边，所以需要判断它们的大小关系，发现${4>1}$,${4>2}$，所以满足条件。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 2000001010 #define MAXN 200010011 #define llg int 12 #define inf 0x7fffffff13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);14 llg n,m,minl[maxn],a[MAXN],c[MAXN],rank[MAXN];15 16 llg min_(llg o,llg l,llg r,llg L,llg R)17 {18 if (l>=L && r<=R)19 {20 return minl[o];21 }22 llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1;23 llg ans=inf;24 if (L<=mid) ans=min(ans,min_(lc,l,mid,L,R));25 if (R>mid) ans=min(ans,min_(rc,mid+1,r,L,R));26 return ans;27 }28 29 void add(llg o,llg l,llg r,llg wz,llg val)30 {31 if (l==r)32 {33 minl[o]=val;34 return ;35 }36 llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1;37 if (wz<=mid) add(lc,l,mid,wz,val);38 if (wz>mid) add(rc,mid+1,r,wz,val);39 minl[o]=min(minl[lc],minl[rc]);40 }41 inline int getint()42 {43 int w=0,q=0;44 char c=getchar();45 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar();46 if (c==‘-‘) q=1, c=getchar();47 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar();48 return q ? -w : w;49 }50 int main()51 {52 //yyj("C");53 cin>>n;54 for (llg i=1;i<=n;i++) a[i]=getint();55 for (llg i=1;i<=n;i++) c[i]=getint();56 for (llg i=1;i<=n;i++) rank[c[i]]=i;57 for (llg i=1;i<=20000000;i++) minl[i]=inf;58 for (llg i=1;i<=n;i++)59 {60 llg x=rank[a[i]];61 llg v=min_(1,1,n,x,n);62 if (a[i]>v) {cout<<"NO"; return 0;}63 add(1,1,n,x,a[i]);64 }65 cout<<"YES";66 return 0;67 }
UOJ【UR #12】实验室外的攻防战
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。