记录编号	587680	评测结果	AAAAAAAAAA
题目名称	[AHOI 2013] 作业	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.985 s
提交时间	2024-04-16 15:02:52	内存使用	23.77 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+10,M = 330;
const ll inf = 1e17;


int read(){
    int x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}


int n,m,B;
int a[N];
struct query{
    int l,r,id,a,b;
    bool operator < (const query x)const{
        if(l / B != x.l / B)return l < x.l;
        return (l / B) ? r < x.r : r > x.r;
    }
}q[N];


struct BLOCK{
    int B = 320,t,bl[N],L[N],R[N];
    int s1[M],s2[M],cnt[N];
    void build(){
        t = (1e5-1)/B+1;
        for(int i = 1;i <= t;i++)L[i] = (i-1)*B+1,R[i] = min(i*B,100000);
        for(int i = 1;i <= n;i++)bl[i] = (i-1)/B+1;
    }
    void add(int x){s1[bl[x]] += !cnt[x]++,s2[bl[x]]++;}
    void del(int x){s1[bl[x]] -= !--cnt[x],s2[bl[x]]--;}
    int ask1(int l,int r){
        int p = bl[l],q = bl[r],ans = 0;
        if(p == q){
            for(int i = l;i <= r;i++)ans += cnt[i] > 0;
            return ans;
        }
        for(int i = l;i <= R[p];i++)ans += cnt[i] > 0;
        for(int i = L[q];i <= r;i++)ans += cnt[i] > 0;
        for(int i = p+1;i <= q-1;i++)ans += s1[i];
        return ans;
    }
    int ask2(int l,int r){
        int p = bl[l],q = bl[r],ans = 0;
        if(p == q){
            for(int i = l;i <= r;i++)ans += cnt[i];
            return ans;
        }
        for(int i = l;i <= R[p];i++)ans += cnt[i];
        for(int i = L[q];i <= r;i++)ans += cnt[i];
        for(int i = p+1;i <= q-1;i++)ans += s2[i];
        return ans;
    }
}bl; 
int ans1[N],ans2[N];
int main(){
	freopen("ahoi2013_homework.in","r",stdin);
    freopen("ahoi2013_homework.out","w",stdout);
    n = read(),m = read();
    B = 1.0 * n / sqrt(m) + 1;
    for(int i = 1;i <= n;i++)a[i] = read();
    for(int i = 1;i <= m;i++)q[i].l = read(),q[i].r = read(),q[i].a = read(),q[i].b = read(),q[i].id = i;
    sort(q+1,q+1+m);
    bl.build();
    for(int i = 1,l = 1,r = 0;i <= m;i++){
        while(l > q[i].l)bl.add(a[--l]);
        while(r < q[i].r)bl.add(a[++r]);
        while(l < q[i].l)bl.del(a[l++]);
        while(r > q[i].r)bl.del(a[r--]);
        ans1[q[i].id] = bl.ask1(q[i].a,q[i].b);
        ans2[q[i].id] = bl.ask2(q[i].a,q[i].b);
    }
    for(int i = 1;i <= m;i++)printf("%d %d\n",ans2[i],ans1[i]);

	return 0;

}