一道比较简单的莫队……
用bitset维护三个区间的交元素。
#include<bits/stdc++.h>
const int N=;
const int wy=;
#define UI unsigned int
#define rep(i,_x,_y) for (register int i=(_x);i<=(_y);i++)
#define rdp(i,_x,_y) for (register int i=(_x);i>=(_y);i--)
#define debug(x) cerr<<#x<<" = "<<x<<endl;
#define sqr(x) (x)*(x)
using namespace std;
int n,m,len,qaq,size,l1[N],r1[N],l2[N],r2[N],l3[N],r3[N],cal[(<<)+],A[N],b[N];
int block[N],pos[N],head[N],h[N];
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
struct Data{
int x;int v;
bool operator <(const Data &f)const{return x<f.x;}
}a[N];
struct bs{
UI S[];
inline void update(int x){S[x>>]^=(1U<<(x&));}
inline int count(){int tot=;
rep(i,,) tot+=cal[S[i]>>]+cal[S[i]&];
return tot;
}
void clear(){memset(S,,sizeof(S));}
}now,c[];
inline bs operator ^ (bs &x,bs &y){
bs z;rep(i,,) z.S[i]=x.S[i]^y.S[i];
return z;
}
inline bs operator & (bs &x,bs &y){
bs z;rep(i,,) z.S[i]=x.S[i]&y.S[i];
return z;
}
struct Node{
int l,r,id;
Node(int l=,int r=,int id=):l(l),r(r),id(id){}
bool operator<(const Node &tmp)const{return block[l]==block[tmp.l]?(block[l]&)?r>tmp.r:r<tmp.r:l<tmp.l;}
}q[N];
inline void add(int x){h[x]++;now.update(head[x]+h[x]-);}
inline void del(int x){now.update(head[x]+h[x]-);h[x]--;}
inline void solve(){
now.clear();memset(h,,sizeof(h));memset(c,,sizeof(c));
int l=,r=;
sort(q+,q+len+);
for(int i=;i<=len;i++){
int lx=q[i].l,rx=q[i].r,id=q[i].id;
while(lx<l)add(A[--l]);
while(lx>l)del(A[l++]);
while(rx<r)del(A[r--]);
while(rx>r)add(A[++r]);
c[id]=c[id]&now;
}
}
int main(){
//freopen("xp1.in","r",stdin);
//freopen("xwd.out","w",stdout);
n=read();m=read();size=(int)sqrt(n+.);
rep(i,,(<<)-) cal[i]=cal[i>>]+(i&);
for(int i=;i<=n;i++)block[i]=(i-)/size+;
for(int i=;i<=n;i++)a[i].x=read(),a[i].v=i;
sort(a+,a+n+);
for(int i=;i<=n;i++)A[a[i].v]=a[i].x==a[i-].x?A[a[i-].v]:++qaq;
for(int i=;i<=n;i++)b[i]=A[i];
sort(b+,b+n+);
for(int i=;i<=n;i++)if(b[i]!=b[i-])head[b[i]]=i;
for(int i=;i<=m;i++){
l1[i]=read();r1[i]=read();l2[i]=read();r2[i]=read();l3[i]=read();r3[i]=read();
pos[i]=r1[i]+r2[i]+r3[i]-l1[i]-l2[i]-l3[i]+;
}
for(int i=;i<=m;i+=wy){
len=;
for(int j=i;j<=i+wy-;j++){
if(j>m)break;
q[++len]=Node{l1[j],r1[j],j-i+};
q[++len]=Node{l2[j],r2[j],j-i+};
q[++len]=Node{l3[j],r3[j],j-i+};
}
solve();
for(int j=i;j<=i+wy-;j++){
if(j>m)break;
printf("%d\n",pos[j]-*c[j-i+].count());
}
}
}