题目为 CF1290E

#include <bits/stdc++.h>
#define int long long
using namespace std;

constexpr int MAXN = 15e4 + 5,inf = 1e18;
int n,a[MAXN],p[MAXN];
random_device seed;
mt19937 rnd(seed());
namespace FHQTreap
{
    struct Firefly
    {
        int ls,rs,val,rank,max,smx,mxCnt,size,sum;
        int lazadd,lazmin;
    }tree[MAXN << 1];
    int rootL,rootR,cnt;
    #define lson(rt) tree[rt].ls
    #define rson(rt) tree[rt].rs
    inline void pushup(int rt)
    {
        tree[rt].max = max({tree[lson(rt)].max,tree[rson(rt)].max,tree[rt].val});
        tree[rt].sum = tree[lson(rt)].sum + tree[rson(rt)].sum + tree[rt].val;
        tree[rt].size = tree[lson(rt)].size + tree[rson(rt)].size + 1;
        tree[rt].smx = max(tree[lson(rt)].smx,tree[rson(rt)].smx);
        tree[rt].mxCnt = 0;
        if(tree[rt].max == tree[rt].val)
            tree[rt].mxCnt++;
        else
            tree[rt].smx = max(tree[rt].smx,tree[rt].val);
        if(tree[rt].max == tree[lson(rt)].max)
            tree[rt].mxCnt += tree[lson(rt)].mxCnt;
        else
            tree[rt].smx = max(tree[rt].smx,tree[lson(rt)].smx);
        if(tree[rt].max == tree[rson(rt)].max)
            tree[rt].mxCnt += tree[rson(rt)].mxCnt;
        else
            tree[rt].smx = max(tree[rt].smx,tree[rson(rt)].smx);
    }
    inline void updateAdd(int rt,int val)
    {
        tree[rt].sum += tree[rt].size * val;
        tree[rt].max += val;
        tree[rt].val += val;
        tree[rt].lazadd += val;
        if(tree[rt].smx != -inf)
            tree[rt].smx += val;
        if(tree[rt].lazmin != -inf)
            tree[rt].lazmin += val;
    }
    inline void updateMin(int rt,int val)
    {
        if(val >= tree[rt].max)
            return ;
        tree[rt].sum -= (tree[rt].max - val) * tree[rt].mxCnt;
        tree[rt].val = min(tree[rt].val,val);
        tree[rt].lazmin = tree[rt].max = val;
    }
    inline void pushdown(int rt)
    {
        if(tree[rt].lazadd)
        {
            if(lson(rt))
                updateAdd(lson(rt),tree[rt].lazadd);
            if(rson(rt))
                updateAdd(rson(rt),tree[rt].lazadd);
            tree[rt].lazadd = 0;
        }
        if(tree[rt].lazmin != -inf)
        {
            if(lson(rt))
                updateMin(lson(rt),tree[rt].lazmin);
            if(rson(rt))
                updateMin(rson(rt),tree[rt].lazmin);
            tree[rt].lazmin = -inf;
        }
    }
    inline void modifyMin(int rt,int val)
    {
        if(tree[rt].max <= val)
            return ;
        if(tree[rt].smx < val)
            return updateMin(rt,val);
        pushdown(rt);
        if(tree[rt].val > val)
            tree[rt].sum -= (tree[rt].val - val),tree[rt].val = val;
        if(lson(rt))
            modifyMin(lson(rt),val);
        if(rson(rt))
            modifyMin(rson(rt),val);
        pushup(rt);
    }
    inline int newNode(int val)
    {
        ++cnt;
        tree[cnt].lazadd = lson(cnt) = rson(cnt) = 0;
        tree[cnt].sum = tree[cnt].val = tree[cnt].max = val;
        tree[cnt].lazmin = tree[cnt].smx = -inf;
        tree[cnt].rank = rnd();
        tree[cnt].size = tree[cnt].mxCnt = 1;
        return cnt;
    }
    void splitRank(int rt,int rk,int &L,int &R)
    {
        if(!rt)
        {
            L = R = 0;
            return ;
        }
        pushdown(rt);
        if(tree[lson(rt)].size < rk)
        {
            L = rt;
            splitRank(rson(rt),rk - tree[lson(rt)].size - 1,rson(rt),R);
        }
        else
        {
            R = rt;
            splitRank(lson(rt),rk,L,lson(rt));
        }
        pushup(rt);
    }
    int merge(int L,int R)
    {
        if(!L || !R)
            return L | R;
        if(tree[L].rank > tree[R].rank)
        {
            pushdown(L);
            rson(L) = merge(rson(L),R);
            pushup(L);
            return L;
        }
        else
        {
            pushdown(R);
            lson(R) = merge(L,lson(R));
            pushup(R);
            return R;
        }
    }
}
using namespace FHQTreap;
namespace BIT
{
    int c[MAXN];
    #define lowbit(x) (x & -x)
    inline void modify(int p)
    {
        for(int i = p;i <= n;i += lowbit(i))
            ++c[i];
    }
    inline int query(int p)
    {
        int res = 0;
        for(int i = p;i;i -= lowbit(i))
            res += c[i];
        return res;
    }
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    tree[0].max = tree[0].smx = -inf;
    tree[0].size = 0;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        p[a[i]] = i;
    }
    using namespace BIT;
    for(int i = 1;i <= n;i++)
    {
        int x,y,pos = query(p[i]);
        modify(p[i]);
        splitRank(rootL,pos,x,y);
        if(y)
        {
            updateAdd(y,-1);
            modifyMin(y,-pos - 2);
        }
        rootL = merge(merge(x,newNode(-1)),y);
        splitRank(rootR,pos,x,y);
        if(x)
            modifyMin(x,pos);
        if(y)
            updateAdd(y,1);
        rootR = merge(merge(x,newNode(i)),y);
        cout << tree[rootR].sum + tree[rootL].sum + i << "\n";
    }
}

上面这份代码在同一份数据的情况下随机出错，求大佬解释/条