莫队二次离线的板子寄掉了。

大佬帮帮 qwq

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#include <sstream>
#include <bitset>
#include <cassert>
#include <random>
//#define int long long
#define double long double
#define endl "\n"
#define pii pair<double,int>
#define p1(x) ((x).first)
#define p2(x) ((x).second)
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
#define len(x) T[x].len
#define sum(x) T[x].sum
#define pre(x) T[x].pre
#define suf(x) T[x].suf
#define mx(x) T[x].mx
#define i128 __int128_t
using namespace std;
const int N=1e5;
const int SIZ=250;
const int LEN=N/SIZ+10;
int n,a[N+10],b[N+10];
long long f[N+10],h[N+10];
long long ANS[N+10];
int q;
int bel[N+10],L[LEN+10],R[LEN+10];

int t[N+10];
int S[LEN+10];
int suf[N+10],SUF[LEN+10],pre[N+10],PRE[LEN+10];
inline void clr(){
    memset(t,0,sizeof(t));
    memset(S,0,sizeof(S));
    memset(SUF,0,sizeof(SUF));
    memset(suf,0,sizeof(suf));
    memset(PRE,0,sizeof(PRE));
    memset(pre,0,sizeof(pre));
}
inline void rb(int id){
    suf[R[id]]=t[R[id]];
    for(int i=R[id]-1;i>=L[id];i--)
        suf[i]=suf[i+1]+t[i];
    pre[L[id]]=t[L[id]];
    for(int i=L[id]+1;i<=R[id];i++)
    pre[i]=pre[i-1]+t[i];
    
    S[id]=suf[L[id]];
    
    for(int i=LEN;i>=1;i--)
        SUF[i]=SUF[i+1]+S[i];
    for(int i=1;i<=LEN;i++)
        PRE[i]=PRE[i-1]+S[i];
}
inline void add(int x){
    t[x]++;
    rb(bel[x]);
}
inline int gsuf(int x){return SUF[bel[x]+1]+suf[x];}
inline int gpre(int x){return PRE[bel[x]-1]+pre[x];}
struct ASK{
    int l,r,id,s;
}A[N+10];
vector<ASK>TSUF[N+10],TPRE[N+10];
inline bool cmp(ASK A,ASK B){
    return bel[A.l]==bel[B.l]?bel[A.l]&1?A.r<B.r:A.r>B.r:A.l<B.l;
}
signed main(){
    ios::sync_with_stdio(0);
//    freopen("/Users/noip2019/Downloads/P5047_1.in","r",stdin);
//    freopen("b.out","w",stdout);
    memset(L,0x3f,sizeof(L));
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    for(int i=1;i<=N;i++)
        bel[i]=(i+SIZ-1)/SIZ,
        L[bel[i]]=min(L[bel[i]],i),
        R[bel[i]]=max(R[bel[i]],i);
    sort(b+1,b+n+1);
    auto tmp=unique(b+1,b+n+1);
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,tmp,a[i])-b;
    for(int i=1;i<=n;i++)
        add(a[i]),f[i]=f[i-1]+gsuf(a[i]+1),h[i]=h[i-1]+gpre(a[i]-1);
    clr();
//    cout<<f[114]-f[113]<<" "<<h[114]-h[113]<<endl;
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        A[i]={l,r,i,0};
    }
    sort(A+1,A+q+1,cmp);
    int l=1,r=0;
    
    for(int i=1;i<=q;i++){
        if(r<A[i].r){
            ANS[A[i].id]+=f[A[i].r]-f[r];
            TSUF[l-1].push_back({r+1,A[i].r,A[i].id,-1});
            r=A[i].r;
        }
        if(l>A[i].l){
            TPRE[r].push_back({A[i].l,l-1,A[i].id,1});
            ANS[A[i].id]-=h[l-1]-h[A[i].l-1];
            l=A[i].l;
        }
        if(r>A[i].r){
            ANS[A[i].id]-=f[r]-f[A[i].r];
            TSUF[l-1].push_back({A[i].r+1,A[i].r,A[i].id,1});
            r=A[i].r;
        }
        if(l<A[i].l){
            TPRE[r].push_back({l,A[i].l-1,A[i].id,-1});
            ANS[A[i].id]+=h[A[i].l-1]-h[l-1];
            l=A[i].l;
        }
//        cout<<l<<" "<<r<<" "<<A[i].l<<" "<<A[i].r<<endl;
    }
    for(int i=0;i<=n;i++){
        if(i)add(a[i]);
        for(ASK A:TSUF[i]){
//            cout<<i<<" "<<A.l<<" "<<A.r<<endl;
            for(int j=A.l;j<=A.r;j++)
                ANS[A.id]+=A.s*gsuf(a[j]+1);}
        
        for(ASK A:TPRE[i]){
//            cout<<i<<" "<<A.l<<" "<<A.r<<endl;
            for(int j=A.l;j<=A.r;j++)
                ANS[A.id]+=A.s*gpre(a[j]-1);}
    }
    for(int i=1;i<=q;i++)
        ANS[A[i].id]+=ANS[A[i-1].id];
    for(int i=1;i<=q;i++)
        cout<<ANS[i]<<endl;
    cout.flush();
    return 0;
}
/*
*/