题解 | #Forsaken的数列#

平衡树板子题，随便整个平衡树都能做。 下面是代码，用的是FHQ treap，核心是维护一个节点下所有节点的总和与个数，还有懒标记，区间加就拆开来维护中间那颗树的头节点，插入就是拆开来然后加入一个树再合并，区间查询就不用我多说了吧。

#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
const int M=2e5+10;
ll cnt,x,y,z,root;
struct FHQ_Treap
{ll x,ls,rs,sz,lz,sum,key;}s[M];
inline ll NewNode(ll v)
{
    s[++cnt]=(FHQ_Treap){v,0,0,1,0,v,rand()};
    //cout << cnt << endl;
    return cnt;
}
inline void push_up(ll u)
{
    s[u].sum=s[s[u].ls].sum+s[s[u].rs].sum+s[u].x;
    s[u].sz=s[s[u].ls].sz+s[s[u].rs].sz+1;
}
inline void push_down(ll u)
{
    if(!s[u].lz)return;
    s[s[u].ls].lz+=s[u].lz;s[s[u].rs].lz+=s[u].lz;
    s[s[u].ls].x+=s[u].lz,s[s[u].rs].x+=s[u].lz;
    s[s[u].ls].sum+=s[u].lz*s[s[u].ls].sz;
    s[s[u].rs].sum+=s[u].lz*s[s[u].rs].sz;
    s[u].lz=0;
}
ll Merge(ll x,ll y)
{
    if(s[x].lz)push_down(x);
    if(s[y].lz)push_down(y);
    if(!x||!y)return x+y;
    if(s[x].key<s[y].key)return s[x].rs=Merge(s[x].rs,y),push_up(x),x;
    else return s[y].ls=Merge(x,s[y].ls),push_up(y),y;
}
void split(ll now,ll size,ll &x,ll &y)
{
    if(!now){x=y=0;return;}
    push_down(now);
    if(s[s[now].ls].sz>=size)y=now,split(s[now].ls,size,x,s[now].ls);
    else x=now,split(s[now].rs,size-s[s[now].ls].sz-1,s[now].rs,y);
    push_up(now);
}
inline void Insert(ll v,ll pos)
{
    split(root,pos-1,x,y);
    root=Merge(Merge(x,NewNode(v)),y);
    //cout << root << endl;
}
inline void add(ll l,ll r,ll v)
{
    split(root,r,x,z);split(x,l-1,x,y);
    s[y].x+=v;s[y].lz+=v;s[y].sum+=v*s[y].sz;
    root=Merge(Merge(x,y),z);
}
inline void query(ll l,ll r)
{
    split(root,r,x,z);split(x,l-1,x,y);
    printf("%lld\n",s[y].sum);
    root=Merge(Merge(x,y),z);
}
int main()
{
    ll n,m;
    srand(1919810);
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
    {
        ll v;
        scanf("%lld",&v);
        Insert(v,i);
    }
    scanf("%lld",&m);
    while(m--)
    {
        ll op,l,r,pos;
        scanf("%lld",&op);
        if(op==1)scanf("%lld",&pos),Insert(0,pos);
        if(op==2)scanf("%lld%lld%lld",&l,&r,&pos),add(l,r,pos);
        if(op==3)scanf("%lld%lld",&l,&r),query(l,r);
        //cout << m << endl;
    }
}