Educational Codeforces Round 67 (Rated for Div. 2)D. Subarray Sorting(线段树+思维)

题目链接
大意：给你两个数组 $a,b$a,b，第一个数组可以将任意子数组按非递减顺序排序，问你是否能变成第二个数组
思路：先将 $a$a数组建一个最小值线段树，然后我们遍历 $b$b数组，显然对于每个 $b_i$bi​，我们需要一个下标最小的等于当前元素的 $a_k$ak​来移动到 $i$i这个位置，那么我们先考虑 $b_1$b1​，显然，要想 $a$a数组与 $b_1$b1​匹配的数可以移动到 $1$1位置，那么 $a_k$ak​必然是 $mi{n}_{a_{1-k}}$mina1−k​​，否则不可能移动到 $1$1这个位置，那么这么想的话，我们每次对于成功匹配的 $k$k位置重新赋一个极大值，代表已经用过，我们每次遍历的 $b_i$bi​对于相应的 $a_k$ak​，都应该是 $mi{n}_{a_{1-k}}$mina1−k​​，如果都匹配成功即说明可以。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 3e5 +11;
int _,n,a[N],b[N],t[N<<2];
void build(int now,int l,int r,int pos,int d){
	if(l==r&&l==pos){
		t[now]=d;
		return ;
	}
	int mid=l+r>>1;
	if(pos<=mid)build(now<<1,l,mid,pos,d);
	else build(now<<1|1,mid+1,r,pos,d);
	t[now]=min(t[now<<1],t[now<<1|1]);
}
int g(int now,int l,int r,int x,int y){
	if(x<=l&&y>=r)return t[now];
	int mid=l+r>>1;
	int ans=1e9;
	if(x<=mid)ans=min(ans,g(now<<1,l,mid,x,y));
	if(y>mid)ans=min(ans,g(now<<1|1,mid+1,r,x,y));
	return ans; 
}
queue<int>q[N];
int s(){
	for(int i=1;i<=n;i++)q[a[i]].push(i);
	for(int i=1;i<=n;i++){
		if(q[b[i]].empty())return 0;
		int k=q[b[i]].front();
		q[b[i]].pop();
		int G=g(1,1,n,1,k);
		if(G<b[i])return 0;
		build(1,1,n,k,1e9);
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(false);
	for(cin>>_;_;_--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i],build(1,1,n,i,a[i]);
		for(int i=1;i<=n;i++)cin>>b[i];
		if(s())cout<<"YES\n";
		else cout<<"NO\n";
		for(int i=1;i<=n;i++){
			while(!q[a[i]].empty())q[a[i]].pop();
		}
	}	
	return 0;
}