并不对劲的复健训练-CF1187D

题目大意

有两个长度为\(n\)的序列\(a_1,...,a_n\)，\(b_1,...,b_n\)（\(a,b\leq n\leq 3\times 10^5\) ）。一次操作是选取 \([l,r]\) ，将 \(a_l,...,a_r\) 排序。问能否通过若干次操作把 \(a_1,...,a_n\) 变得和 \(b_1,...,b_n\) 一样。

题解

这个人讲得很清楚

首先，如果\(a,b\)中每个数的出现次数不一样，那么一定不能。

其余的部分的问题在于能不能通过交换\(a\)中一些数的位置使\(a\)变得和\(b\)一样。

设\(a\)中两个位置\(i,j\)的数在\(b\)中的位置为\(i',j'\)。

当\(i<j\)且\(i'>j'\)时，要想使\(a,b\)相同必须交换\(i,j\)的位置，一定存在一次操作使\([i,j]\in[l,r]\)。

当\(a_i<a_j\)且\(i'>j'\)时，如果存在一次操作\([i,j]\in[l,r]\)，那么\(a_i\)就会被换到\(a_j\)左边，而且没法再换回来了，所以此时对于任意一次操作都没有\([min(i,j),max(i,j)]\in[l,r]\)。

所以当存在\(a_i<a_j\)且\(i<j\)且\(i'>j'\)时，一定没有合法解。

想要判断这部分，可以从左往右扫序列\(b\)，对于\(b_i\)，设\(b_i\)在\(a\)中目前第一次出现的位置为\(p(i)\)，若\(min\{a_j|j\in[1,p(i)]\}<b_i\)那么就没有合法解；反之，将\(a_{p(i)}\)改为\(+inf\)，继续判断剩下的。

代码

#include<algorithm>

#include<cmath>

#include<complex>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define view(u,k) for(int k=fir[u];~k;k=nxt[k])

#define LL long long

#define maxn 300007

#define ls (u<<1)

#define rs (u<<1|1)

#define mi (l+r>>1)

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)&&ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

    return x*f;

}

void write(int x)

{

    if(x==0){putchar('0'),putchar(' ');return;}

    int f=0;char ch[20];

    if(x<0)putchar('-'),x=-x;

    while(x)ch[++f]=x%10+'0',x/=10;

    while(f)putchar(ch[f--]);

    putchar(' ');

    return;

}

int t,n,a[maxn],b[maxn],tr[maxn<<2],ta[maxn],tb[maxn],fir[maxn],nxt[maxn];

void pu(int u){tr[u]=min(tr[ls],tr[rs]);}

void add(int u,int l,int r,int x,int k)

{

	if(x<=l&&r<=x){tr[u]=k;return;}

	if(x<=mi)add(ls,l,mi,x,k);

	else add(rs,mi+1,r,x,k);

	pu(u);return;

}

int ask(int u,int l,int r,int x,int y)

{

	if(x<=l&&r<=y)return tr[u];

	int res=n+1;

	if(x<=mi)res=ask(ls,l,mi,x,y);

	if(y>mi)res=min(res,ask(rs,mi+1,r,x,y));

	return res;

}

void build(int u,int l,int r)

{

	if(l==r){tr[u]=a[l];return;}

	build(ls,l,mi),build(rs,mi+1,r),pu(u);return;

}

int main()

{

    t=read();

    while(t--)

    {

    	n=read();int ans=1;

    	rep(i,1,n)ta[i]=a[i]=read(),fir[i]=-1;

    	rep(i,1,n)tb[i]=b[i]=read();

    	sort(ta+1,ta+n+1),sort(tb+1,tb+n+1);

    	rep(i,1,n)if(ta[i]!=tb[i]){ans=0;break;}

    	if(!ans){puts("NO");continue;}

    	build(1,1,n);

    	dwn(i,n,1){nxt[i]=fir[a[i]],fir[a[i]]=i;}

		rep(i,1,n)

		{

			int pos=fir[b[i]],mn=ask(1,1,n,1,pos);fir[b[i]]=nxt[pos];

			if(mn<b[i]){ans=0;break;}

			add(1,1,n,pos,n+1);

		}

		if(!ans)puts("NO");

		else puts("YES");

	}

	return 0;

}

WAWAWAWA

1.将\(b\)分成很多段，每一段连续且不下降且尽可能长。若\(b\)一段中的每个数的个数和\(a\)对应这一段位置的每个数的个数不同，那么NO，否则YES。

2.最小的数无法往右走但往左走多远都行，…，最大的数无法往左走但往右走多远都行。计算\(a\)中每个数最多往右走几个、最多往左走几个，如果这个数在\(a\)中的位置和它在\(b\)中的位置的差距大于这个范围，就NO，否则YES。

3.正解，但没有判\(a，b\)整体上是不是所有数的个数一样。

4.正解，但是没有反着求“fir”“nxt”。

巴特西

并不对劲的复健训练-CF1187D

题目大意

题解

代码

WAWAWAWA

最新文章

热门文章