[AHOI2013]作业(过程看注释)

题目描述

此时己是凌晨两点，刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。

然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文……小 A 压力巨大。

这时小 A 碰见了一道非常恶心的数学题，给定了一个长度为 $n$ 的数列和若干个询问，每个询问是关于数列的区间表示数列的第 $l$ 个数到第 $r$ 个数)，首先你要统计该区间内大于等于 $a$，小于等于 $b$ 的数的个数，其次是所有大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数。

小 A 望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。

输入格式

第一行两个整数 $n,m$

接下来 $n$ 个不超过 $10^5$ 的正整数表示数列

接下来 $m$ 行，每行四个整数 $l,r,a,b$，具体含义参见题意。

输出格式

输出 $m$ 行，分别对应每个询问，输出两个数，分别为在 $l$ 到 $r$ 这段区间中大小在 $[a,b]$ 中的数的个数，以及大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数（具体可以参考样例）。

样例 #1

样例输入 #1

3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3

样例输出 #1

2 2
1 1
3 2
2 1

提示

$N\le 100000,M\le 100000$，读入的数字均为 $[1,10^5]$ 内的正整数。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
//用普通的莫队维护区间，问题间转移的时候 O(1) 增减值域分块中的元素
//当莫队把已知区间移动到询问区间的时候，利用值域分块查询答案即可
struct modui{
    int l,r,qa,qb,id;
}s[N];
int n,m,dis,a[N],c[N],pos[N],belong[N],L=1,R=0;
int k[N],sum[N],ans1[N],ans2[N],kmax=0;
bool cmp(modui x,modui y){//按左端点分块，然后在同一个块当中区间右端点要递增
	if (pos[x.l]!=pos[y.l]) return x.l<y.l;
    if(pos[x.l]&1) return x.r<y.r;//奇偶性优化
	return x.r>y.r;//都是为了加速
}
void add(int x){
    //如果当前加入这个值之后,c[]数组为1,说明这个值是第一次加入,把种类数+1
	if((++c[x])==1) k[belong[x]]++;
	sum[belong[x]]++;
}
void del(int x){
    //同样的,如果删除这个数之后,c[]数组变为了0,说明当前区间内已经没有这个值了,把种类数−1
	if(!(--c[x])) k[belong[x]]--;
	sum[belong[x]]--;
}
void query(int l,int r,int aa,int bb,int id){//移动指针的时候，对应地去删除或添加对答案的贡献
	while (L<l) del(a[L++]);//左指针往右移删除
	while (L>l) add(a[--L]);//左指针往左移加入
	while (R<r) add(a[++R]);//右指针往右移加入
	while (R>r) del(a[R--]);//右指针往左移删除
    int tot=0,cal=0;
    //tot代表总数,cal代表种类
    //在询问中,我们把[a,b]分成[a,belong[a]∗block],[belong[a]+1,belong[b]−1],[(belong[b]−1)∗block+1,b]进行统计
    //和常规分块询问操作一样
	for(int i=aa;i<=min(belong[aa]*dis,bb);i++){//对于不完整块直接暴力
		if(c[i]) cal++;
		tot+=c[i];
	}
	if(belong[aa]!=belong[bb]){
		for(int i=(belong[bb]-1)*dis+1;i<=bb;i++){//对于不完整块直接暴力
			if(c[i]) cal++;
			tot+=c[i];
		}
	}
	for(int i=belong[aa]+1;i<=belong[bb]-1;i++){//对于完整块直接统计
		tot+=sum[i];
		cal+=k[i];
	}
    ans1[id]=tot;//记录答案
    ans2[id]=cal;
	return;
}
int main(){
    cin>>n>>m;
    dis=sqrt(n);//块大小
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[i]=(i-1)/dis+1;//pos标记每个数所属的分块
    for(int i=1;i<=m;i++){
        scanf("%d %d %d %d",&s[i].l,&s[i].r,&s[i].qa,&s[i].qb);
		s[i].id=i;//排序将会打乱原有的询问顺序,借此离线
        kmax=max(s[i].qb,kmax);//将询问中出现的最大值设为kmax,以此分块
    }
    sort(s+1,s+1+m,cmp);
    dis=sqrt(kmax);//块大小
    for(int i=1;i<=kmax;i++) belong[i]=(i-1)/dis+1;
    for(int i=1;i<=m;i++) query(s[i].l,s[i].r,s[i].qa,s[i].qb,s[i].id);
    for(int i=1;i<=m;i++) printf("%d %d\n",ans1[i],ans2[i]);
}