题解 T50424 【lqyz10.11选拔赛 T3 婆罗门的城市斗鸡】

题目描述

在一个城市的一条窄到只有长度没有宽度的道路上有 N只婆罗门的斗鸡在不同斗鸡点的上， 对一个城市定义该城市的斗鸡爱好度为：

这n × (n − 1)个距离的总和。

每只婆罗门的斗鸡都计算到其它各只婆罗门的斗鸡的距离。 但是婆罗门数学太差，所以他要让你帮他求城市斗鸡爱好度。

输入输出格式

输入格式：

第一行一个整数 N。

接下来一行每行一个整数 Ji，代表第 i只婆罗门的斗鸡的位置。

输出格式：

输出一个数代表该城市的斗鸡爱好度。

输入输出样例

输入样例#1： 复制

5
1 2 3 4 5

输出样例#1： 复制

40

说明

对于 60%的数据：

N ≤ 1e4.

对于 100%的数据：

N ≤ 1e5, Ji ≤ 1e6 .

主要思路： 暴力 + 线段树优化

我绝对不会告诉你我考试时我电脑炸了

然而，我用快读就会被卡到80分，用scanf有100分。

emmm...

这是个令人深思的问题啊。

好的回到正题。

怎么用线段树？

我们如果求一个点到其他所有点的距离好像不太好做的说，起码O(n^2)，

但我们把这些数放在数轴上，可以一次性求出一个点到之前的所有点的距离吗？

当然可以！！！

我们可以想，一个点到另一个点的距离不是这个点的坐标减去另一个点的坐标吗？在这个点a[i]之前有i - 1个坐标，实际上是一个数列求和的问题。

a[i] - a[1] 
a[i] - a[2]
a[i] - a[3]
...
a[i] - a[i - 1]

  ||
  ||
 \--/
  \/
  
a[i] * (i - 1) - (a[1] + a[2] + a[3] + ... + a[i - 1])

我们可以这么求。

如果不考虑爆long long的话，我们可以用一个区间求和的线段树求a[1] ~ a[i - 1]，在用a[i] * (i - 1)减去这个数。

但是会爆int，还会爆long long。怎么办？

我们继续考虑线段树上的操作。

如果我们每次存进去一个点的负值，并求前面点的负值和，我们如果直接在线段树上把a[i]加进去，正好是每个点一个a[i] - a[j]（思路似乎又转回来了）

这样每次把一段区间区间加a[i]，求和加入答案，然后再区间减去a[i]。

这样求出的是一个点到之前点的距离和，只要答案*2就可以变成所有的距离和了

这样相当于只用了一个数据结构，不动脑子，就可以暴力解水题了

记得，目前此题的这组数据有毒，n^2可以过，但是你加了像我这样写的快读，你就可能凉凉

Code：

-------------------------------(线段树板子泥萌确定要看？？？)------------------------------

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 1000100
#define inf 2147483647
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
//#define LOCAL
#define mod 
#define Debug(...) fprintf(stderr, __VA_ARGS__)
inline int read(){  // 凉凉之快读
    int f = 1, x = 0;char ch = getchar();
    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
//This is AC head above...
struct tree{
    ll x;
};
struct SegmentTree{    // 线段树不解释，，，就是板子
    tree z[mn << 2];
    ll col[mn << 2];
    inline void update(int rt){ z[rt].x = z[rt << 1].x + z[rt << 1 | 1].x;} 
    inline tree operation(tree a,tree b){ return (tree){a.x + b.x}; }
    inline void color(int l,int r,int rt,ll v){
        z[rt].x += (r - l + 1) * v;
        col[rt] += v;
    }
    inline void push_col(int l,int r,int rt){
        if(col[rt]){
            int m = (l + r) >> 1;
            color(lson, col[rt]);color(rson, col[rt]);
            col[rt] = 0;
        }
    }
    inline void build(int l,int r,int rt){
        if(l==r){z[rt].x = 0;return;}
        int m = (l + r) >> 1;build(lson);build(rson); update(rt);
    }
    inline void modify(int l,int r,int rt,int nowl,int nowr,ll v){
        if(nowl<=l && r<=nowr){color(bson, v); return;}
        int m = (l + r) >> 1; push_col(bson);
        if(nowl<=m) modify(lson, nowl, nowr, v);
        if(m<nowr)  modify(rson, nowl, nowr, v);
        update(rt);
    }
    inline tree query(int l,int r,int rt,int nowl,int nowr){
        if(nowl<=l && r<=nowr) return z[rt];
        int m = (l + r) >> 1; push_col(bson);
        if(nowl<=m){
            if(m<nowr) return operation(query(lson, nowl, nowr), query(rson, nowl, nowr));
            else       return query(lson, nowl, nowr);
        }else          return query(rson, nowl, nowr);
    }
} tr;
ll n;
ll a[mn], b[mn], ans;
int main(){
    n = read();
    go(i, 1, n, 1) scanf("%d",&a[i]), b[i] = a[i];
    tr.build(root);
    sort(b + 1, b + n + 1); // 在数轴上记得排下序
    tr.modify(root, 1, 1, -b[1]);
    go(i,2,n,1){
        tr.modify(root, 1, i - 1, b[i]);
        ans += tr.query(root, 1, i - 1).x;
        tr.modify(root, 1, i - 1, -b[i]);
        tr.modify(root, i, i, -b[i]);
    }
    cout << (ans << 1); // 记得要×2
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}