用int正确longlongRE，线段树模拟费用流求条

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5 + 10;
ll a[N], b[N];
struct node
{
    ll x, y;
    bool operator<(const node &t) const
    {
        return a[x] + b[y] < a[t.x] + b[t.y];
    }
};
struct GG
{
    ll ma, mb;       // 区间花费最小的a[ma]和b[mb]
    ll la, lb;       // 满足a[la]是l-la的严格前缀最小值的最小值，b[lb]是r-lb的严格后缀最小值的最小值
    ll tag, mn;      // 区间加减的tag和区间最小值mn
    node va, vb, vc; // va是满足()的，vb是满足)(的（前提要求符合严格大于区间最小值，vc是)(不考虑要求
};
struct SEG
{
    GG tr[N * 4];
    GG pushup(GG L, GG R)
    {
        GG tmp;
        tmp.tag = 0;
        if (a[L.ma] < a[R.ma]) // 找最小a
            tmp.ma = L.ma;
        else
            tmp.ma = R.ma;
        if (b[L.mb] < b[R.mb]) // 找最小b
            tmp.mb = L.mb;
        else
            tmp.mb = R.mb;
        tmp.mn = min(L.mn, R.mn);                        // 取区间最小值
        tmp.va = min(node{L.ma, R.mb}, min(L.va, R.va)); // 满足要求的最优情况1
        tmp.vc = min(node{R.ma, L.mb}, min(L.vc, R.vc)); // 可能不满足要求的情况2
        tmp.vb = min(L.vb, R.vb);
        if (L.mn > R.mn)
        {
            tmp.vb = min(min(tmp.vb, L.vc), node{R.la, L.mb}); // 因为R的最小值小于L，所以L的vc一定就合法，同时{R.la,L.mb}一定合法
            if (a[L.ma] < a[R.la])
                tmp.la = L.ma;
            else
                tmp.la = R.la;
            tmp.lb = R.lb;
        }
        else if (L.mn < R.mn)
        {
            tmp.vb = min(min(tmp.vb, R.vc), node{R.ma, L.lb}); // 同上
            if (a[L.lb] < a[R.mb])
                tmp.la = L.lb;
            else
                tmp.la = R.mb;
            tmp.la = R.la;
        }
        return tmp;
    }
    void pushdown(ll u)
    {
        if (tr[u].tag)
        {
            tr[u << 1].tag += tr[u].tag, tr[u << 1].mn += tr[u].tag;
            tr[u << 1 | 1].tag += tr[u].tag, tr[u << 1 | 1].mn += tr[u].tag;
            tr[u].tag = 0;
        }
    }
    void build(ll u, ll l, ll r)
    {
        if (l == r)
        {
            tr[u] = {l, l, l, 0, 0, 0, node{l, l}, node{0, 0}, node{l, l}};
            return;
        }
        ll mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        tr[u] = pushup(tr[u << 1], tr[u << 1 | 1]);
    }
    void modify(ll u, ll l, ll r, ll p)
    {
        if (l == r)
            return;
        pushdown(u);
        ll mid = (l + r) >> 1;
        if (p <= mid)
            modify(u << 1, l, mid, p);
        else
            modify(u << 1 | 1, mid + 1, r, p);
        tr[u] = pushup(tr[u << 1], tr[u << 1 | 1]);
    }
    void modify1(ll u, ll l, ll r, ll L, ll R, ll p)
    {
        if (l > R or L > r)
            return;
        if (L <= l and r <= R)
        {
            tr[u].tag += p, tr[u].mn += p;
            return;
        }
        pushdown(u);
        ll mid = (l + r) >> 1;
        if (L <= mid)
            modify1(u << 1, l, mid, L, R, p);
        if (R > mid)
            modify1(u << 1 | 1, mid + 1, r, L, R, p);
        tr[u] = pushup(tr[u << 1], tr[u << 1 | 1]);
    }
} T;
ll n, k;
int main()
{
    cin >> n >> k;
    for (ll i = 1; i <= n; i++)
        cin >> a[i];
    for (ll i = 1; i <= n; i++)
        cin >> b[i];
    a[0] = b[0] = 0x3f3f3f3f3f3f3f3f;
    T.build(1, 1, n);
    ll ans = 0;
    while (k--)
    {
        ll x, y, del;
        if (T.tr[1].va < T.tr[1].vb)
        {
            x = T.tr[1].va.x, y = T.tr[1].va.y, del = 1;
        }
        else
        {
            x = T.tr[1].vb.x, y = T.tr[1].vb.y, del = -1;
        }
        ans += a[x] + b[y];
        a[x] = b[y] = 0x3f3f3f3f;
        T.modify(1, 1, n, x), T.modify(1, 1, n, y);
        T.modify1(1, 1, n, min(x, y), max(x, y) - 1, del);
    }
    cout << ans;
}