具体见代码

#include<bits/stdc++.h>
#define f(i,a,b) for (int i=a;i<=b;i++)
#define ff(i,a,b) for (int i=a;i>=b;i--)
#define ll long long
using namespace std;
const int N=1e5+10;
const int M=34010;
int a[N],cnt[N];
int n,m,cst,ans1[M];
map <int,int> mm;
bitset <N> ans[M],nb;
struct node
{
	ll l,r,num;
} b[3*M];
bool cmp1(node x,node y)
{
	return x.l<y.l;
}
bool cmp2(node x,node y)
{
	return x.r<y.r;
}
inline ll read()
{
	ll l=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9')
	{
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9') l=(l<<3)+(l<<1)+f*(c-'0'),c=getchar();
	return l;
}
void ins(int p)
{
	nb[p-cnt[p]]=1,cnt[p]++;
}
void del(int p)
{
	cnt[p]--,nb[p-cnt[p]]=0;
}
void solve()
{
	int tp=0;
	if (cst>=m) return;
	f(i,1,M-10)//当这里改成f(i,1,M)时原地暴毙（9T1R）
	{
		cst++;
		if (cst>m) break;
		b[++tp].l=read(),b[tp].r=read(),b[tp].num=i,ans1[i]+=b[tp].r-b[tp].l+1;
		b[++tp].l=read(),b[tp].r=read(),b[tp].num=i,ans1[i]+=b[tp].r-b[tp].l+1;
		b[++tp].l=read(),b[tp].r=read(),b[tp].num=i,ans1[i]+=b[tp].r-b[tp].l+1;
	}
	f(i,1,tp/3) ans[i].set();
	sort(b+1,b+tp+1,cmp1);
	for (int i=1; i<=tp; i+=320)
	{
		int r=min(tp,i+319);
		sort(b+i,b+r+1,cmp2);
	}
	int l=1,r=0;
	f(i,1,tp)
	{
		if(r<b[i].l)
		{
			f(j,l,r) del(a[j]);
			l=b[i].l,r=b[i].r;
			f(j,l,r) ins(a[j]);
		}
		else
		{
			while (l<b[i].l) del(a[l++]);
			while (l>b[i].l) ins(a[--l]);
			while (r<b[i].r) ins(a[++r]);
			while (r>b[i].r) del(a[r--]);
		}
		ans[b[i].num]&=nb;
	}
	f(i,l,r) del(a[i]);
	for (int i=1; i<=tp/3; i++) printf("%lld\n",ans1[i]-ans[i].count()*3);
	for (int i=1; i<=tp/3; i++) ans1[i]=0;
}
signed main()
{
	n=read(),m=read();
	f(i,1,n) a[i]=read(),mm[a[i]]++;
	map<int,int>::iterator it,it1;
	for (it=mm.begin(),it1=it,it1++; it1!=mm.end(); ++it,++it1)
		it1->second+=it->second;
	f(i,1,n) a[i]=mm[a[i]];
	solve(),solve(),solve();
	return 0;
}