Yaxşı Ev Sahibi#12266
Daxil ol

Yaxşı Ev Sahibi (Həll təhlili)

Problem Müəllifi:

De3b0o

Hazırlayan:

De3b0o

Redaktə edən:

Hasan Saleh (MathModel)

Həll

Dəyər \frac{|h_i - x|}{c} -dən kiçikdir, çünki (1 \le h_i,x \le c), buna görə də optimal qapı həmişə minimum a_i dəyərinə sahib olacaq. Əgər minimum a_i dəyərinə sahib bir neçə qapı varsa, onda biz h_i-ni -ə ən yaxın olanı seçirik, çünki bu, ən az fraksiyanı verir.

Biz minimum a_i dəyərini izləyə bilərik və yeniləmələri və sorğuları vaxtında idarə edə bilərik.

Komplekslik \mathcal{O}((n+q) \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 pll pair<ll,ll>
#define lin cout << "\n";
 
using namespace std;

const ll N = 2e5+9;

ll n , c , q , mn=1e9;
ll a[N],h[N];
set<pll> s[N];
multiset<ll> se;

void upd(ll id , ll b , ll d)
{
    s[a[id]].erase({h[id],id});
    se.erase(se.find(a[id]));
    a[id]=b;
    h[id]=d;
    s[a[id]].in({h[id],id});
    se.in(a[id]);
    mn=*se.begin();
}

int main()
{
    d3
    cin >> n >> c;
    for(int i = 1 ; n>=i ; i++)
        cin >> a[i],se.in(a[i]),mn=min(mn,a[i]);
    for(int i = 1 ; n>=i ; i++)
        cin >> h[i],s[a[i]].in({h[i],i});
    cin >> q;
    while(q--)
    {
        ll t;
        cin >> t;
        if(t==1)
        {
            ll x;
            cin >> x;
            ll ans=1e10;
            ll idx;
            auto it = s[mn].lower_bound({x,-1});
            if(it!=s[mn].end())
            {
                ans=abs(it->F-x);
                idx=it->S;
            }
            if(it!=s[mn].begin())
            {
                it--;
                if(abs(it->F-x)<ans)
                    idx=it->S;
            }
            cout << idx << "\n";
        }
        else
        {
            ll id , b , d;
            cin >> id >> b >> d;
            upd(id,b,d);
        }
    }
}