题目传送门：洛谷P4396。
题意简述：
给定一个长度为\(n\)的数列。有\(m\)次询问，每次询问区间\([l,r]\)中数值在\([a,b]\)之间的数的个数，和数值在\([a,b]\)之间的不同的数的个数。
题解：
第一问可以用主席树维护，但是第二问呢？
考虑离线处理询问，用莫队算法。
问题转化为加入一个数，删除一个数，统计数值在一个区间中的数的个数。
离散化后可以用树状数组维护，但是复杂度多个log，变成了\(O(n\sqrt{n}\log n)\)。
考虑对数值也分块，先离散化，然后也是根号分块。修改时是$O(1)$的，查询是$O(\sqrt{n})$的。
那么考虑莫队的复杂度，有\(O(n\sqrt{n})\)次修改，但是只有$O(n)$次查询，那么总复杂度仍然是$O(n\sqrt{n})$。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define F(i,a,b) for(int i=(a);i<=(b);++i) 4 5 int n,q,S,T,U; 6 int a[100001],b[100001],blk[100001]; 7 struct D{int l,r,a,b,id;}Q[100001]; 8 bool cmp(D i,D j){return blk[i.l]==blk[j.l]?i.r<j.r:blk[i.l]<blk[j.l];} 9 int cnt[100001],bel[100001],sum[320],num[320]; 10 pair<int,int> Ans[100001]; 11 12 void Ins(int p,int x){ 13 if(!cnt[p]) ++num[bel[p]]; 14 cnt[p]+=x, sum[bel[p]]+=x; 15 if(!cnt[p]) --num[bel[p]]; 16 } 17 18 pair<int,int> Qur(int a,int b){ 19 if(a>b) return make_pair(0,0); 20 int S=0,N=0; 21 if(bel[a]==bel[b]) F(i,a,b) {if(cnt[i]) S+=cnt[i], ++N;} 22 else{ 23 F(i,bel[a]+1,bel[b]-1) S+=sum[i], N+=num[i]; 24 F(i,a,bel[a]*U) if(cnt[i]) S+=cnt[i], ++N; 25 F(i,bel[b]*U-U+1,b) if(cnt[i]) S+=cnt[i], ++N; 26 } 27 return make_pair(S,N); 28 } 29 30 int main(){ 31 scanf("%d%d",&n,&q); S=sqrt(n)+0.5; 32 F(i,1,n) blk[i]=(i-1)/S+1; 33 F(i,1,n) scanf("%d",a+i), b[i]=a[i]; 34 sort(b+1,b+n+1); T=unique(b+1,b+n+1)-b-1; 35 U=sqrt(T)+0.5; 36 F(i,1,T) bel[i]=(i-1)/U+1; 37 F(i,1,n) a[i]=lower_bound(b+1,b+T+1,a[i])-b; 38 F(i,1,q) scanf("%d%d%d%d",&Q[i].l,&Q[i].r,&Q[i].a,&Q[i].b), Q[i].id=i; 39 sort(Q+1,Q+q+1,cmp); 40 int L=1,R=0; 41 F(i,1,q){ 42 while(L>Q[i].l) --L, Ins(a[L],1); 43 while(R<Q[i].r) ++R, Ins(a[R],1); 44 while(L<Q[i].l) Ins(a[L],-1), ++L; 45 while(R>Q[i].r) Ins(a[R],-1), --R; 46 Ans[Q[i].id]=Qur(lower_bound(b+1,b+T+1,Q[i].a)-b,upper_bound(b+1,b+T+1,Q[i].b)-b-1); 47 } 48 F(i,1,q) printf("%d %d\n",Ans[i].first,Ans[i].second); 49 return 0; 50 }