记录编号	361026	评测结果	AAAAAAAAAA
题目名称	[AHOI 2013] 作业	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	14.585 s
提交时间	2017-01-02 18:26:58	内存使用	46.07 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e6+10;
int n,m,a[N],b[N],ans1[N],ans2[N],blo;
int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
int find(int x){//第一个不超过x的值 
	int l=0,r=n;
	while (l!=r){
		int mid=(l+r)>>1;
		if (b[mid+1]<=x) l=mid+1;else r=mid;
	}
	return l;
}
struct opt{int l,r,a,b,id;}Q[N];
bool cmp(const opt &x,const opt &y){
	return x.l/blo==y.l/blo?x.r<y.r:x.l/blo<y.l/blo;
}
struct bit{
	int a[N];
	void add(int p,int d){
		for (;p<=n;p+=p&-p) a[p]+=d;
	}
	int sum(int r){
		int ans=0;
		for (;r;r-=r&-r) ans+=a[r];
		return ans;
	}
}T1,T2;
int sum,cnt[N];
void push(int x){
	if (!cnt[x]) T2.add(x,1);
	cnt[x]++;T1.add(x,1);
}
void del(int x){
	cnt[x]--;T1.add(x,-1);
	if (!cnt[x]) T2.add(x,-1);
}
int main()
{
	freopen("ahoi2013_homework.in","r",stdin);
	freopen("ahoi2013_homework.out","w",stdout);
	scanf("%d%d",&n,&m);
	blo=sqrt(n);
	for (int i=1;i<=n;i++) b[i]=a[i]=read();
	sort(b,b+n+1);
	for (int i=1;i<=n;i++) a[i]=find(a[i]);
	for (int i=1;i<=m;i++){
		Q[i].l=read();
		Q[i].r=read();
		Q[i].a=read();
		Q[i].b=read();
		Q[i].a=find(Q[i].a-1);//差分 
		Q[i].b=find(Q[i].b);
		Q[i].id=i;
	}
	sort(Q+1,Q+m+1,cmp);
	for (int i=1;i<=m;){
		int flag=Q[i].l/blo,l=Q[i].l,r=l-1;
		for (;Q[i].l/blo==flag;i++){
			while (r<Q[i].r) r++,push(a[r]);
			while (l>Q[i].l) l--,push(a[l]);
			while (l<Q[i].l) del(a[l]),l++;
			ans1[Q[i].id]=T1.sum(Q[i].b)-T1.sum(Q[i].a);
			ans2[Q[i].id]=T2.sum(Q[i].b)-T2.sum(Q[i].a);
		}
		for (;r>=l;r--) del(a[r]);
	}
	for (int i=1;i<=m;i++)
		printf("%d %d\n",ans1[i],ans2[i]);
	return 0;
}