Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

arc147 Min Diff Sum

Posted on

比较暴力，思路不难，非常卡常。

不理解王巨这题为啥想了一晚上（QWQ）

Solution

首先猜想最优情况肯定是让所有数全部趋近于一个数，于是考虑三分，因为各种原因，这种方法$T$飞了（没错，小编也无法理解为啥出题人闲的要卡三分，平时不都放的吗），经过不断的尝试以及和出题人斗志斗勇的痛苦挣扎中，我们得出一个重要结论：最后趋近的那个数，一定是某个数的上界，或者下界，证明可以考虑微调：设目前三分到了一个值$x$，离它最近的两个临界值分别为$l$和$r$，这里考虑微调到$r$的情况（$l$同理），对于所有$L_i$比$x$要大数，就算将$x$微调到$r$，它们的值依旧不会改变，那么$R_i$比$x$小的数依旧同理，由于$x$不为临界值，剩下的数一定都能调整到$r$，那么当$\ge r$的数中被计算的次数大于$\le l$的数被计算的次数时，答案就会变优，否则微调到$l$的答案就会更优。

但是这样依旧不足以让你过掉这道题，我们继续乱搞，猜想：因为谷底的平衡态会使$x$左右两边的数的个数接近，于是我们将所有边界的值离散化了之后，最优情况一定离它们的中位数不远，于是我们只在离中位数距离不超过$300$的地方三分，就可以了。

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#pragma GCC optimize("O2,O3,Ofast")
#include <bits/stdc++.h>
#define LL long long
#define PII pair<LL, int>
using namespace std;
template <class T>
inline void read(T &res)
{
	res = 0; bool flag = 0;
	char c = getchar();
	while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
	while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
	if(flag) res = -res; 
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
	if(res < 0) putchar('-'), res = -res;
	if(res > 9) write(res / 10);
	putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); } 
const int N = 3e5 + 5;
int n;
int L[N], R[N];
int a[N], b[N];
vector<int>s;
PII tr[N];
inline PII add(PII x, PII y)
{
    return {x.first + y.first, x.second + y.second};
}
inline void modify(int x, int val, int v)
{
    PII o = {val, v};
    for(int i = x;i <= s.size();i += (i & -i)) tr[i] = add(tr[i], o);
}
inline PII query(int x)
{
    PII res = {0, 0};
    for(int i = x; i;i -= (i & (-i))) res = add(res, tr[i]);
    return res;
}
inline PII del(PII x, PII y)
{
    return {x.first - y.first, x.second - y.second};
}
LL ans = 1e18;
inline LL calc(int x)
{
    LL res = 0;
    s.clear();
    for(int i = 1;i <= n;i ++)
    {
        if(R[i] < x) a[i] = R[i];
        else if(L[i] > x) a[i] = L[i];
        else a[i] = x;
        s.emplace_back(a[i]);
    }
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    for(int i = 1;i <= n;i ++) b[i] = lower_bound(s.begin(), s.end(), a[i]) - s.begin() + 1;
    for(int i = 0;i <= s.size();i ++) tr[i] = {0, 0};
    PII lv, rv;
    for(int i = n, l, r;i >= 1;i --)
    {
        lv = query(b[i]), rv = query(s.size());
        rv = del(rv, lv);
        res += 1ll * s[b[i] - 1] * (lv.second - rv.second) - lv.first + rv.first;
        modify(b[i], s[b[i] - 1], 1);
    }
    ans = min(ans, res);
    return res;
}
vector<int>klm;
int main()
{
    read(n);
    for(int i = 1;i <= n;i ++) read(L[i], R[i]), klm.emplace_back(L[i]), klm.emplace_back(R[i]);
    sort(klm.begin(), klm.end());
    klm.erase(unique(klm.begin(), klm.end()), klm.end());
    int l = max(1, (int)klm.size() / 2 - 300), r = min((int)klm.size(), (int)klm.size() / 2 + 300);
    while(l <= r)
    {
        int rmid = (l + r) >> 1, lmid = (rmid + l) >> 1;
        if(calc(klm[lmid]) <= calc(klm[rmid])) r = rmid - 1;
        else l = lmid + 1;
    }
    write(ans);
    return 0;
}