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}$，所以满足条件。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 using namespace std;

 #define maxn 20000010

 #define MAXN 2000100

 #define llg int

 #define inf 0x7fffffff

 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

 llg n,m,minl[maxn],a[MAXN],c[MAXN],rank[MAXN];

 llg min_(llg o,llg l,llg r,llg L,llg R)

 {

     if (l>=L && r<=R)

     {

         return minl[o];

     }

     llg lc=o<<,rc=o<<|,mid=(l+r)>>;

     llg ans=inf;

     if (L<=mid) ans=min(ans,min_(lc,l,mid,L,R));

     if (R>mid) ans=min(ans,min_(rc,mid+,r,L,R));

     return ans;

 }

 void add(llg o,llg l,llg r,llg wz,llg val)

 {

     if (l==r)

     {

         minl[o]=val;

         return ;

     }

     llg lc=o<<,rc=o<<|,mid=(l+r)>>;

     if (wz<=mid) add(lc,l,mid,wz,val);

     if (wz>mid) add(rc,mid+,r,wz,val);

     minl[o]=min(minl[lc],minl[rc]);

 }

 inline int getint()

 {

        int w=,q=;

        char c=getchar();

        while((c<'' || c>'') && c!='-') c=getchar();

        if (c=='-')  q=, c=getchar();

        while (c>='' && c<='') w=w*+c-'', c=getchar();

        return q ? -w : w;

 }

 int main()

 {

     //yyj("C");

     cin>>n;

     for (llg i=;i<=n;i++) a[i]=getint();

     for (llg i=;i<=n;i++) c[i]=getint();

     for (llg i=;i<=n;i++) rank[c[i]]=i;

     for (llg i=;i<=;i++) minl[i]=inf;

     for (llg i=;i<=n;i++)

     {

         llg x=rank[a[i]];

         llg v=min_(,,n,x,n);

         if (a[i]>v) {cout<<"NO"; return ;}

         add(,,n,x,a[i]);

     }

     cout<<"YES";

     return ;

 }

巴特西

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

最新文章

热门文章