# 朝田诗乃 的博客

### 题解 P2234 【[HNOI2002]营业额统计】

posted on 2018-12-06 17:39:41 | under 题解 |

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXV = 2e6 + 50;
const int MAXN = 40050;
const int PIAO = 1e6;
typedef long long lint;
int t[MAXV], n, a[MAXN], maxval, minval = 2147483647; lint ans;
bool vis[MAXV];
char ch; int f = 1;
while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
x = ch - 48; while(ch = getchar(), ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - 48; x *= f;
}
void update(int x, int val) {for(; x <= maxval; t[x] += val, x += x & (-x));}
int query(int x) {
int res = 0;
for(; x >= minval; res += t[x], x -= x&(-x));
return res;
}
int bs(int l, int r, int val) {
while(l < r) {
int mid = (l + r) >> 1, V;
V = query(mid);
if(V == val) r = mid;
else if(val > V) l = mid + 1;
else r = mid-1;
}
return r;
}
int main() {
for(int i = 1; i <= n; ++i)
read(a[i]), a[i] += PIAO, maxval = max(a[i], maxval), minval = min(a[i], minval);
int imax = a[1], imin = a[1]; update(a[1], 1); vis[a[1]] = 1;
for(int i = 2; i <= n; ++i) {
if(vis[a[i]]) continue; //重复数特判
imax = max(imax, a[i]); imin = min(imin, a[i]); //处理当前边界
int tmp = 2147483647;
if(a[i] != imin) tmp = min(tmp, a[i]-bs(imin, a[i], query(a[i])));
if(a[i] != imax) tmp = min(tmp, bs(a[i], imax, query(a[i])+1)-a[i]);
if(tmp == 2147483647) tmp = 0;
ans += tmp;
update(a[i], 1); vis[a[i]] = 1;
}
printf("%lld\n", ans + a[1] - PIAO)； //a[1]特判
}