Rt

submission

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>

#define N 100005
#define LL long long

using namespace std;
int n,m,k,a[N],b[N];

struct Que { int l,r,id; LL ans; }que[N];

int B,pre1[N],pre2[N];

struct BIT1 {
    LL c[N];

    int lowbit(int x) { return x&-x; }
    void upd(int x,int k) { for (int i=x;i;i-=lowbit(i)) c[i]+=k; }
    LL ask(int x) { LL res=0; for (int i=x;i<=k;i+=lowbit(i)) res+=c[i]; return res; }
}t1;

struct BIT2 {
    int c[N];

    int lowbit(int x) { return x&-x; }
    void upd(int x,int k) { for (int i=x;i<=::k;i+=lowbit(i)) c[i]+=k; }
    int ask(int x) { int res=0; for (int i=x;i;i-=lowbit(i)) res+=c[i]; return res; }
}t2;

struct Tmp {
    int x,l,r,id,op,op1;

    Tmp(int _x=0,int _l=0,int _r=0,int _id=0,int _op=0,int _op1=0) {
        x=_x,l=_l,r=_r,id=_id,op=_op,op1=_op1;
    }
}arr[N<<2];
int cnt;

int block,L[N],R[N],bel[N]; LL tag[2][N],val[2][N];

void upd(int l,int r,int k,int op) {
    if (l>r) return;
    if (bel[l]==bel[r]) {
        for (int i=l;i<=r;i++)
            val[op][i]+=k;
    } else {
        for (int i=l;i<=R[bel[l]];i++)
            val[op][i]+=k;
        for (int i=L[bel[r]];i<=r;i++)
            val[op][i]+=k;
        for (int i=bel[l]+1;i<bel[r];i++)
            tag[op][i]+=k;
    }
}

int main() {
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) {
        scanf("%d",a+i);
        k=max(k,a[i]);
    }
    for (int i=1;i<=n;i++) {
        pre1[i]=t1.ask(a[i]+1);
        t1.upd(a[i],a[i]);
        pre2[i]=t2.ask(a[i]-1);
        t2.upd(a[i],1);
    }
    for (int i=1;i<=m;i++) {
        scanf("%d%d",&que[i].l,&que[i].r);
        que[i].id=i;
    }
    B=m/sqrt(n)+1;
    sort(que+1,que+m+1,[](Que tmp1,Que tmp2) {
        return (tmp1.l/B)^(tmp2.l/B)
                ?tmp1.l<tmp2.l
                :((tmp1.l/B)&1)?tmp1.r<tmp2.r:tmp1.r>tmp2.r;
    });
    for (int i=1,L=1,R=0;i<=m;i++) {
        if (L>que[i].l) arr[++cnt]=Tmp{R,que[i].l,L-1,i,1,1};
        while (L>que[i].l) --L,que[i].ans-=pre1[L]+1ll*pre2[L]*a[L];

        if (R<que[i].r) arr[++cnt]=Tmp{L-1,R+1,que[i].r,i,-1,0};
        while (R<que[i].r) ++R,que[i].ans+=pre1[R]+1ll*(pre2[R]+1)*a[R];

        if (L<que[i].l) arr[++cnt]=Tmp{R,L,que[i].l-1,i,-1,1};
        while (L<que[i].l) que[i].ans+=pre1[L]+1ll*pre2[L]*a[L],++L;

        if (R>que[i].r) arr[++cnt]=Tmp{L-1,que[i].r+1,R,i,1,0};
        while (R>que[i].r) que[i].ans-=pre1[R]+1ll*(pre2[R]+1)*a[R],--R;
    }
    block=sqrt(k);
    for (int i=1;i<=k/block;i++) {
        L[i]=R[i-1]+1,R[i]=L[i]+block-1;
        for (int j=L[i];j<=R[i];j++) bel[j]=i;
    }
    if (R[k/block]!=k) {
        int i=k/block;
        for (int j=R[i]+1;j<=k;j++) bel[j]=i;
        R[i]=k;
    }
    sort(arr+1,arr+cnt+1,[](Tmp tmp1,Tmp tmp2) {
        return tmp1.x<tmp2.x;
    });
    for (int i=1,j=1;i<=n;i++) {
        upd(1,a[i]-1,a[i],0); upd(a[i]+1,k,1,1);
        while (j<=cnt and arr[j].x<i) ++j;
        while (j<=cnt and arr[j].x==i) {
            for (int l=arr[j].l;l<=arr[j].r;l++)
                que[arr[j].id].ans+=arr[j].op*(val[0][a[l]]+tag[0][bel[a[l]]])
                                    +arr[j].op*(val[1][a[l]]+tag[1][bel[a[l]]]+arr[j].op1)*a[l];
            ++j;
        }
    }
    for (int i=1;i<=m;i++) que[i].ans+=que[i-1].ans;
    sort(que+1,que+m+1,[](Que tmp1,Que tmp2) { return tmp1.id<tmp2.id; });
    for (int i=1;i<=m;i++) printf("%lld\n",que[i].ans);
    return 0;
}