记录编号	140659	评测结果	AAAAAAAAAA
题目名称	[AHOI 2013] 作业	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	13.101 s
提交时间	2014-11-23 10:41:01	内存使用	32.74 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int SIZEN=100010,SIZEM=1000010;
class TARRAY{
public:
	int n;
	int s[SIZEN];
	#define lowbit(x) ((x)&(-x))
	void clear(int x){n=x;memset(s,0,sizeof(s));}
	inline void add(int x,int t){for(;x<=n;x+=lowbit(x)) s[x]+=t;}
	inline int presum(int x){
		int ans=0;
		for(;x;x-=lowbit(x)) ans+=s[x];
		return ans;
	}
	inline int query(int l,int r){return presum(r)-presum(l-1);}
};
class Solver{
public:
	TARRAY T1;//权值树状数组
	int num[SIZEN];//每个权值有多少个
	TARRAY T2;//去重后的的权值树状数组
	void clear(int n){
		T1.clear(n);
		memset(num,0,sizeof(num));
		T2.clear(n);
	}
	inline void add(int x,int t){
		if(!x) return;
		T1.add(x,t);
		num[x]+=t;
		if(t==-1&&num[x]==0) T2.add(x,-1);
		else if(t==1&&num[x]==1) T2.add(x,1);
	}
	inline pair<int,int> query(int l,int r){return make_pair(T1.query(l,r),T2.query(l,r));}
}SV;
class QUERY{
public:
	int l,r;
	int a,b;
	int lb;
	int id;
};
bool operator < (QUERY a,QUERY b){
	if(a.lb==b.lb) return a.r<b.r;
	return a.lb<b.lb;
}
QUERY Q[SIZEM];
int A[SIZEN];
int N,M;
int belong[SIZEN];
pair<int,int> ans[SIZEM];
void work(void){
	sort(Q+1,Q+1+M);
	SV.clear(N);
	int nl=0,nr=0;
	for(int i=1;i<=M;i++){
		while(nl>Q[i].l) SV.add(A[--nl],1);
		while(nr<Q[i].r) SV.add(A[++nr],1);
		while(nl<Q[i].l) SV.add(A[nl++],-1);
		while(nr>Q[i].r) SV.add(A[nr--],-1);
		ans[Q[i].id]=SV.query(Q[i].a,Q[i].b);
	}
	for(int i=1;i<=M;i++) printf("%d %d\n",ans[i].first,ans[i].second);
}
void read(void){
	scanf("%d%d",&N,&M);
	int BT=sqrt(N+0.0),now=1,tot=0;
	for(int i=1;i<=N;i++){
		belong[i]=now,tot++;
		if(tot>BT) tot=0,now++;
	}
	for(int i=1;i<=N;i++) scanf("%d",&A[i]);
	for(int i=1;i<=M;i++){
		Q[i].id=i;
		scanf("%d%d%d%d",&Q[i].l,&Q[i].r,&Q[i].a,&Q[i].b);
		Q[i].lb=belong[Q[i].l];
	}
}
int main(){
	freopen("ahoi2013_homework.in","r",stdin);
	freopen("ahoi2013_homework.out","w",stdout);
	read();
	work();
	return 0;
}