题目描述

blablabla

样例

blablabla

算法1

(莫队算法)

其实代码都差不多 就是增加和删除要变化一下而已

时间复杂度

参考文献

C++ 代码

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

#define gc getchar
#define ll long long

inline ll read(){
    ll res=0,f=1;
    char ch=gc();
    while(!isdigit(ch)) f^=ch=='-',ch=gc();
    while(isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=gc();
    return f?res:-res;
} 

inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}

const int N=50100;
int a[N];
int n,m,t;
int num[N];
int L[N],R[N];
ll ans[N];
ll tot=0;
ll p[N];

struct Point{int l,r,id;}pos[N];

bool cmpl(Point &a,Point &b){return a.l<b.l;} 
bool cmpr(Point &a,Point &b){return a.r<b.r;}

void init(){
    sort(pos+1,pos+1+m,cmpl);
    t=sqrt(m);
    for(int i=1;i<=t;i++)
        L[i]=(i-1)*sqrt(m),R[i]=i*sqrt(m);
    if(R[t]<m){
        L[t+1]=R[t]+1;R[t+1]=m;
        t++;
    } 
    for(int i=1;i<=t;i++)
        sort(pos+L[i],pos+R[i],cmpr);
}

void Add(int x){tot+=(num[x]*(num[x]+1))/2-(num[x]*(num[x]-1))/2;num[x]++;}
void Dec(int x){tot+=((num[x]-2)*(num[x]-1))/2-(num[x]*(num[x]-1))/2;num[x]--;}


void work(){
    int l=1,r=0;
    tot=0;
    for(int i=1;i<=m;i++){
        while(l<pos[i].l) Dec(a[l++]);
        while(l>pos[i].l) Add(a[--l]);
        while(r<pos[i].r) Add(a[++r]);
        while(r>pos[i].r) Dec(a[r--]);
        ans[pos[i].id]=tot;
    }
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++) {
        pos[i].l=read(),pos[i].r=read();
        pos[i].id=i;
        p[i]=(pos[i].r-pos[i].l);
        p[i]=(p[i]+1)*p[i]/2;
    }
    init();
    work(); 
    for(int i=1;i<=m;i++){
        if(!ans[i]) printf("0/1\n");
        else{
            ll c=gcd(ans[i],p[i]);
            printf("%lld/%lld\n",ans[i]/c,p[i]/c);
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla