C++(clang++ 11.0.1) 解法, 执行用时: 208ms, 内存消耗: 5196K, 提交时间: 2023-05-24 23:51:47

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=5e4+5;
const int mod=1e9+7;
int a[maxn],cnt[2][maxn],belo[maxn];
struct query{
    int l,r,f,id;
    bool operator <(const query& q)const {
        return belo[l]!=belo[q.l]?(belo[l]<belo[q.l]):((belo[l]&1)?r<q.r:r>q.r);
    }
}q[maxn<<2];
ll now;
int ans[maxn],d[maxn];
inline void add(int &x,int i){
    (now+=cnt[i^1][x])%=mod;
    ++cnt[i][x];
}
inline void del(int &x,int i){
    (now-=cnt[i^1][x])%=mod;
    --cnt[i][x];
}
inline ll qpow(ll x,ll n){
    ll ans=1;
    while(n>0){
        if(n&1)
            ans=ans*x%mod;
        x=x*x%mod,n>>=1;
    }
    return ans;
}

int main() {
    int n,m;scanf("%d%d",&n,&m);
    int blo=pow(n,0.5);
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
        belo[i]=(i-1)/blo-1;
    }
    for(int i=1;i<=m;++i){
        int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        q[4*i-3]={r1,r2,1,i};
        q[4*i-2]={r1,l2-1,-1,i};
        q[4*i-1]={l1-1,r2,-1,i};
        q[4*i]={l1-1,l2-1,1,i};
        d[i]=1ll*(r2-l2+1)*(r1-l1+1)%mod;
    }
    sort(q+1,q+4*m+1);
    int l=0,r=0;
    for(int i=1;i<=4*m;++i){
        int ql=q[i].l,qr=q[i].r,qf=q[i].f;
        while(l<ql) add(a[++l],0);
        while(l>ql) del(a[l--],0);
        while(r<qr) add(a[++r],1);
        while(r>qr) del(a[r--],1);

        (ans[q[i].id]+=now*qf)%=mod;
    }
    for(int i=1;i<=m;++i)
        printf("%lld\n",1ll*(ans[i]+mod)%mod*qpow(d[i],mod-2)%mod);
    return 0;
}