\(\text{link}\)，这题太毒瘤啦！难写难调还略微卡常。
谁爱卡常谁卡吧。反正我先贺为敬了。——引用自洛谷别人的提交记录
本人写了两天（两个 \(case\) 各一天），调崩溃了才调出来，太毒瘤了！
看到颜色相同发现不弱于 \(O(n\sqrt n)\)，一眼根号分治，设阈值为 \(B\)。
case 1
对于颜色出现次数 \(\le B\) 的，发现同色对是 \(O(nB)\) 级别的。（因为一个颜色最多能对应 \(B\) 个同色）
令 \(\max[i,j]=\max\limits_{k=i}^j y_k,\min[i,j]=\min\limits_{k=i}^j y_k\)。
我们可以枚举这样的同色对 \((i,j)\)，发现 \(\forall i\le k\le j,l\le y_k\le r\Leftrightarrow \max[i,j]\le r,\min[i,j]\ge l\)。
我们把每个点对 \((i,j)\) 看成点对 \((\max[i,j],\min[i,j])\)，ST 表处理，则只需加点，矩形数点即可。套用 \(O(1)-O(\sqrt n)\) 单点加，区间和即可。复杂度 \(O(nB+m\sqrt n)\)。
但是此时空间复杂度为 \(O(nB)\)，不可接受。
考虑枚举这样颜色后，对于每个在颜色集中相邻位置 \((i,j)\)，设 \((i,j)\) 区间最大值为 \(mx\)，则暴力预处理出最远的 \(l\) 使得 \(\max[l,j]=mx\)，最远的 \(r\) 使得 \(\max[i,r]=mx\)。
于是所有最大值位置在 \([i,j]\) 的区间 \([L,R]\) 等价于 \(l\le L\le i,j\le R\le r\)。把 \((i,j,l,r)\) 加入到 vector 中，加点的时候暴力枚举加入即可。实际代码加入的与这有一点出入，本质相同。
但是当 \([i,j]\) 最大值在 \(i\) 或 \(j\) 时可能会算重，注意要减掉这部分贡献。这里自己手推一下就行，和上面类似的。
空间复杂度变为线性，时间复杂度不变。
case 2
当颜色出现次数 \(> B\) 时，发现最多只有 \(\dfrac{n}{B}\) 个颜色。
对于每个这样的颜色考虑，设当前有 \(n_i\) 个这样的颜色。
考虑相邻同色区间 \((l,r)\) 只有 \(\max[l+1,r-1],\min[l+1,r-1]\) 这两个值有用，保留这些颜色和其中间的这两个数，此时留下的数为 \(O(n_i)\) 级别。
于是把所有留下来的数和询问的 \(l,r\) 离散化一下，然后对于值域跑回滚莫队，维护在序列上的连续段，用链表维护即可。取块长为 \(O(\dfrac{n_i}{\sqrt m})\) 级别，则每次莫队复杂度为 \(O(n_i\sqrt m+m)\)，总复杂度 \(O(n\sqrt m+\dfrac{nm}{B})\)。
取 \(B=\sqrt m\)，总复杂度 \(O(n\sqrt m+m\sqrt n)\)，实际 \(B\) 要开三倍（根据自己情况调参），\(B\) 取定值避免不必要麻烦（回滚莫队块长千万别取成定值！），回滚莫队的块长要 \(+1\) 避免不必要麻烦。
小细节部分：
-
离散化的时候记 \(le_i\) 表示 \(\le i\) 的数的个数，每次 \(O(n)\) 前缀和求出来而后离散化，注意询问 \(l,r\) 的离散化方法不同。
-
维护连续段把连续段中的是这种颜色的个数记在左右端点中的一个上，记个 \(to\) 表示某个点所在的连续段中，当它是左右端点时，若它是左端点则记录右端点，否则记录左端点，具体修改细节自己思考。
-
要及时清空数组，循环清空避免超时，注意边界情况可能的问题。
具体细节看代码，注释比较清楚。
代码：
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
#define sq __builtin_sqrt
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
namespace IO
{
const int _Pu=2e7+5,_d=32;
char buf[_Pu],obuf[_Pu],*p1=buf+_Pu,*p2=buf+_Pu,*p3=obuf,*p4=obuf+_Pu-_d;
inline void fin()
{
memmove(buf,p1,p2-p1);
int rlen=fread(buf+(p2-p1),1,p1-buf,stdin);
if(p1-rlen>buf) buf[p2-p1+rlen]=EOF;p1=buf;
}
inline void fout(){fwrite(obuf,p3-obuf,1,stdout),p3=obuf;}
inline int rd()
{
if(p1+_d>p2) fin();int isne=0,x=0;
for(;!isdigit(*p1);++p1) isne=(*p1=='-');x=(*p1++-'0');
for(;isdigit(*p1);++p1) x=x*10+(*p1-'0');
if(isne) x=-x;return x;
}
inline void wr(LL x,char end='\n')
{
if(!x) return *p3++='0',*p3++=end,void();
if(x<0) *p3++='-',x=-x;
char sta[20],*top=sta;
do{*top++=(x%10)+'0';x/=10;}while(x);
do{*p3++=*--top;}while(top!=sta);(*p3++)=end;
}
}using IO::rd;using IO::wr;//快读，没啥好说
const int N=5e5+5;
struct node{int w,c,l,r;};
struct Que{int l,r,id;inline bool operator<(Que X){return r<X.r;}};
int n,m,B,B1,tot,a[N],b[N],le[N],l[N],r[N];LL ans[N];
vector<int>C[N],as[N];
vector<node>g[N],h[N];
vector<Que>q[N];
namespace ST
{
int t,mx[N][19],mn[N][19];
inline void init()
{
for(int i=1;i<=n;i++) mx[i][0]=mn[i][0]=b[i];
for(int j=1;(1<<j)<=n;j++) for(int i=1;i+(1<<j)-1<=n;i++)
mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]),
mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
inline int MX(int l,int r){return t=__lg(r-l+1),max(mx[l][t],mx[r-(1<<t)+1][t]);}
inline int MN(int l,int r){return t=__lg(r-l+1),min(mn[l][t],mn[r-(1<<t)+1][t]);}
}using ST::MX;using ST::MN;//ST表，没啥好说
namespace MAT
{
int B,a[N],b[755],bl[N];
inline void init(){B=sq(n);for(int i=1;i<=n;i++) bl[i]=(i-1)/B+1;}
inline void add(int p,int x){a[p]+=x;b[bl[p]]+=x;}
inline int ask(int l,int r)
{
int L=bl[l],R=bl[r],ans=0;
if(L==R){for(int i=l;i<=r;i++) ans+=a[i];return ans;}
for(int i=L+1;i<R;i++) ans+=b[i];
for(int i=l;i<=bl[l]*B;i++) ans+=a[i];
for(int i=bl[r]*B-B+1;i<=r;i++) ans+=a[i];return ans;
}
}//O(1)-O(sqrt)单点加、区间和，不会还想做这题？
int c[N],ls[N],bl[N],L[N],R[N],w[N],I[N],TO[N],WW[N];
namespace List
{
struct Node{int x,y,z;}sk[N];
int to[N],W[N],st;
inline void add(int x,int o,LL &sum)//o=0时右端点移动时加点，否则为左端点
{
int l=I[x],r=l,val=w[l];
if(to[l-1]) sum-=1ll*W[to[l-1]]*(W[to[l-1]]-1),val+=W[to[l-1]],l=to[l-1];//左边有点则合成连续段
if(to[r+1]) sum-=1ll*W[r+1]*(W[r+1]-1),val+=W[r+1],r=to[r+1];//右边有点则合成连续段
sum+=1ll*val*(val-1);(o)&&(sk[++st]={to[l],W[l],l},1);
to[l]=r,W[l]=val,(o)&&(sk[++st]={to[r],W[r],r},1),to[r]=l;//统计贡献，注意如果左端点移动时要往栈里仍续删的东西
//左右边合并不同的原因是 把连续段中 的是这种颜色的个数 记在了左端点上
}
inline void del(){while(st) to[sk[st].z]=sk[st].x,W[sk[st].z]=sk[st].y,st--;}//回滚莫队移动左端点的清空
inline void cl(){for(int i=1;i<=tot;i++) to[i]=W[i]=0;}//清空
}//链表维护
inline void MO()
{
for(int i=1,ll,rr;i<=bl[tot];i++)
{
sort(q[i].begin(),q[i].end());LL sum=0;ll=R[i],rr=ll+1;List::cl();
for(Que j:q[i])
{
if(bl[j.r]==i)
{
LL SUM=0;
for(int x=j.l;x<=j.r;x++)
{
int l=I[x],r=l,val=w[l];
if(TO[l-1]) SUM-=1ll*WW[TO[l-1]]*(WW[TO[l-1]]-1),val+=WW[TO[l-1]],l=TO[l-1];
if(TO[r+1]) SUM-=1ll*WW[r+1]*(WW[r+1]-1),val+=WW[r+1],r=TO[r+1];
SUM+=1ll*val*(val-1),TO[l]=r,TO[r]=l,WW[l]=val;
}ans[j.id]+=SUM/2;
for(int x=j.l;x<=j.r;x++) TO[I[x]]=WW[I[x]]=0;continue;
}//同一区间同上类似处理
for(;rr<=j.r;rr++) List::add(rr,0,sum);LL Sum=sum;
for(int k=ll;k>=j.l;k--) List::add(k,1,Sum);List::del();ans[j.id]+=Sum/2;
}q[i].clear();
}
}//回滚莫队，有了链表后剩下的就是板子部分了
int main()
{
n=rd(),m=rd();B=2130;
for(int i=1;i<=n;i++) a[i]=rd(),C[a[i]].push_back(i);
for(int i=1;i<=n;i++) b[i]=rd();ST::init();
for(int i=1;i<=m;i++) l[i]=rd(),r[i]=rd(),as[r[i]].push_back(i);
for(int i=1;i<=n;i++)
{
if(C[i].size()<=B)
{
if(C[i].size()<=1) continue;
for(int j=0;j<C[i].size()-1;j++)
{
int o=MX(C[i][j],C[i][j+1]),L=j,R=j+1;
for(int k=j-1;k>=0;k--)
{
if(MX(C[i][k],C[i][j+1])==o) L=k;
else break;
}
for(int k=j+2;k<C[i].size();k++)
{
if(MX(C[i][j],C[i][k])==o) R=k;
else break;
}g[o].push_back({j,i,L,R});
}//+1贡献，思路说的很清楚了
for(int j=1;j<C[i].size()-1;j++)
{
int o1=MX(C[i][j-1],C[i][j]),o2=MX(C[i][j],C[i][j+1]),L=j-1,R=j+1;
if(!(o1==o2&&o1==b[C[i][j]])) continue;
for(int k=j-2;k>=0;k--)
{
if(MX(C[i][k],C[i][j+1])==o1) L=k;
else break;
}
for(int k=j+2;k<C[i].size();k++)
{
if(MX(C[i][j-1],C[i][k])==o1) R=k;
else break;
}h[o1].push_back({j,i,L,R});
}//-1贡献，去重，代码写的听清楚了
}
else
{
for(int j=tot=0;j<C[i].size()-1;j++)
{
int t1=C[i][j],t2=C[i][j+1];c[++tot]=b[t1];w[tot]=1;//w记录是否为那种颜色
(t2-t1>1)&&(c[++tot]=MN(t1+1,t2-1),w[tot]=0);(t2-t1>2)&&(c[++tot]=MX(t1+1,t2-1),w[tot]=0);
}c[++tot]=b[C[i].back()];w[tot]=1;B1=tot/sq(m)+1;
for(int j=1;j<=tot;j++) bl[j]=(j-1)/B1+1;memset(le,0,sizeof(le));
for(int j=1;j<=bl[tot];j++) L[j]=R[j-1]+1,R[j]=j*B1;R[bl[tot]]=tot;
for(int j=1;j<=tot;j++) le[ls[j]=c[j]]++;sort(ls+1,ls+1+tot);
for(int j=1;j<=tot;j++) I[c[j]=lower_bound(ls+1,ls+1+tot,c[j])-ls]=j;
for(int j=1;j<=n;j++) le[j]+=le[j-1];//离散化细节主要在le上，其他的都是套路
for(int j=1,ll,rr;j<=m;j++) ll=le[l[j]-1]+1,rr=le[r[j]],
(ll<=rr)&&(q[bl[ll]].push_back({ll,rr,j}),1);MO();
}
}MAT::init();
for(int i=1;i<=n;i++)
{
for(node j:g[i])
{
int c=j.c;
for(int k=j.l;k<=j.w;k++) for(int I=j.w+1;I<=j.r;I++)
MAT::add(MN(C[c][k],C[c][I]),1);
}
for(node j:h[i])
{
int c=j.c;
for(int k=j.l;k<j.w;k++) for(int I=j.w+1;I<=j.r;I++)
MAT::add(MN(C[c][k],C[c][I]),-1);
}
for(int j:as[i]) ans[j]+=MAT::ask(l[j],n);
}//单点加区间查统计贡献
for(int i=1;i<=m;i++) wr(ans[i]);
return IO::fout(),0;
}