好题！
我们观察题目，发现题目让我们求的可以写成：
\[(r_1-l_1+1)+(r_2-l_2+1)+(r_3-l_3+1)-3\times size \]其中：\(size\) 是三段中公共颜色的个数
问题转移成求三段公共颜色的个数。
考虑使用莫队，然后在转换左右边界的时候使用数组记录每个颜色出现几次，然后再求三个区间中每个颜色的最小值即可。
这显然是正确的，只是\(...\)，优化吧
考虑只用一个变量记录出所有颜色分别出现几次，普通数组肯定是不行的，所以要用 \(bitset\)。
但是问题来了，\(bitset\) 只能记录每个颜色是否出现，不能记录每个颜色出现几次
这个时候就不能转化了，因为无法转化，所以我们考虑运用人类智慧去使 \(bitset\) 可以做到。
我们发现转化左右边界的时候可以得到出这个颜色是第几次出现，那么我们再在离散化时做一下手脚，记录一下比这个颜色小的颜色有多少个，那么在增量时令位置 \(mn_i+co_i\) 变成一，其中 \(co_i\) 是 \(i\) 颜色出现次数，\(mn_i\) 是比 \(i\) 小的颜色个数，显然这个位置是空的，最后再令在三段取交集，就是每个颜色的最小出现次数（理解一下）。
减去的时候也是同理。
这个时候就可以将六个量变成三组，每组两个量 \((l_i,r_i)\)，分开求，大大降低时间复杂度
这个时候我们发现空间复杂度不够，用时间换空间，求三次就好了。
看代码吧：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+500;
int n,m,peo;
struct jgt
{
int zhi,id;
}sr[N];
bool cmp(jgt t1,jgt t2)
{
return t1.zhi<t2.zhi;
}
int a[N],b[N],sq,cnt,st[N];
struct jgt1
{
int l,r,id;
}q[N];
bool cmp1(jgt1 t1,jgt1 t2)
{
return (b[t1.l]^b[t2.l])?b[t1.l]<b[t2.l]:((b[t1.l]&1)?t1.r<t2.r:t1.r>t2.r);
// return (b[t1.l]^b[t2.l])?b[t1.l]<b[t2.l]:t1.r<t2.r;
}
int idx,la;
bitset<N> ans[35000],now;
int ans1[N],tong[N];
void add(int wz)
{
now.set(tong[a[wz]]+st[a[wz]],1);
tong[a[wz]]++;
}
void del(int wz)
{
tong[a[wz]]--;
now.set(tong[a[wz]]+st[a[wz]],0);
}
void slove()
{
sort(q+1,q+idx+1,cmp1);
for(int i=1;i<=idx/3;i++) ans[i].set();
int le=1,ri=0;
now.reset();
for(int i=1;i<=idx;i++)
{
while(ri<q[i].r) add(++ri);
while(le>q[i].l) add(--le);
while(ri>q[i].r) del(ri--);
while(le<q[i].l) del(le++);
ans[q[i].id-la]=(ans[q[i].id-la]&now);
}
for(int i=1;i<=idx;i++)
ans1[q[i].id]-=ans[q[i].id-la].count();
la=la+idx/3;
while(ri>=le) del(ri--);
idx=0;
}
int main()
{
scanf("%d %d",&n,&m);
sq=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&sr[i].zhi);
sr[i].id=i;
b[i]=(i-1)/sq+1;
}
sort(sr+1,sr+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(sr[i].zhi!=sr[i-1].zhi)
{
cnt++;
st[cnt]=i;
}
a[sr[i].id]=cnt;
}
for(int i=1;i<=m;i++)
{
idx++;
scanf("%d %d",&q[idx].l,&q[idx].r);
q[idx].id=i;
ans1[i]=ans1[i]+q[idx].r-q[idx].l+1;
idx++;
scanf("%d %d",&q[idx].l,&q[idx].r);
q[idx].id=i;
ans1[i]=ans1[i]+q[idx].r-q[idx].l+1;
idx++;
scanf("%d %d",&q[idx].l,&q[idx].r);
q[idx].id=i;
ans1[i]=ans1[i]+q[idx].r-q[idx].l+1;
if(idx>=1e5) slove();
}
if(idx!=0) slove();
for(int i=1;i<=m;i++)
printf("%d\n",ans1[i]);
return 0;
}