记录编号	146739	评测结果	AAAAAAAAAA
题目名称	[AHOI 2013] 作业	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	15.251 s
提交时间	2015-01-19 16:42:00	内存使用	78.90 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define lb(x) ((x)&(-x))
#define Maxn 200010
#define Maxm 2000010
using namespace std;
struct asks{
	int l,r,a,b,pos,blc;
}A[Maxm];
int n,m,a[Maxn],C1[Maxm]={0},C2[Maxm]={0},tot[Maxn]={0};
int ans1[Maxm],ans2[Maxm],belong[Maxn],blcsiz;
inline bool cmpx(asks a,asks b){
	if(a.blc==b.blc) return a.r<b.r;
	return a.l<b.l;
}
int query1(int l,int r){
	int res=0; l--;
	for(;r;r-=lb(r)) res+=C1[r];
	for(;l;l-=lb(l)) res-=C1[l];
	return res;
}
int query2(int l,int r){
	int res=0; l--;
	for(;r;r-=lb(r)) res+=C2[r];
	for(;l;l-=lb(l)) res-=C2[l];
	return res;
}
void insert(int t,int v){
	for(int x=t;x<=n&&x;x+=lb(x)) C1[x]+=v; tot[t]+=v;
	if((tot[t]==1&&v>0)||tot[t]==0){
		for(int x=t;x<=n&&x;x+=lb(x)) C2[x]+=v;
	}
}
int main(){
	freopen("ahoi2013_homework.in","r",stdin);
	freopen("ahoi2013_homework.out","w",stdout);
	a[0]=0;
	scanf("%d%d",&n,&m); blcsiz=(int)sqrt(n+0.5);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),belong[i]=(i+1)/blcsiz+1;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&A[i].l,&A[i].r,&A[i].a,&A[i].b);
		A[i].pos=i; A[i].blc=belong[A[i].l];
	}
	sort(A+1,A+m+1,cmpx);
	int l=0,r=0;
	for(int i=1;i<=m;i++){
		while(l>A[i].l) insert(a[--l],1); while(r<A[i].r) insert(a[++r],1);
		while(l<A[i].l) insert(a[l++],-1); while(r>A[i].r) insert(a[r--],-1);
		ans1[A[i].pos]=query1(A[i].a,A[i].b);
		ans2[A[i].pos]=query2(A[i].a,A[i].b);
	}
	for(int i=1;i<=m;i++) printf("%d %d\n",ans1[i],ans2[i]);
	return 0;
}