朝田诗乃 的博客

朝田诗乃 的博客

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

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

给Splay巨佬们跪烂烂。

其实这题可以树状数组+二分搞。

更好的阅读体验点这里呗

如果我们有一个 $0/1$ 数组记录每个数有没有出现过,那么每次只需要查找离 $a$ [ $i$ ]最近的两个 $1$ 即可。

我们用树状数组维护这个数组的前缀和。设这个数组为t[],则查询时只需要找到t[a[i]]第一次出现的位置和t[a[i]+1]第一次出现的位置即可。由于前缀和数组具有单调性,所以可以用二分搞。复杂度 $O(nlog^2a[i])$ 。

由于有负数,所以需要偏移。(就是把每个数加上一个值)

代码:

#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];
void read(int &x) {
    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() {
    read(n);
    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]特判
}