Dances (Hard Version)

发表于 分类于 ，

    对于每组数据，给定 $n$ ， $m$ 与数组 $a$ 的第 $2$ 到 $n$ 项和数组 $b$ 的第 $1$ 到 $n$ 项。你需要根据 $a$ 数组求出 $m$ 个 $c$ 数组的值，具体地：

    • $c[i]_1 = i$

    • $c[i]_j = a_j (2 \le j \le n)$

    对于每一个独立的 $c[i]$ 数组与互不影响的 $b$ ，你可以将 $b$ 、 $c[i]$ 数组中的数字随意排序，再随意删除 $c[i]$ 与 $b$ 中的 $k$ 个数，对于每一个 $c[i]$ 数组，求最小的 $k[i]$ 使得 $ \forall 1\le j \le n, c[i]_j < b_j$，输出所有 $c[i]$ 的删除数 $k[i]$ 的和。

Dances (Hard Version)

Created by LXC on Tue Mar 26 19:51:00 2024

https://codeforces.com/problemset/problem/1883/G2

ranting: 1900

tag: binary search, greedy, sortings, two pointers

problem

对于每组数据，给定 $n$ ， $m$ 与数组 $a$ 的第 $2$ 到 $n$ 项和数组 $b$ 的第 $1$ 到 $n$ 项。你需要根据 $a$ 数组求出 $m$ 个 $c$ 数组的值，具体地：

  • $c[i]_1 = i$

  • $c[i]_j = a_j (2 \le j \le n)$

对于每一个独立的 $c[i]$ 数组与互不影响的 $b$ ，你可以将 $b$ 、 $c[i]$ 数组中的数字随意排序，再随意删除 $c[i]$ 与 $b$ 中的 $k$ 个数，对于每一个 $c[i]$ 数组，求最小的 $k[i]$ 使得 $ \forall 1\le j \le n, c[i]_j < b_j$，输出所有 $c[i]$ 的删除数 $k[i]$ 的和。

solution

注意到可以对数组任意排序，那么我们a和b都升序排序。

b移除m个前缀中的值，a移除m个后缀中的值。如果能满足条件，那么删除m+1个值也能满足条件。所以，答案据有二段性。

对于一个确定的a和b只需要二分答案，$O(nlogn)$可以求出最少需要操作多少次。

而对a修改一个值，对答案的变化不超过1,也具有二段性，总复杂度$O(log(m)nlog(n))$

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n-1), b(n);
    for (auto& i:a) cin >> i;
    for (auto& i:b) cin >> i;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    auto check = [&](ll s) {
        auto sa = a;
        sa.push_back(s);
        for (int i=n-2; i>=0; i--) {
            if (sa[i] > sa[i+1]) swap(sa[i], sa[i+1]);
        }
        // cout << s << endl;
        // cout << sa << endl;
        // cout << b << endl;
        ll l=0, r=n;
        while (l<r) {
            ll m = l+r>>1;
            int ok = 1;
            for (int i=m; i<n;i++) {
                if (b[i] <= sa[i-m]) ok = 0;
            }
            if (ok) { 
                r = m;
            } else {
                l = m+1;
            }
        }
        return r;
    };
    ll v = check(1);
    ll l=1, r=m+1;
    while (l<r) {
        ll m = l+r>>1;
        if (check(m) != v) r = m;
        else l = m+1;
    }
    cout << v*(r-1) + (m-r+1)*check(r) << '\n';

}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}