这几天一直在写各种分块，要写吐了。

今天不剩啥时间了，写道板子题吧。

[LnOI2019] 来者不拒，去者不追

首先看到这个复杂度区间询问且能离线，肯定想到莫队。

但第一感觉是不是以为这东西特别难维护？每次插入删除一个数，那排名不都变了吗？

但你仔细想想，就会发现很好维护。

假设现在插入一个 $x$，那么新增贡献就是 $((\sum_{i=l}^r [a_i<x])+1)\times x+\sum_{i=l}^r [a_i \ge x]\times a_i$ 。

这应该比较好想吧，不再赘述。

如果直接用树状数组维护是 $O(n\sqrt n\log n)$ 的，可以得 80pts。

非常好写，大概几分钟就能写完。

然后考虑正解。

你发现贡献可以拆成两部分，然后发现这两部分都能差分。

然后直接二次离线呗，然后值域分块平衡复杂度呗，然后就做完了。

具体怎么差分，然后二次离线怎么扫描线可以自己想想，很简单。

复杂度 $O(n\sqrt n)$

upd：我错了。

首先，贡献不能只拆成两部分，要拆成三部分：$(\sum_{i=l}^r [a_i<x])\times x,x,\sum_{i=l}^r [a_i \ge x]\times a_i$。

因为第二部分不能差分。

如果按上文那样只拆成两部分，你会发现你连样例都过不了。

我用了两个小时才发现这个东西。

然后，值域分块写挂了，调了半个小时。

我是废物。

#include"bits/stdc++.h"
#define re register
#define int long long
#define lb(x) (x&(-x))
using namespace std;
const int maxn=5e5+10,V=1e5,maxm=350;
int n,m,siz,tot;
int a[maxn],ans[maxn];
int pre1[maxn],pre2[maxn],pre3[maxn];
int st[maxm],ed[maxm],bel[V+10],idx[V+10];
int cnt[V+10],tag1[maxm];
int sum[V+10],tag2[maxm];
struct query{
    int l,r,id,ans;
}q[maxn];
struct node{
    int l,r,id,op;
};
vector<node> g[maxn];
struct BIT{
    int tr[V+10];
    inline void clear(){memset(tr,0,sizeof tr);}
    inline void add(int x,int val){while(x<=V) tr[x]+=val,x+=lb(x);}
    inline int query(int x){int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
}s1,s2;
inline bool cmp(query a,query b){return ((a.l/siz)^(b.l/siz))?(a.l/siz)<(b.l/siz):((a.l/siz)&1)?a.r<b.r:a.r>b.r;}
inline void init(){
    siz=320;
    tot=V/siz;
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<V) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=V;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i,idx[j]=j-st[i]+1;
}
inline void add(int x){
    if(tag1[bel[x]]){
        for(re int i=st[bel[x]];i<=ed[bel[x]];++i) cnt[i]+=tag1[bel[x]];
        tag1[bel[x]]=0;
    }
    if(tag2[bel[x]]){
        for(re int i=st[bel[x]];i<=ed[bel[x]];++i) sum[i]+=tag2[bel[x]];
        tag2[bel[x]]=0;
    }
    for(re int i=x;i<=ed[bel[x]];++i) ++cnt[i],sum[i]+=x;
    for(re int i=bel[x]+1;i<=tot;++i) ++tag1[i],tag2[i]+=x;
}
inline int query1(int x){return tag1[bel[x]]+cnt[x];}
inline int query2(int x){return tag2[bel[x]]+sum[x];}
inline void solve(){
    for(re int i=1;i<=n;++i){
        add(a[i]);
        for(auto x:g[i]){
            for(re int j=x.l;j<=x.r;++j){
                q[x.id].ans+=x.op*(query1(a[j]-1)*a[j]+query2(V)-query2(a[j]));
            }
        }
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1;i<=n;++i){
        pre1[i]=pre1[i-1]+s1.query(a[i]-1)*a[i];
        pre2[i]=pre2[i-1]+s2.query(V)-s2.query(a[i]);
        pre3[i]=pre3[i-1]+a[i];
        s1.add(a[i],1),s2.add(a[i],a[i]);
    }
    for(re int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    siz=sqrt(n);
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(re int i=1;i<=m;++i){
        if(r<q[i].r){
            g[l-1].push_back({r+1,q[i].r,i,-1});
            q[i].ans+=(pre1[q[i].r]-pre1[r]+pre2[q[i].r]-pre2[r]);
            q[i].ans+=(pre3[q[i].r]-pre3[r]);
            r=q[i].r;
        }
        if(l>q[i].l){
            g[r].push_back({q[i].l,l-1,i,1});
            q[i].ans-=(pre1[l-1]-pre1[q[i].l-1]+pre2[l-1]-pre2[q[i].l-1]);
            q[i].ans+=(pre3[l-1]-pre3[q[i].l-1]);
            l=q[i].l;
        }
        if(r>q[i].r){
            g[l-1].push_back({q[i].r+1,r,i,1});
            q[i].ans-=(pre1[r]-pre1[q[i].r]+pre2[r]-pre2[q[i].r]);
            q[i].ans-=(pre3[r]-pre3[q[i].r]);
            r=q[i].r;
        }
        if(l<q[i].l){
            g[r].push_back({l,q[i].l-1,i,-1});
            q[i].ans+=(pre1[q[i].l-1]-pre1[l-1]+pre2[q[i].l-1]-pre2[l-1]);
            q[i].ans-=(pre3[q[i].l-1]-pre3[l-1]);
            l=q[i].l;
        }
    }
    init();
    solve();
    for(re int i=1;i<=m;++i) q[i].ans+=q[i-1].ans;
    for(re int i=1;i<=m;++i) ans[q[i].id]=q[i].ans;
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}