D. Subarray Sorting（區間極小+分析維護）

題目

題意：

    給兩個數組a,b。你可以使a的任意區間從小到大排序，判斷是否可以通過操作使得a數組變為b數組。

     1 ≤ n ≤ 3 ⋅ 1 0 5 , 1 ≤ a i ≤ n , 1 ≤ b i ≤ n 1≤n≤3⋅10^5,1≤a_i≤n,1≤b_i≤n 1≤n≤3⋅105,1≤ai​≤n,1≤bi​≤n

分析：

    我們考慮從左到右依次滿足a[i]==b[i]，對于一個b[i]來說，肯定是要在a數組中找到相應的值所在的位置x，若這個值[1,x]這個區間的最小值，那麼才可以移動過來，否則比它小的元素必然會阻礙他。為什麼是[1,x]呢？因為之前比對的元素放到了前面去，那麼那些未比對的元素實際上移動了，但是我們并沒有維護這個移動的過程，即所有未比對過在[1,x]這一區間的值的位置都在b[i]之後了。對于已經比對好的元素，即把他們放到了最前面去了，是以就可以不必考慮他們的存在，設為最大值即可。區間最小用線段樹維護一下即可。

#include <iostream>
#include <queue>
using namespace std;

queue<int> q[300005];
int b[300005];

struct node{
	int l,r,minx;
}a[300005*4];

void update(int x)
{
	a[x].minx = min(a[2*x].minx,a[2*x+1].minx); 
}

void build(int x,int l,int r)
{
	a[x].l = l;
	a[x].r = r;
	if( l == r )
	{
		a[x].minx = 0;
		return;
	}
	int mid = ( l + r ) / 2;
	build(2*x,l,mid);
	build(2*x+1,mid+1,r);
	update(x);
}

void change(int x,int l,int r,int k)
{
	if( a[x].l == l && a[x].r == r )
	{
		a[x].minx += k;
		return;
	}
	int mid = ( a[x].l + a[x].r ) / 2;
	if( l > mid ) change(2*x+1,l,r,k);
	else if( r <= mid ) change(2*x,l,r,k);
	else
	{
		change(2*x,l,mid,k);
		change(2*x+1,mid+1,r,k);
	}
	update(x);
}

int query(int x,int l,int r)
{
	if( a[x].l == l && a[x].r == r ) return a[x].minx;
	int mid = ( a[x].l + a[x].r ) / 2;
	if( l > mid ) return query(2*x+1,l,r);
	else if( r <= mid ) return query(2*x,l,r);
	else return min(query(2*x,l,mid),query(2*x+1,mid+1,r));
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while( t-- )
	{
		int n;
		cin >> n;
		build(1,1,n);
		for (int i = 1; i <= n; i++) 
		{
			while( !q[i].empty() ) q[i].pop();
		}
		for (int i = 1; i <= n; i++)
		{
			int x;
			cin >> x;
			q[x].push(i);
			change(1,i,i,x);
		}
		for (int i = 1; i <= n; i++)
		{
			cin >> b[i];
		}
		int flag = 0;
		for (int i = 1; i <= n; i++)
		{
			//cout << i << '\n';
			if( q[b[i]].empty() )
			{
				flag = 1;
				break;
			}
			int x = q[b[i]].front();
			q[b[i]].pop();
			int t = query(1,1,x);
			//cout << "asd " << x << ' ' <<t << '\n'; 
			if( t != b[i] )
			{
				flag = 1;
				break;
			}
			change(1,x,x,3e5);
		}
		if( flag ) cout << "NO" << '\n';
		else cout << "YES" << '\n';
	}
	return 0;
}