Захопливі масиви (Розбір)

Розв'язок

Факт 1 : оскільки ми можемо застосовувати операцію будь-яку кількість разів , ми можемо переставляти обидва масиви як завгодно.

Умова [a_1 , a_2 , ... , a_n] = [b_1 , b_2 , ... , b_i] для кожного $i$ (1 \le i \le \text{min}(n,m)) означає, що довжина найдовшого спільного префікса між $a$ та $b$ має дорівнювати \text{min}(n,m).

Тепер нехай $len$ — довжина найдовшого спільного префікса, freq[x][0] — частота числа $x$ у масиві $a$, а freq[x][1] — частота числа $x$ у масиві $b$.

Тепер, якщо ми хочемо збільшити $len$ на $y$, використовуючи значення $x$, ми повинні взяти $y$ елементів зі значенням $x$ з масиву $a$ та $y$ елементів зі значенням $x$ з масиву $b$; максимальне $y$, яке ми можемо отримати, дорівнює \text{min}(freq[x][0] , freq[x][1]), тому кожне число $x$ збільшує $len$ на \text{min}(freq[x][0] , freq[x][1]).

Після використання всіх чисел $x$, де (1 \le x \le n+m), якщо $len$ дорівнює \text{min}(n,m), відповідь — «YES», інакше — «NO».

Часова складність : \mathcal{O}(n+m).

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define F first
#define S second
using namespace std;
const int N = 2e5 + 1;
const int M = 1e9 + 7;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc = 1;
    cin>>tc;
    while(tc--)
    {
        int n,m;
        cin>>n>>m;
        int freq[n+m+1][2] , len = 0;
        memset(freq , 0 , sizeof freq);
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            freq[x][0]++;
        }
        for(int i=1;i<=m;i++)
        {
            int x;
            cin>>x;
            freq[x][1]++;
        }
        for(int i=1;i<=n+m;i++)
        {
            len += min(freq[i][0] , freq[i][1]);
        }
        cout<<(len == min(n , m) ? "YES" : "NO")<<endl;
    }
}