性感回滚莫队在线求卡常

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+7;
int bl[N],jl[N],a[N],n,m,blk,bln,L[N],R[N],nw,l,r,len,nid[N];
long long res,Ans[N];
struct Que{int x,y,id;}q[N];
pair<int,int> v[N],s[N]; 

int Abs(int x){return x>=0?x:-x;}
inline bool cmp(Que x,Que y){if(bl[x.x]==bl[y.x]) return x.y>y.y; else return x.x<y.x;}
inline int in()
{
	int x=0; char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch<='9'&&ch>='0')
		x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x;
}

inline long long gtans(int x,int y,bool fl)
{
	if(fl)
		for(register int i=1;i<=len;i++) jl[v[i].first]=0;
	len=0;
	for(register int i=1;i<=n;i++)
		if(nid[i]>=x&&nid[i]<=y) v[++len]=make_pair(i,nid[i]);
	if(fl)
		for(register int i=1;i<=len;i++) s[i]=make_pair(i-1,i+1),jl[v[i].first]=i;
	long long ans=0;
	for(register int i=1;i<len;i++) ans+=Abs(v[i+1].second-v[i].second);
//	for(int i=0;i<v.size();i++) cout<<v[i].second<<" ";
//	cout<<endl;
	return ans;
}

inline void did(int x)
{
	int dlt=0;
	x=jl[a[x]];
	s[s[x].first].second=s[x].second;
	s[s[x].second].first=s[x].first;
	if(s[x].first!=0) dlt=dlt-Abs(v[x].second-v[s[x].first].second);
	if(s[x].second!=len+1) dlt=dlt-Abs(v[x].second-v[s[x].second].second);
	if(s[x].first!=0&&s[x].second!=len+1)
		dlt=dlt+Abs(v[s[x].first].second-v[s[x].second].second);
	res+=1ll*dlt;
	return;
}

inline void undid(int x)
{
	x=jl[a[x]];
	s[s[x].first].second=x;
	s[s[x].second].first=x;
	return;
}

int main()
{
	n=in(); m=in();
	blk=900; bln=(n/blk+(n%blk==0?0:1));
	for(register int i=1;i<=bln;i++) L[i]=R[i-1]+1,R[i]=i*blk;
	R[bln]=n;
	for(register int i=1;i<=n;i++) a[i]=in(),nid[a[i]]=i,bl[i]=(i-1)/blk+1;
	for(register int i=1;i<=m;i++)
		q[i].x=in(),q[i].y=in(),q[i].id=i;
	sort(q+1,q+1+m,cmp); nw=1;
	for(register int i=1;i<=bln;i++)
	{
		if(bl[q[nw].x]!=i) continue;
		res=gtans(L[i],max(R[i],q[nw].y),1);
		l=L[i]; r=q[nw].y;
		while(nw<=m&&bl[q[nw].x]==i)
		{
			if(bl[q[nw].x]==bl[q[nw].y])
			{
				Ans[q[nw].id]=gtans(q[nw].x,q[nw].y,0);
				nw++; continue;
			}
			while(r>q[nw].y) did(r--);
			long long tmp=res;
			while(l<q[nw].x) did(l++);
			Ans[q[nw].id]=res;
			while(l>L[i]) undid(--l);
			res=tmp; nw++;
		}
	}
	for(register int i=1;i<=m;i++) printf("%lld\n",Ans[i]);
	return 0;
}