经典的莫队+值域分块
虽然直接用莫队+树状数组也是能过的
贴个板子
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
//#define A puts("YES")
//#define B puts("NO")
using namespace std;
typedef long long ll;
typedef double db;
const ll inf=1ll<<60;
const int N=1e5+5;
int S,t;
struct node{
int l,r,a,b,id;
bool operator < (const node &x) const{
if (l/S !=x.l/S) return l<x.l;
return (l/S) &1 ? r<x.r : r>x.r;
}
};
node q[N];
int n,m,c[N],L[N],R[N],pos[N];
int a[N],b[N],l,r,p,cnt[N];
struct key{
int a,b;
};
key ans[N];
void add(int x){
p=pos[x];
cnt[x]++;
a[p]++;
if (cnt[x]==1) b[p]++;
}
void sub(int x){
p=pos[x];
cnt[x]--;
a[p]--;
if (!cnt[x]) b[p]--;
}
void ask(int l,int r,int id){
int p=pos[l],q=pos[r];
int s1=0,s2=0;
if (p==q) {
fo(i,l,r) {
s1+=cnt[i];
s2+=cnt[i]>0;
}
ans[id]=(key){s1,s2};
return;
}
fo(i,p+1,q-1) {
s1+=a[i];
s2+=b[i];
}
fo(i,l,R[p]){
s1+=cnt[i];
s2+=cnt[i]>0;
}
fo(i,L[q],r) {
s1+=cnt[i];
s2+=cnt[i]>0;
}
ans[id]=(key){s1,s2};
}
int main(){
// freopen("data.in","r",stdin);
scanf("%d %d",&n,&m);
S=sqrt(n);
fo(i,1,n) scanf("%d",&c[i]);
fo(i,1,m){
scanf("%d %d %d %d",&q[i].l, &q[i].r, &q[i].a, &q[i].b);
q[i].id=i;
}
sort(q+1,q+m+1);
t=sqrt(N-1);
fo(i,1,t) {
L[i]=(i-1)*t+1;
R[i]=i*t;
}
if (R[t]<N-1) t++, L[t]=R[t-1]+1,R[t]=N-1;
fo(i,1,t) {
fo(j,L[i],R[i]) {
pos[j]=i;
}
}
l=1; r=0;
fo(i,1,m) {
while (l>q[i].l) add(c[--l]);
while (r<q[i].r) add(c[++r]);
while (l<q[i].l) sub(c[l++]);
while (r>q[i].r) sub(c[r--]);
ask(q[i].a, q[i].b, q[i].id);
}
fo(i,1,m) printf("%d %d\n",ans[i].a ,ans[i].b);
return 0;
}