Gty的二逼妹子序列

题目描述

Autumn 和 Bakser 又在研究 Gty 的妹子序列了！但他们遇到了一个难题。

对于一段妹子们，他们想让你帮忙求出这之内美丽度 $\in [a,b]$ 的妹子的美丽度的种类数。

为了方便，我们规定妹子们的美丽度全都在 $[1,n]$ 中。

给定一个长度为 $n(1\le n\le 10^5)$ 的正整数序列 $s(1\le s_i\le n)$，对于 $m(1\le m\le 10^6)$ 次询问 $l,r,a,b$，每次输出 $s_l\cdots s_r$ 中，权值 $\in [a,b]$ 的权值的种类数。

输入格式

第一行包括两个整数 $n,m(1\le n\le 100000,1\le m\le 1000000)$，表示数列 $s$ 中的元素数和询问数。

第二行包括 $n$ 个整数 $s_1\cdots s_n(1\le s_i\le n)$。

接下来 $m$ 行,每行包括 $4$ 个整数 $l,r,a,b(1\le l\le r\le n,1\le a\le b\le n)$，意义见题目描述。

保证涉及的所有数在 C++ 的 int 内。保证输入合法。

输出格式

对每个询问，单独输出一行，表示 $s_l\cdots s_r$ 中权值 $\in [a,b]$ 的权值的种类数。

样例 #1

样例输入 #1

10 10
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4

样例输出 #1

2
0
0
2
1
1
1
0
1
2

提示

【样例的部分解释】

5 9 1 2
子序列为4 1 5 1 2
在[1,2]里的权值有1,1,2，有2种，因此答案为2。

3 4 7 9
子序列为5 1
在[7,9]里的权值有5，有1种，因此答案为1。

4 4 2 5
子序列为1
没有权值在[2,5]中的，因此答案为0。

2 3 4 7
子序列为4 5
权值在[4,7]中的有4,5，因此答案为2。

建议使用输入/输出优化。

#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],ans[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]]++;
}
void del(int x){
    //同样的,如果删除这个数之后,c[]数组变为了0,说明当前区间内已经没有这个值了,把种类数−1
	if(!(--c[x])) k[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 cal=0;
    //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++;
	}
	if(belong[aa]!=belong[bb]){
		for(int i=(belong[bb]-1)*dis+1;i<=bb;i++){//对于不完整块直接暴力
			if(c[i]) cal++;
		}
	}
	for(int i=belong[aa]+1;i<=belong[bb]-1;i++){//对于完整块直接统计
		cal+=k[i];
	}
    ans[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\n",ans[i]);
}