今年第一更……噫

终于学会莫队了，不过目前只能做这样的模板题……

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
using namespace std;
const int maxn=50005;
typedef long long ll;
ll gcd(ll a,ll b){
    if(!b){
        return a;
    }else{
        return gcd(b,a%b);
    }
}
ll C2(ll n){
    register ll temp,ns1=n-1;
    if(n&1){
        temp=ns1>>1;
        return temp*n;
    }else{
        temp=n>>1;
        return temp*ns1;
    }
}
 
struct Node{
    int L_s;
    int L,R;
    int id;
    ll ans1,ans2;
};
bool cmp1(const Node& a,const Node& b){
    if(a.L_s==b.L_s){
        return a.R<b.R;
    }else{
        return a.L_s<b.L_s;
    }
}
bool cmp2(const Node& a,const Node& b){
    return a.id<b.id;
}
Node Q[maxn];
int C[maxn],d[maxn];
int n,m;
inline void add_p(int x,ll &ans){
    d[x]++;
    ans+=d[x]-1;
}
inline void sub_p(int x,ll &ans){
    d[x]--;
    ans-=d[x];
}
inline void Mo(){
    register int i,j,L_p,R_p,sqrt_n=sqrt(n+0.5);
    register ll ans,t_gcd,t2;
    for(i=1;i<=m;i++){
        Q[i].L_s=Q[i].L/sqrt_n;
    }
    sort(Q+1,Q+1+m,cmp1);
    L_p=R_p=Q[1].L;
    ans=0;
    d[C[L_p]]++;
    for(i=1;i<=m;i++){
        while(L_p<Q[i].L){
            sub_p(C[L_p],ans);
            L_p++;
        }
        while(L_p>Q[i].L){
            L_p--;
            add_p(C[L_p],ans);
        }
        while(R_p<Q[i].R){
            R_p++;
            add_p(C[R_p],ans);
        }
        while(R_p>Q[i].R){
            sub_p(C[R_p],ans);
            R_p--;
        }
        t2=C2(R_p-L_p+1);
        t_gcd=gcd(ans,t2);
        Q[i].ans1=ans/t_gcd;
        Q[i].ans2=t2/t_gcd;
    }
    sort(Q+1,Q+1+m,cmp2);
}
 
int main(){
    register int i;
    int a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&C[i]);
    }
    for(i=1;i<=m;i++){
        Q[i].id=i;
        scanf("%d%d",&a,&b);
        Q[i].L=a;
        Q[i].R=b;
    }
    Mo();
    for(i=1;i<=m;i++){
        printf("%lld/%lld\n",Q[i].ans1,Q[i].ans2);
    }
    return 0;
}

• 相关文章
• 全局相关文章