Відповідність масивів#12302

Відповідність масивів (Розбір)

Автор проблеми:	De3b0o
Підготовлено:	De3b0o
Редаговано:	Hasan Saleh (MathModel)

Рішення

Твердження: Якщо ми виберемо діапазон $(l, r)$ (l,r) і ціле число $x$ для виконання операції, то завжди оптимально, щоб $b_{l} - a_{l} = b_{r} - a_{r} = x$ b_l - a_l = b_r - a_r = x.

Доказ: Припустимо, ми вибрали діапазон $(l, r)$ (l,r) і будь-яке ціле число $x$ , якщо $b_{l} - a_{l} \neq = x$ b_l - a_l \neq x, ми можемо просто виконати ту ж саму операцію на діапазоні $(l + 1, r)$ (l+1,r), і остаточна відповідь або залишиться такою ж, або збільшиться на $1$ . Те ж саме стосується $r$ .

Позначимо $p_{i}$ p_i як кількість індексів $j$ , де $j \leq i$ j \le i і $a_{j} = b_{j}$ a_j = b_j. А $q_{i}$ q_i як кількість індексів $j$ , де $j < i$ j < i і $b_{j} - a_{j} = b_{i} - a_{i}$ b_j - a_j = b_i - a_i.

Тепер для будь-якого діапазону $l, r$ , де $b_{r} - a_{r} = b_{l} - a_{l}$ b_r - a_r = b_l - a_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})$ p_n - p_r + p_{l-1} + q_r + 1 - q_l = p_n - p_r + q_r + 1 +(p_{l-1}-q_l)

Отже, якщо ми зафіксуємо $r$ , відповідь буде $co n s t + (p_{l - 1} - q_{l})$ const + (p_{l-1}-q_l), ми можемо просто вибрати $l$ , яке дає максимальне значення $p_{l - 1} - q_{l}$ p_{l-1}-q_l.

Складність $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
    }
}