lg1494

链接:lg1494

题解

  • 显然要求的是$\frac {\sum_{i=1}^v{C_{f(i)}^2}}{C_{r-l+1}^2}$ (v表示数字值,f(i)表示数字i在区间内出现的次数)
  • 首先考虑分子$C_{x}^2=\frac {x^2-x}{2}$,分子可写成$\frac{\sum_{i=1}^{v}f(i)^2-\sum_{i=1}^{v}f(i)}{2}$
  • 显然$\sum_{i=1}^{v}f(i)=r-l+1$
  • 现在的问题是已知$[l,r]的值,如何求[l,r+1]的值,这时只增加了一个Z,是很好处理的,设原分子为S_0,现在为S$
  • 显然$S=S_0-f(Z)^2+(f(Z)+1)^2-1=S_0+2*f(Z),O(1)即可完成$
  • 这样区间间的移动就可以$O(|r-r_i|+|l-l_i|)$做到
  • 接下来就可以用莫队完成了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    #include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=1e5+7;
    template <typename T>inline void read(T &x){
    char c;x=0;int sign=1;
    do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
    x*=sign;
    }
    int n,m,f[N],col[N],pos[N];
    ll ans;
    struct node{
    int l,r,id;
    ll a,b;
    }q[N];
    inline ll gcd(ll a,ll b){
    while(b){
    ll t=a%b;
    a=b;
    b=t;
    }
    return a;
    }
    inline int cmp_id(node a,node b){return a.id<b.id;}
    inline int cmp_pos(node a,node b){return pos[a.l]==pos[b.l]?pos[a.r]<pos[b.r]:pos[a.l]<pos[b.l];}
    inline void init(){
    read(n);read(m);
    rep(i,1,n)read(col[i]);
    int x=sqrt(n);
    rep(i,1,n)pos[i]=(i-1)/x+1;
    rep(i,1,m){read(q[i].l);read(q[i].r);q[i].id=i;}
    sort(q+1,q+m+1,cmp_pos);
    }
    inline void modify(int p,ll &ans,int add){
    ans+=2*add*f[col[p]]+1;
    f[col[p]]+=add;
    }
    inline void modify(node &a){
    ll t=gcd(a.b,a.a);
    if(t){
    a.a/=t;
    a.b/=t;
    }
    }
    inline void solve(){
    int l=1,r=0;ans=0;
    rep(i,1,m){
    if(r<q[i].r){
    for(r=r+1;r<q[i].r;++r)modify(r,ans,1);
    modify(r,ans,1);
    }
    if(q[i].l<l){
    for(l=l-1;l>q[i].l;--l)modify(l,ans,1);
    modify(l,ans,1);
    }
    if(r>q[i].r){
    for(;r>q[i].r;--r)modify(r,ans,-1);
    //modify(r,ans,-1);
    }
    if(l<q[i].l){
    for(;l<q[i].l;++l)modify(l,ans,-1);
    //modify(l,ans,-1);
    }
    if(q[i].l==q[i].r){
    q[i].a=0;
    q[i].b=1;
    continue;
    }
    q[i].a=ans-q[i].r+q[i].l-1;
    q[i].b=1ll*(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
    modify(q[i]);
    }
    sort(q+1,q+m+1,cmp_id);
    rep(i,1,m)printf("%lld/%lld\n",q[i].a,q[i].b);
    }
    int main(){
    init();
    solve();
    return 0;
    }