记录编号	427918	评测结果	AAAAAAAAAA
题目名称	[AHOI 2013] 作业	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	3.332 s
提交时间	2017-07-23 19:17:13	内存使用	14.09 MiB

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=100000+10;
const int M=1000000+10;
const int qrt=1000;
int n,m,bl,qr;
int block[N],beg[qrt+10],bend[qrt+10],val[N],f[qrt+10],g[qrt+10],cnt[N];
struct DATE{
	int l,r,mn,mx,id;
}date[M];
struct P{
	int o,t;
}ans[M];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline bool cmp(DATE a,DATE b){
	if(block[a.l]==block[b.l]) return a.r<b.r;
	return block[a.l]<block[b.l];
}
inline void change(int pos,int va){
	int col=val[pos];int bll=block[col];
	cnt[col]+=va;f[bll]+=va;
	if((cnt[col]==1&&va>0)||(!cnt[col])) g[bll]+=va;
}
inline P query(int l,int r){
	int x=0,y=0;
	int le=block[l],ri=block[r];
	if(le==ri){
		for(int i=l;i<=r;i++){
			if(cnt[i]){
				x+=cnt[i];
				y+=1;
			}
		}
		P temp=(P){x,y};
		return temp;
	}
	for(int i=le+1;i<=ri-1;i++){
		x+=f[i];
		y+=g[i];
	}
	for(int i=l;i<=bend[le];i++){
		if(cnt[i]){
				x+=cnt[i];
				y+=1;
			}
	}
	for(int i=beg[ri];i<=r;i++){
		if(cnt[i]){
				x+=cnt[i];
				y+=1;
			}
	}
	P temp=(P){x,y};
	return temp;
}
inline void init(){
	for(int i=1;i<=bl;i++){
		beg[i]=qr*(i-1)+1;
		bend[i]=min(n,i*qr);
	}
}
int DK(){
	freopen("ahoi2013_homework.in","r",stdin);
    freopen("ahoi2013_homework.out","w",stdout);
	n=read();m=read();
	qr=sqrt(n+0.5);
	for(int i=1;i<=n;i++){
		val[i]=read();
		block[i]=(i-1)/qr+1;
	}
	bl=block[n];init();
	for(int i=1;i<=m;i++){
		date[i].l=read();date[i].r=read();
		date[i].mn=read();date[i].mx=read();
		date[i].id=i;
	}
	sort(date+1,date+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		for(;r<date[i].r;r++) change(r+1,1);
		for(;r>date[i].r;r--) change(r,-1);
		for(;l<date[i].l;l++) change(l,-1);
		for(;l>date[i].l;l--) change(l-1,1);
		int bh=date[i].id;
		ans[bh]=query(date[i].mn,date[i].mx);
	}
	for(int i=1;i<=m;i++)  printf("%d %d\n",ans[i].o,ans[i].t);
	return 0;
}
int dk=DK();
int main(){
	;
}