洛谷 U264950 3D打印一道折磨我很久的题目

刷 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。

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

CPP 代码 · 共 65 行
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;
}

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

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

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

如果输入数据是一高一低： 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到这个时候我们似乎已经看破这道题目了。

按照这个思路写出代码：

CPP 代码 · 共 92 行
#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;
}

（啪的一下，很快啊。）

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

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

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

看来主席树是过不了了。

想法三：
#

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

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

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

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

CPP 代码 · 共 83 行
#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;
}

（啪的一下，很快啊！）

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

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

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

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

想法一#

想法二：#

想法三：#

想法一
#

想法二：
#

想法三：
#