Array Matching#12302

Array Matching (Editorial)

Problem Author:	De3b0o
Prepared by:	De3b0o
Edited by:	Hasan Saleh (MathModel)

Solution

Claim: If we choose a range $(l, r)$ (l,r) and an integer $x$ to make the operation, then it's always optimal that $b_{l} - a_{l} = b_{r} - a_{r} = x$ b_l - a_l = b_r - a_r = x.

Proof: Let's say we choose a range $(l, r)$ (l,r) and any integer $x$ , if $b_{l} - a_{l} \neq = x$ b_l - a_l \neq x, we can just make the same operation on the range $(l + 1, r)$ (l+1,r) and the final answer will either be the same or increase by $1$ . The same goes for $r$ .

Let's define $p_{i}$ p_i as the number of indices $j$ where $j \leq i$ j \le i and $a_{j} = b_{j}$ a_j = b_j. And $q_{i}$ q_i as the number of indices $j$ where $j < i$ j < i and $b_{j} - a_{j} = b_{i} - a_{i}$ b_j - a_j = b_i - a_i.

Now for any range $l, r$ where $b_{r} - a_{r} = b_{l} - a_{l}$ b_r - a_r = b_l - a_l the final answer of the array after performing an operation on this range is:

$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)

So if we fix $r$ , the answer is $co n s t + (p_{l - 1} - q_{l})$ const + (p_{l-1}-q_l), we can just pick the $l$ that gives the maximum $p_{l - 1} - q_{l}$ p_{l-1}-q_l value.

Complexity $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
    }
}