Array Matching#12302

Array Matching (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	Hasan Saleh (MathModel)

Həll

İddia: Əgər $(l, r)$ (l,r) aralığını və bir tam ədəd $x$ seçsək, əməliyyatı yerinə yetirmək üçün, o zaman həmişə optimaldır ki, $b_{l} - a_{l} = b_{r} - a_{r} = x$ b_l - a_l = b_r - a_r = x.

Sübut: Gəlin $(l, r)$ (l,r) aralığını və istənilən tam ədəd $x$ seçdiyimizi düşünək, əgər $b_{l} - a_{l} \neq = x$ b_l - a_l \neq x isə, $(l + 1, r)$ (l+1,r) aralığında eyni əməliyyatı yerinə yetirə bilərik və son cavab ya eyni olacaq, ya da $1$ artacaq. Eyni şey $r$ üçün də keçərlidir.

İndi $p_{i}$ p_i-ni $j \leq i$ j \le i olan indekslərin sayı kimi müəyyən edək, burada $a_{j} = b_{j}$ a_j = b_j. Və $q_{i}$ q_i-ni $j < i$ j < i olan indekslərin sayı kimi müəyyən edək, burada $b_{j} - a_{j} = b_{i} - a_{i}$ b_j - a_j = b_i - a_i.

İndi $l, r$ aralığı üçün, burada $b_{r} - a_{r} = b_{l} - a_{l}$ b_r - a_r = b_l - a_l, bu aralıqda əməliyyat yerinə yetirdikdən sonra array-in son cavabı:

$p_{n} - p_{r} + p_{l - 1} + q_{r} + 1 - q_{l} = p_{n} - p_{r} + q_{r} + 1 + (p_{l - 1} - q_{l})$ p_n - p_r + p_{l-1} + q_r + 1 - q_l = p_n - p_r + q_r + 1 +(p_{l-1}-q_l)

Beləliklə, $r$ -ni düzəltsək, cavab $co n s t + (p_{l - 1} - q_{l})$ const + (p_{l-1}-q_l) olacaq, maksimum $p_{l - 1} - q_{l}$ p_{l-1}-q_l dəyərini verən $l$ -ni seçə bilərik.

Mürəkkəblik $O (n \cdot lo g (n))$ \mathcal{O}(n \cdot \log(n)).


#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll, ll>
#define lin cout << "\n";
#define mid ((l + r) / 2)
#define lc (2 * x)
#define rc (2 * x + 1)
#define double long double

using namespace std;

const ll N = 5e5+9;

ll n,ans;
ll a[N],b[N];
ll p[N],q[N];
map<ll,ll> mp;
map<ll,ll> mx;

int main()
{
    d3
    ll T = 1;
    cin >> T;
    while(T--)
    {
        mp.clear();
        mx.clear();
        ans=0;
        cin >> n;
        for(int i = 1 ; n>=i ; i++)
            cin >> a[i];
        for(int i = 1 ; n>=i ; i++)
            cin >> b[i];
        for(int i = 1 ; n>=i ; i++)
        {
            p[i]=0;
            if(a[i]==b[i])
                p[i]=1;
            p[i]+=p[i-1];
            q[i]=mp[b[i]-a[i]];
            mp[b[i]-a[i]]++;
        }
        for(int i = 1 ; n>=i ; i++)
        {
            mx[b[i]-a[i]]=max(mx[b[i]-a[i]],p[i-1]-q[i]);
            ans=max(ans,q[i]+1+mx[b[i]-a[i]]+p[n]-p[i]);
        }
        cans
    }
}