刷LeetCode的时候看到了一个求助题，发现洛谷上有这个题目，想着不难开始尝试....然后就有了这篇文章。

链接：U264950 3D打印 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

伏笔：这道题目卡常很恐怖.

想法一：

很显然啊，当第i个柱子涂满之后，

他耗费的材料 = 第i个柱子的高度 + [1,i-1]∪[i+1,n] 中所有小于它的柱子高度和 +

（第i个柱子高度-1）* [i+1,n] 中高度大于等于它的柱子个数和 +

第i个柱子高度* [1,i]中高度大于等于它的柱子个数和

这个公式画个图很快就能理解了。那么问题来了，怎么快速求后三项和呢？

第一时间想到了线段树，在每一个节点中保存 minn maxn 以及 sum ，那么如果高度介于minn和maxn，我们就继续向这个区间查询，如果高度大于等于maxn，那么可以返回 (r-l+1)*本身高度，

如果高度小于等于minn，那么可以返回它的sum。

根据这个思路写出来代码：

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
struct node{
     int maxn,minn,sum;
     node*l,*r;
 }*t;

const int N=1e6+10;

int a[N];
int n;

inline void pushup(node*&root)
{
    root->minn=min(root->l->minn,root->r->minn);
    root->maxn=max(root->l->maxn,root->r->maxn);
    root->sum=root->l->sum+root->r->sum;
    return;
}

inline void build(node*&root,int l,int r)
{
    root=new node;
    root->l=NULL,root->r=NULL;

    if(l==r)
    {
        root->maxn=root->minn=root->sum=a[l];
        return;
    }

    int mid=l+r>>1;

    build(root->l,l,mid);
    build(root->r,mid+1,r);

    pushup(root);
}

inline int query1(node*&root,int l,int r,int L,int R,int key)
{
    if(l>=L&&r<=R&&root->minn>=key)
    {
        return key*(r-l+1);
    }

    if(l>=L&&r<=R&&root->maxn<=key)
    {
        return root->sum;
    }

    int mid=l+r>>1;
    int ans=0;

    if(mid>=L)ans+=query1(root->l,l,mid,L,R,key);
    if(mid<R)ans+=query1(root->r,mid+1,r,L,R,key);

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n;

    for(int i=1;i<=n;++i)
        cin>>a[i];

    build(t,1,n);

    for(int i=1;i<=n;++i)
    {
        int ans=0;

        if(i>1)
            ans+=query1(t,1,n,1,i-1,a[i]);

        if(i<n)
            ans+=query1(t,1,n,i+1,n,a[i]-1);

        cout<<ans+a[i]<<'\n';
    }

    cout<<endl;
    system("pause");
    return 0;
}

点击并拖拽以移动

（之所以写成链式，是因为被卡过一次....）

img点击并拖拽以移动

啪的一下，很快的哈，就被卡死了。

那么分析一下为什么会被卡：

如果输入数据是一高一低： 1 6 2 3 2 6

这时候，因为查询的高度很容易介于maxn 和 minn 之间，所以区间查询形同虚设，它会一个一个节点的访问，logn 退化成 n 当然就会TLE了。

想法二：

在思考怎么区间查询之前，我们思考：能不能提前知道每个柱子被涂满的前后顺序呢？

显然是可以的，如果我们对数组进行排序得到的以高度进行的排序肯定是顺序，但如果高度相同呢？如：1 2 3 2 6 2 三个2的被涂满的顺序是不一样的，那肯定要考虑前后编号了，我们要求前面的在前面后面的在后面，即stable_sort 。

好的这个时候我们得到了被涂满的前后顺序了，显然前面的是会被先涂满的，用一个sum变量记录，便可以得到小于等于本身的前后顺序了，那后面的呢？

我们回顾公式：

他耗费的材料 = 第i个柱子的高度 + [1,i-1]∪[i+1,n] 中所有小于它的柱子高度和 +

（第i个柱子高度-1）* [i+1,n] 中高度大于等于它的柱子个数和 +

第i个柱子高度* [1,i]中高度大于等于它的柱子个数和

也就是说我们这个时候可以解决前两项快速计算问题，后面两项呢？

可以看到，后面两项都是大于等于本身的，这个问题我们在前面的sort已经解决了，sort之后在编号后面的显然就是大于等于本身高度的柱子。但这时我们需要区分 原编号在前面的和在后面的，这个时候才能适当的使用公式。

即：排序之后我们需要针对原编号查询大于等于的情况。从 [i+1,n] 查询原编号大于等于本身原编号的个数！

这个问题怎么办呢？区间查询大于等于某个数的个数？ 主席树！

OK，ok到这个时候我们似乎已经看破这道题目了。

按照这个思路写出代码：

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 #include <iostream>
 #include <cmath>
 #include <string>
 #include <cstring>
 #include <vector>
 #include <algorithm>
 #define us unsigned short
 #define ll long long

using namespace std;

const int maxn = 1e6 + 10;

struct node
{
    int id;
    ll x;

    bool operator<(const node &it) const
    {
        return x < it.x;
    }
};

struct Tree
{
    int l, r;
    int cnt;
};

vector<Tree> t;

int n, cnt = 0;
vector<ll> res;
vector<int> root;
vector<node> a;

inline void modify(int &x, int l, int r, int &id)
{
    t[++cnt] = t[x];
    x = cnt;
    t[x].cnt++;

    if (l == r)
        return;

    int mid = l + r >> 1;

    if (mid >= id)
        modify(t[x].l, l, mid, id);
    else
        modify(t[x].r, mid + 1, r, id);
}

inline int query(int L, int R, int l, int r, int id, int cnt) // 求后面的大于等于id的个数
{
    if (l == r)
        return cnt;

    int mid = l + r >> 1;

    if (mid >= id)
        return query(t[L].l, t[R].l, l, mid, id, cnt);

    else
        // 向右子树走，减去左子树的部分
        return query(t[L].r, t[R].r, mid + 1, r, id, cnt - (t[t[R].l].cnt - t[t[L].l].cnt));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    a.resize(n + 1);
    t.resize(n * 16);
    root.resize(n + 1);
    res.resize(n + 1);

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].x;
        a[i].id = i;
    }

    stable_sort(a.begin() + 1, a.end());

    for (int i = 1; i <= n; ++i)
    {
        root[i] = root[i - 1];

        modify(root[i], 1, n, a[i].id);
    }

    ll sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        sum += a[i].x;

        // t1是排序之后在i后面的，且id号大于a[i].id+1 的个数
        // t2则是小于的个数
        int t1 = query(root[i], root[n], 1, n, a[i].id + 1, n - i);
        int t2 = n - i - t1;

        // 答案等于前面所有的小于的+本身 + 本身-1 * 在后面的 + 本身* 在前面的
        res[a[i].id] = sum + (a[i].x - 1) * t1 + a[i].x * t2;
    }

    for (int i = 1; i <= n; ++i)
        cout << res[i] << '\n';

    cout << endl;
    system("pause");
    return 0;
}

点击并拖拽以移动

img点击并拖拽以移动

（啪的一下，很快啊。）

还记得我说的嘛？这题卡常很离谱。

一看内存，我*，128MB，大概是3千万个int，而主席树需要 n*16 的内存这还没办法省的，这下怎么办？

说实话，笔者反复尝试，想看看能不能在不MLE的情况下过这个题目，但事实上是不是MLE就是RE（提交记录估计有一两页都是我交，真的抱歉。）

看来主席树是过不了了。

想法三：

用主席树来找区间大于等于某个数的个数的想法肯定是没有错的，那去考虑这道题目有什么特别的地方，也就是和别的区间查询不同的地方？

发现，我们的区间查询只需要查询从 [i+1,n] 的大于等于某个数的个数，也就是这个区间是从后向前的一个后缀，但是主席树是任意[l,r]区间都可以查询的，这不就是大材小用吗？

转念一想，主席树不就是可持久化权值线段树吗？就是可持久化赋予了权值线段树随机查询的能力。那如果我们把可持久化去掉呢？仅仅只是一颗简单的权值线段树，在从前向后遍历的同时，删除本身那个数字，不就做到了一样的效果吗？也就是说我们用动态权值线段树代替了静态主席树。可以实现吗？

来试试，除了查询和建树的部分，其实和主席树没有太大区别。

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
99
100
101
102
103
104
105
106
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

#define ll long long

using namespace std;

// 因为查询的时候总是从前向后查询，不是随机区间查询，所以可以使用权值线段树，查询一个就删除一个就好了
const int maxn = 1e6 + 10;

struct node
{
    int id;
    ll x;

    bool operator<(const node &it) const
    {
        return x < it.x;
    }
};

int t[maxn << 2];
int n, cnt = 0;
vector<ll> res;
vector<node> a;

inline void modify(int x, int l, int r, int id, int k)
{
    if (l == r)
    {
        t[x] += k;
        return;
    }

    int mid = l + r >> 1;

    if (mid >= id)
        modify(x << 1, l, mid, id, k);
    else
        modify(x << 1 | 1, mid + 1, r, id, k);

    t[x] = t[x << 1] + t[x << 1 | 1];
}

inline int query(int x, int l, int r, int id, int cnt)
{
    if (l == r)
        return cnt;

    int mid = l + r >> 1;

    if (mid >= id)
        return query(x << 1, l, mid, id, cnt);
    else
        return query(x << 1 | 1, mid + 1, r, id, cnt - t[x << 1]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    a.resize(n + 1);
    res.resize(n + 1);

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].x;
        a[i].id = i;
    }

    stable_sort(a.begin() + 1, a.end());

    for (int i = 1; i <= n; ++i)
    {
        modify(1, 1, n, a[i].id, 1);
    }

    ll sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        sum += a[i].x;

        // 如果填a[i].id+1会找到最右边的，导致最后的n会出现1，然后t2会少1，然后得到结果少1
        int t1 = query(1, 1, n, a[i].id, t[1]) - 1;
        int t2 = n - i - t1;
        // cout<<t1<<' '<<t2<<endl;
        //  答案等于前面所有的小于的+本身 + 本身-1 * 在后面的 + 本身* 在前面的
        res[a[i].id] = sum + (a[i].x - 1) * t1 + a[i].x * t2;

        modify(1, 1, n, a[i].id, -1);
    }

    for (int i = 1; i <= n; ++i)
        cout << res[i] << '\n';

    cout << endl;
    system("pause");
    return 0;
}

点击并拖拽以移动

img点击并拖拽以移动

（啪的一下，很快啊！）

怎么回事？我们的树的大小明明已经控制在了 maxn*4 了啊？开开O2试试。

img点击并拖拽以移动

这下终于过了，卡常太恶心了。

用了动态权值线段树之后成功AC了这道题目，其实我在写这道很恶心很卡常的题目的时候也呼朋唤友，同学用的树状数组，思路也不一样，两个人也没法交流，我们两个最后也都是只好独立搞出来。

本来都不打算继续学算法了，想学项目的，但是算法真的是网瘾啊，有时候一道题目真能干一天，尽管知道可能是在浪费时间，但是还是把持不住