rt，样例过了，提交全 WA

这真的是最后一次写二次离线莫队了

不知道咋回事电脑更新完后怎么对拍拍不了乐

#include<bits/stdc++.h>
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
char buf[1<<20],*p1,*p2;
#define ll long long
using namespace std;
const int N=5e5+1,V=1e5+1,M=320;
int n,m,belong[N],a[N],f[N],id[V];
ll sum[V],Sum[M],s[N],ans[N];
int cnt[V],Cnt[M];

int read() {
	int x=0; char ch=0; while (!isdigit(ch) ) ch=gc();
	while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=gc();
	return x;
}
struct Query
{
	int l,r,id; ll ans;
	bool operator <(Query o)const {
		return belong[l]^belong[o.l]?l<o.l:r<o.r; 
	}
}Q[N];

struct qwq {
	int l,r,id,sign;
};
vector<qwq> q[N];

void update(int x)
{
    for (int i=1;i<id[x];i++) Sum[i]+=x;
    for (int i=x-1;id[i]==id[x];i--) sum[i]+=x;
	for (int i=x+1;id[i]==id[x];i++) cnt[i]++;
	for (int i=id[x]+1;i<=id[V];i++) Cnt[i]++;
}
ll calc(int x) {
	return sum[x]+Sum[id[x] ]+1ll*(cnt[x]+Cnt[id[x] ])*x;
}
int main()
{
	n=read(),m=read(); int sz=sqrt(n);
	for (int i=1;i<=V;i++) id[i]=(i-1)/M+1;
	for (int i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i],belong[i]=(i-1)/sz;
	for (int i=1;i<=n;i++) f[i]=f[i-1]+calc(a[i]),update(a[i]);
	for (int i=0;i<m;i++) Q[i]={read(),read(),i}; sort(Q,Q+m);
	
	for (int i=0,l=1,r=0;i<m;i++)
	{
		int L=Q[i].l,R=Q[i].r;
		Q[i].ans=f[L-1]-f[l-1]+f[R]-f[r];
		if (l>L) q[r].push_back({L,l-1,i,1}),l=L;
		if (l<L) q[r].push_back({l,L-1,i,-1}),l=L;
		if (r<R) q[l-1].push_back({r+1,R,i,-1}),r=R;
		if (r>R) q[l-1].push_back({R+1,r,i,1}),r=R;
	}
	memset(sum,0,sizeof sum);
	memset(Sum,0,sizeof Sum);
	memset(cnt,0,sizeof cnt);
	memset(Cnt,0,sizeof Cnt);
	
	for (int i=1;i<=n;i++)
	{
		update(a[i]);
		for (auto t:q[i])
			for (int j=t.l;j<=t.r;j++)
				Q[t.id].ans+=calc(a[j])*t.sign;
	}
	for (int i=1;i<m;i++) Q[i].ans+=Q[i-1].ans;
	for (int i=0;i<m;i++) ans[Q[i].id]=Q[i].ans+s[Q[i].r]-s[Q[i].l-1];
	for (int i=0;i<m;i++) printf("%lld\n",ans[i]);
	return 0;
}