Luogu

分析

考虑莫队。则我们需要实现一个支持单点修改、区间求和和非 $0$ 数的个数的东西。

考虑用值域分块实现，对于每块维护内部的和和非 $0$ 数的个数即可。

总时间复杂度 $\mathcal{O}(m\sqrt{n})$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,B,C;
int a[N],S[N];
int L[N],R[N],bl[N];
int s[N],num[N],sum[N];
pair<int,int> ans[N];
struct query { int l,r,a,b,id; } q[N];
bool operator <(query a,query b) {
    return bl[a.l]!=bl[b.l]?a.l<b.l:(bl[a.l]&1?a.r<b.r:a.r>b.r);
}

inline void add(int w) { if (!s[w]) ++num[bl[w]]; ++sum[bl[w]],++s[w]; }
inline void del(int w) { --s[w],--sum[bl[w]]; if (!s[w]) --num[bl[w]]; }
inline pair<int,int> query(int l,int r) {
    pair<int,int> ans=make_pair(0,0);
    if (bl[l]==bl[r]) {
        for (re int i=l;i<=r;++i)
            ans.first+=s[i],ans.second+=(s[i]!=0);
    } else {
        for (re int i=bl[l]+1;i<=bl[r]-1;++i)
            ans.first+=sum[i],ans.second+=num[i];
        for (re int i=l;i<=R[bl[l]];++i)
            ans.first+=s[i],ans.second+=(s[i]!=0);
        for (re int i=L[bl[r]];i<=r;++i)
            ans.first+=s[i],ans.second+=(s[i]!=0);
    }
    return ans;
}

int main() {
    n=read(),m=read(); B=sqrt(n),C=n/B+(n%B!=0);
    for (re int i=1;i<=C;++i) L[i]=R[i-1]+1,R[i]=min(i*B,n);
    for (re int i=1;i<=n;++i) bl[i]=(i-1)/B+1;
    for (re int i=1;i<=n;++i) S[i]=a[i]=read();
    sort(S+1,S+n+1); int c=unique(S+1,S+n+1)-S-1;
    for (re int i=1;i<=n;++i) a[i]=lower_bound(S+1,S+c+1,a[i])-S;
    for (re int i=1;i<=m;++i) {
        q[i].l=read(),q[i].r=read();
        q[i].a=lower_bound(S+1,S+c+1,read())-S;
        q[i].b=upper_bound(S+1,S+c+1,read())-S-1;
        q[i].id=i;
    }
    sort(q+1,q+m+1);
    for (re int i=1,l=1,r=0;i<=m;++i) {
        if (q[i].a>q[i].b) { ans[q[i].id]=make_pair(0,0); continue; }
        while (l<q[i].l) del(a[l]),++l;
        while (l>q[i].l) --l,add(a[l]);
        while (r<q[i].r) ++r,add(a[r]);
        while (r>q[i].r) del(a[r]),--r;
        ans[q[i].id]=query(q[i].a,q[i].b);
    }
    for (re int i=1;i<=m;++i) printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}