然而并没有题面,2333
莫队+树状数组,20s稳得很…..
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define N 210010
#define M 1500000
using namespace std;
int n,m,block;
int f[N],a[N],itc[N];
int num[N],t[N];
int ans[M][2];
int read()
{
int out=0,flag=1;
char c=getchar();
while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
while(c>=48&&c<=57)
{
out=out*10+c-48;
c=getchar();
}
return out*flag;
}
struct node
{
int l,r,a,b,id;
}ask[M];
bool comp(node aa,node bb)
{
return itc[aa.l]==itc[bb.l]? aa.r<bb.r:itc[aa.l]<itc[bb.l];
}
bool cmp(node aa,node bb)
{
return aa.id<bb.id;
}
void ADD(int now,int it,int at[])
{
for(int i=now;i<=n;i+=(i&(-i)))
{
at[i]+=it;
}
}
void add(int now)
{
if(!num[now]) ADD(now,1,t);
num[now]++;
ADD(now,1,f);
}
void pop(int now)
{
num[now]--;
if(!num[now]) ADD(now,-1,t);
ADD(now,-1,f);
}
int Ask(int now,int at[])
{
if(now<1)return 0;
int re=0;
for(int i=now;i;i-=(i&(-i)))
{
re+=at[i];
}
return re;
}
int main()
{
freopen("ahoi2013_homework.in","r",stdin);
freopen("ahoi2013_homework.out","w",stdout);
n=read();m=read();
block=sqrt(n);
for(int i=1;i<=n;++i)
{
a[i]=read();
itc[i]=(i-1)/block+1;
}
for(int i=1;i<=m;++i)
ask[i].l=read(),ask[i].r=read(),ask[i].a=read(),ask[i].b=read(),ask[i].id=i;
sort(ask+1,ask+m+1,comp);
int L=ask[1].l,R=ask[1].r;
for(int i=L;i<=R;++i)
{
add(a[i]);
}
ans[ask[1].id][0]=Ask(ask[1].b,f)-Ask(ask[1].a-1,f);
ans[ask[1].id][1]=Ask(ask[1].b,t)-Ask(ask[1].a-1,t);
for(int i=2;i<=m;++i)
{
while(R<ask[i].r) add(a[++R]);
while(R>ask[i].r) pop(a[R--]);
while(L<ask[i].l) pop(a[L++]);
while(L>ask[i].l) add(a[--L]);
ans[ask[i].id][0]=Ask(ask[i].b,f)-Ask(ask[i].a-1,f);
ans[ask[i].id][1]=Ask(ask[i].b,t)-Ask(ask[i].a-1,t);
}
for(int i=1;i<=m;++i)
{
printf("%d %d\n",ans[i][0],ans[i][1]);
}
return 0;
}