http://www.lydsy.com/JudgeOnline/problem.php?id=3236
BIT套SBT
Treap没救了，无论怎么优化常数都过不了，于是乎随便改成了SBT。。。。。。
开始SBT的sz我用的s维护结果狂RE。。。。。。
最后90s卡过。。。。。比莫队慢。。。。。。。
被虐了2h。。。。。。
早知道写个莫队。。。。。。
莫队明明是O(nsqrt(n)logn)我的是O(nlognlogn)为什么会慢想不通啊。。。。。。。。。。。
一定是我太弱了。。。。。。。。
Orz 5s过的神犇。。。。。。。。
。。。。。。。。。。。。。。。。。。。。
以后有时间试一下http://hi.baidu.com/greencloud/item/0e25878061444bde5e0ec1f7
//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int getint()
{
int r=0,k=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
return k*r;
}
/////////////////////////////////////////////////
int n,m;
int A[100010];
inline int rnd(){return (rand()<<16)|rand();}
struct data{int id,l,r,a,b;}q[1000010];
bool cmp(data a,data b){return a.r<b.r;}
int ans1[1000010],ans2[1000010];
int last[100010];
/////////////////////////////////////////////////
namespace SBT
{/////////////////////////////////
#define LS T[o].l
#define RS T[o].r
int root[100010];
struct data{int l,r,s,sz,cnt,x,w,sum;}T[1000010];
int sz;
inline void update(int o){T[o].s=T[LS].s+T[RS].s+T[o].cnt;T[o].sz=T[LS].sz+T[RS].sz+1;T[o].sum=T[LS].sum+T[RS].sum+T[o].w;}
inline void l_rot(int &o){int t=RS;RS=T[t].l;T[t].l=o;T[t].s=T[o].s;T[t].sz=T[o].sz;T[t].sum=T[o].sum;update(o);o=t;}
inline void r_rot(int &o){int t=LS;LS=T[t].r;T[t].r=o;T[t].s=T[o].s;T[t].sz=T[o].sz;T[t].sum=T[o].sum;update(o);o=t;}
inline void maintain(int &o,bool b)
{
if(!b)
{
if(!LS) return;
if(T[T[LS].l].sz>T[RS].sz) r_rot(o);
else if(T[T[LS].r].sz>T[RS].sz) l_rot(LS),r_rot(o);
else return;
}
else
{
if(!RS) return;
if(T[T[RS].r].sz>T[LS].sz) l_rot(o);
else if(T[T[RS].l].sz>T[LS].sz) r_rot(RS),l_rot(o);
else return;
}
maintain(LS,0); maintain(RS,1);
maintain(o,0); maintain(o,1);
}
inline void insert(int &o,int x)
{
if(o==0)
{
o=++sz; T[o].sz=T[o].s=T[o].cnt=1; T[o].x=x; T[o].w=0; T[o].sum=0;
return;
}
T[o].s++; T[o].sz++;
if(x<T[o].x)
{
insert(LS,x);
maintain(o,0);
}
else if(x>T[o].x)
{
insert(RS,x);
maintain(o,1);
}
else T[o].cnt++;
}
inline int query1(int o,int x)
{
int res=0;
while(o)
{
if(x<T[o].x) o=LS;
else if(x>T[o].x) res+=T[LS].s+T[o].cnt,o=RS;
else return res+T[LS].s+T[o].cnt;
}
return res;
}
inline int query2(int o,int x)
{
int res=0;
while(o)
{
if(x<T[o].x) res+=T[RS].s+T[o].cnt,o=LS;
else if(x>T[o].x) o=RS;
else return res+T[RS].s+T[o].cnt;
}
return res;
}
inline void add(int o,int clr,int x)
{
while(o)
{
T[o].sum+=x;
if(clr<T[o].x) o=LS;
else if(clr>T[o].x) o=RS;
else T[o].w+=x,o=0;
}
}
inline int query3(int o,int x)
{
int res=0;
while(o)
{
if(x<T[o].x) o=LS;
else if(x>T[o].x) res+=T[LS].sum+T[o].w,o=RS;
else return res+T[LS].sum+T[o].w;
}
return res;
}
inline int query4(int o,int x)
{
int res=0;
while(o)
{
if(x<T[o].x) res+=T[RS].sum+T[o].w,o=LS;
else if(x>T[o].x) o=RS;
else return res+T[RS].sum+T[o].w;
}
return res;
}
}/////////////////////////////////
namespace BIT
{/////////////////////////////////
inline void insert(int o,int x)
{
for(;o<=n;o+=o&-o)
SBT::insert(SBT::root[o],x);
}
inline int query1(int o,int a,int b)
{
using namespace SBT;
int s=0;
for(;o>0;o-=o&-o)
s+=SBT::query2(root[o],a) + SBT::query1(root[o],b);
return s;
}
inline int query2(int o,int a,int b)
{
using namespace SBT;
int s=0;
for(;o>0;o-=o&-o)
s+=SBT::query3(root[o],b) + SBT::query4(root[o],a) - SBT::query3(root[o],n);
return s;
}
inline void add(int o,int clr,int x)
{
for(;o<=n;o+=o&-o)
SBT::add(SBT::root[o],clr,x);
}
}/////////////////////////////////
/////////////////////////////////////////////////
void input()
{
using namespace BIT;
scanf("%d%d",&n,&m);
int x;
rep(i,1,n)
insert(i,A[i]=getint());
rep(i,1,m)
q[i].id=i, q[i].l=getint(), q[i].r=getint(), q[i].a=getint(), q[i].b=getint();
sort(&q[1],&q[m+1],cmp);
}
void solve()
{
using namespace BIT;
int cur=1;
int id,l,r,a,b;
rep(i,1,n)
{
int &lst=last[A[i]];
if(lst==0) add(i,A[i],1);
else add(lst,A[lst],-1), add(i,A[i],1);
last[A[i]]=i;
for(;q[cur].r==i && cur<=m;cur++)
{
id=q[cur].id; l=q[cur].l-1; r=q[cur].r; a=q[cur].a; b=q[cur].b;
int s1=query1(r,a,b)-r;
int s2=query1(l,a,b)-l;
ans1[id]=s1-s2;
s1=query2(r,a,b);
s2=query2(l,a,b);
ans2[id]=s1-s2;
}
}
rep(i,1,m) printf("%d %d\n",ans1[i],ans2[i]);
}
/////////////////////////////////////////////////
int main()
{
#ifndef _TEST
freopen("std.in","r",stdin); freopen("std.out","w",stdout);
#endif
input(),
solve();
return 0;
}