不难发现，问题即求满足以下条件的$(i,j)$对数：
1.$1\le i<j\le n$且$a_{i}=a_{j}$
2.$\min_{i\le k\le j}y_{k}\ge l$且$\max_{i\le k\le j}y_{k}\le r$
先考虑条件1，枚举$1\le x\le n$，并对满足$a_{i}=x$的$i$个数$cnt$分类讨论：
1.若$cnt\le B$（其中$B$为常数），那么$a_{i}=a_{j}=x$的区间个数和（指对所有这样的$x$）不超过$nB$，暴力预处理出此类区间$y_{i}$的最小值和最大值，即变为一个二维数点的问题
关于这个二维数点，注意到点初始给定且条件只有一边，因此对其中一维使用扫描线处理，那么另外一维即变为支持单点修改和区间查询
由于有$o(nB)$次修改和$o(m)$次查询，为了均摊可以采取多层分块的结构，假设分$t$层，则修改和查询的复杂度分别为$o(nBt)$和$o(mn^{\frac{1}{t}}t)$（取$t=2$即为直接分块，取$t=\log_{2}n$即为线段树）
2.若$cnt>B$，那么这类$x$不超过$\frac{n}{B}$个，对应的$i$将序列划分若干段，并求出每一段$y_{i}$的最大值和最小值，注意到我们仅关心于$l,r$和这些最小值和最大值的关系，因此只有$o(cnt)$个本质不同的位置
由此使用莫队，问题即是要维护被包含的段长度（和和平方和），为了做到线性可以使用回滚莫队+链表，复杂度即$o(cnt\sqrt{m}+m)$，那么总复杂度为$o(n\sqrt{m}+\frac{nm}{B})$
另外，为了去掉其中的$\log$，具体实现是可能要借助基数排序等操作，可以参考代码
取$B=\sqrt{m}$和$t=3$即可，时间复杂度为$o(n\sqrt{m}+mn^{\frac{1}{3}})$，可以通过
（由于常数问题，取$B=4\sqrt{m}$更优，另外为了实现方便代码中取了$t=2$）
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 100005
4 #define M 1000005
5 #define ll long long
6 #define pii pair<int,int>
7 #define fi first
8 #define se second
9 struct Data{
10 int l,r,id;
11 bool operator < (const Data &k)const{
12 return ((l<k.l)||(l==k.l)&&(r<k.r));
13 }
14 }Q[M];
15 vector<int>v[N];
16 int n,m,B,x,P[N];
17 ll ans[M];
18 namespace ST{
19 int lg[N],mn[N][20],mx[N][20];
20 void init(){
21 lg[0]=-1;
22 for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1;
23 for(int i=1;i<=n;i++)mn[i][0]=mx[i][0]=P[i];
24 for(int i=n;i;i--)
25 for(int j=1;j<20;j++){
26 mn[i][j]=min(mn[i][j-1],mn[min(i+(1<<j-1),n)][j-1]);
27 mx[i][j]=max(mx[i][j-1],mx[min(i+(1<<j-1),n)][j-1]);
28 }
29 }
30 int get_min(int l,int r){
31 int m=lg[r-l+1];
32 return min(mn[l][m],mn[r-(1<<m)+1][m]);
33 }
34 int get_max(int l,int r){
35 int m=lg[r-l+1];
36 return max(mx[l][m],mx[r-(1<<m)+1][m]);
37 }
38 }
39 namespace Subtask1{
40 int f[N],sum[N];
41 vector<int>V[N];
42 void update(int k){
43 f[k]++,sum[k>>8]++;
44 }
45 int query(int k){
46 int ans=0;
47 for(int i=0;i<(k>>8);i++)ans+=sum[i];
48 for(int i=((k>>8)<<8);i<=k;i++)ans+=f[i];
49 return ans;
50 }
51 void calc(){
52 for(int i=1;i<=n;i++)
53 if (v[i].size()<=B){
54 for(int x=0;x<v[i].size();x++)
55 for(int y=x+1;y<v[i].size();y++){
56 int mn=ST::get_min(v[i][x],v[i][y]);
57 V[mn].push_back(ST::get_max(v[i][x],v[i][y]));
58 }
59 }
60 for(int i=n,k=m;i;i--){
61 for(int j=0;j<V[i].size();j++)update(V[i][j]);
62 while ((k)&&(Q[k].l==i)){
63 ans[Q[k].id]+=query(Q[k].r);
64 k--;
65 }
66 }
67 }
68 }
69 namespace Subtask2{
70 vector<int>V[N];
71 int sz,cnt,K,l,r,mn[N],mx[N],vis[N],id[N],pos[N],L0[N],L1[N],R0[N],R1[N],L[N],R[N],mnV[N];
72 ll Ans[N];
73 void init(){
74 Ans[0]=0;
75 memset(vis,0,sizeof(vis));
76 memset(L,0,sizeof(L));
77 memset(R,0,sizeof(R));
78 }
79 void check_add(int k){
80 if ((vis[k])&&(vis[k+1])){
81 Ans[0]+=(ll)(k-L[k]+1)*(R[k+1]-k);
82 R[L[k]]=R[k+1],L[R[k+1]]=L[k];
83 }
84 }
85 void check_del(int k){
86 if ((vis[k])&&(vis[k+1])){
87 R[L[k]]=k,L[R[k+1]]=k+1;
88 Ans[0]-=(ll)(k-L[k]+1)*(R[k+1]-k);
89 }
90 }
91 void add(int k){
92 vis[k]=1,L[k]=R[k]=k,Ans[0]++;
93 check_add(k-1),check_add(k);
94 }
95 void del(int k){
96 check_del(k-1),check_del(k);
97 vis[k]=L[k]=R[k]=0,Ans[0]--;
98 }
99 void addl(){
100 if ((L0[l])&&(mx[L0[l]]<=pos[r]))del(L0[l]);
101 if ((L1[l])&&(mx[L1[l]]<=pos[r]))del(L1[l]);
102 l++;
103 }
104 void decl(){
105 l--;
106 if ((L0[l])&&(mx[L0[l]]<=pos[r]))add(L0[l]);
107 if ((L1[l])&&(mx[L1[l]]<=pos[r]))add(L1[l]);
108 }
109 void addr(){
110 r++;
111 if ((R0[r])&&(pos[l]<=mn[R0[r]]))add(R0[r]);
112 if ((R1[r])&&(pos[l]<=mn[R1[r]]))add(R1[r]);
113 }
114 void decr(){
115 if ((R0[r])&&(pos[l]<=mn[R0[r]]))del(R0[r]);
116 if ((R1[r])&&(pos[l]<=mn[R1[r]]))del(R1[r]);
117 r--;
118 }
119 void calc(int k){
120 sz=v[k].size(),cnt=0;
121 memset(vis,0,sizeof(vis));
122 memset(L0,0,sizeof(L0));
123 memset(L1,0,sizeof(L1));
124 memset(R0,0,sizeof(R0));
125 memset(R1,0,sizeof(R1));
126 for(int i=1;i<sz;i++){
127 mn[i]=ST::get_min(v[k][i-1],v[k][i]);
128 mx[i]=ST::get_max(v[k][i-1],v[k][i]);
129 vis[mn[i]]=vis[mx[i]]=1;
130 }
131 for(int i=1;i<=n;i++){
132 if (vis[i])pos[++cnt]=i;
133 id[i]=cnt;
134 }
135 for(int i=1;i<sz;i++){
136 if (!L0[id[mn[i]]])L0[id[mn[i]]]=i;
137 else L1[id[mn[i]]]=i;
138 if (!R0[id[mx[i]]])R0[id[mx[i]]]=i;
139 else R1[id[mx[i]]]=i;
140 }
141 K=max(cnt/B,1);
142 for(int i=0,k=1;i*K<cnt;i++){
143 init();
144 int st=i*K+1,ed=min((i+1)*K,cnt);
145 for(int j=st;j<=cnt;j++){
146 mnV[j]=0x3f3f3f3f;
147 V[j].clear();
148 }
149 while ((k<=m)&&(Q[k].l<=pos[ed])){
150 mnV[id[Q[k].r]]=min(mnV[id[Q[k].r]],id[Q[k].l-1]+1);
151 V[id[Q[k].r]].push_back(k);
152 k++;
153 }
154 for(int j=st;j<ed;j++){
155 l=j+1,r=j,Ans[0]=Ans[j+1]=0;
156 while (mnV[j]<l){
157 decl();
158 Ans[l]=Ans[0];
159 }
160 for(int k=0;k<V[j].size();k++)ans[Q[V[j][k]].id]+=Ans[id[Q[V[j][k]].l-1]+1];
161 while (l<=j)addl();
162 }
163 l=ed,r=ed-1,Ans[0]=0;
164 for(int j=ed;j<=cnt;j++){
165 addr();
166 Ans[l]=Ans[0];
167 while (mnV[j]<l){
168 decl();
169 Ans[l]=Ans[0];
170 }
171 for(int k=0;k<V[j].size();k++)ans[Q[V[j][k]].id]+=Ans[id[Q[V[j][k]].l-1]+1];
172 while (l<ed)addl();
173 Ans[0]=Ans[l];
174 }
175 }
176 }
177 void calc(){
178 for(int i=1;i<=n;i++)
179 if (v[i].size()>B)calc(i);
180 }
181 }
182 int main(){
183 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
184 cin>>n>>m;
185 B=4*(int)sqrt(m);
186 for(int i=1;i<=n;i++){
187 cin>>x;
188 v[x].push_back(i);
189 }
190 for(int i=1;i<=n;i++)cin>>P[i];
191 for(int i=1;i<=m;i++){
192 cin>>Q[i].l>>Q[i].r;
193 Q[i].id=i;
194 }
195 sort(Q+1,Q+m+1);
196 ST::init();
197 Subtask1::calc();
198 Subtask2::calc();
199 for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
200 return 0;
201 }