洛谷 P3372 線段樹模闆

【分析】

splay搞yeah

【代碼】

//線段樹闆子(splay複習) 
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define M(a) memset(a,0,sizeof a)
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int mxn=;
ll n,m,sz,root,k;
int ch[mxn][],f[mxn],size[mxn];
ll key[mxn],sum[mxn],add[mxn],a[mxn];
inline ll read()
{
    ll x=,f=;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*+ch-'0',ch=getchar();
    return x*f;
}
inline int get(int x)
{
    if(ch[f[x]][]==x) return ;return ;
}
inline void update(int x)
{
    size[x]=size[ch[x][]]+size[ch[x][]]+;
    sum[x]=sum[ch[x][]]+sum[ch[x][]]+key[x];
}
inline void ADD(int x,ll ad)
{
    add[x]+=ad,key[x]+=ad;
    sum[x]+=ad*size[x];
}
inline void pushdown(int x)
{
    if(x && add[x])
    {
        if(ch[x][]) ADD(ch[x][],add[x]);
        if(ch[x][]) ADD(ch[x][],add[x]);
        add[x]=;
    }
}
inline void rotate(int x)
{
    pushdown(x);
    int fa=f[x],fafa=f[fa],which=get(x);
    ch[fa][which]=ch[x][which^],f[ch[fa][which]]=fa;
    ch[x][which^]=fa,f[fa]=x;
    f[x]=fafa;
    if(fafa) ch[fafa][ch[fafa][]==fa?:]=x;
    update(fa),update(x);
}
inline void splay(int x,int lastfa)
{
    for(int fa;(fa=f[x])!=lastfa;rotate(x))
      if(f[fa]!=lastfa) rotate(get(x)==get(fa)?fa:x);
    if(!lastfa) root=x;
}
inline int number(int x)
{
    int now=root;
    while()
    {
        pushdown(now);
        if(x<=size[ch[now][]] && ch[now][]) now=ch[now][];
        else 
        {
            if(x==size[ch[now][]]+) return now;
            x=x-size[ch[now][]]-;
            now=ch[now][];
        }
    }
}
inline int build(int fa,int l,int r)
{
    if(l>r) return ;
    int now=++sz,mid=l+r>>;
    f[now]=fa,key[now]=sum[now]=a[mid],size[now]=;
    ch[now][]=build(now,l,mid-);
    ch[now][]=build(now,mid+,r);
    update(now);
    return now;
}
int main()
{
    int i,j,x,y,opt;
    scanf("%lld%lld",&n,&m);
    fo(i,,n+) scanf("%lld",&a[i]);
    root=build(,,n+);
    fo(i,,m)
    {
        opt=read();
        if(opt==)
        {
            scanf("%d%d%lld",&x,&y,&k);x++,y++;
            x=number(x-),y=number(y+);
            splay(x,),splay(y,x);
            ADD(ch[y][],k);
        }
        if(opt==)
        {
            scanf("%d%d",&x,&y);x++,y++;
            x=number(x-),y=number(y+);
            splay(x,),splay(y,x);
            printf("%lld\n",sum[ch[y][]]);
        }
    }
    return ;
}