Catalog
  1. 1. 突然感觉qxy和小z是同种生物
  • 莫队的一道裸题
    1. 这道题是需要我们经过一定的数学推导才可以做出来的。
      1. 具体过程如下:
  • 小Z的袜子-题解

    查看原题请戳这里

    突然感觉qxy和小z是同种生物

    莫队的一道裸题

    虽说莫队算是一种暴力的算法,但ta依然是某些题目的正解的。(dfs:我不服)

    这道题是需要我们经过一定的数学推导才可以做出来的。

    具体过程如下:

    对于L,R的询问。 设其中颜色为x,y,z的袜子的个数为a,b,c… 那么答案即为 (a*(a-1)/2+b*(b-1)/2+c*(c-1)/2....)/((R-L+1)*(R-L)/2) 化简得: (a^2+b^2+c^2+...x^2-(a+b+c+d+.....))/((R-L+1)*(R-L)) 即: (a^2+b^2+c^2+...x^2-(R-L+1))/((R-L+1)*(R-L)) 于是这道题目变成了求a^2+b^2+c^2+...x^2,这个过程我们可以用莫队去实现。 附一下代码:

    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
    89
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    #define re register
    #define INF 0x7fffffff

    using namespace std;

    long long read()
    {
    long long x = 0,f = 1; char ch;
    ch = getchar();
    while(ch >'9' || ch < '0'){if(ch == '-') f = -f; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
    }

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

    long long n,m,a[50005],xsort,p1,p2,t[50005],ans,cnt,g,ll,rr,in[50005],save1[50005],save2[50005];

    struct query{
    long long l,r,num;
    }q[50005];

    long long mysort(query x, query y)
    {
    if(x.l / xsort == y.l / xsort) return x.r < y.r;
    return x.l < y.l;
    }

    long long work(long long x)
    {
    return x * x;
    }

    void add(long long k)
    {
    long long u = a[k];
    if(k == 0) return ;
    ans = ans - work(t[u]);
    t[u] ++;
    ans = ans + work(t[u]);
    }

    void del(long long k)
    {
    long long u = a[k];
    if(k == 0) return ;
    ans = ans - work(t[u]);
    t[u] --;
    ans = ans + work(t[u]);
    }

    int main()
    {
    n = read(); m = read();
    for(re int i = 1; i <= n; i ++) a[i] = read();
    for(re int i = 1; i <= m; i++)
    {
    q[i].l = read();
    q[i].r = read();
    q[i].num = i;
    }
    xsort = sqrt(n);
    sort(q + 1, q + m + 1, mysort);
    for(re int i = 1; i <= m; i++)
    {
    ll =q[i].l; rr = q[i].r;
    while(p1 < ll){del(p1); p1 ++;}
    while(p1 > ll){p1 --; add(p1);}
    while(p2 < rr){p2 ++; add(p2);}
    while(p2 > rr){del(p2); p2 --;}
    cnt = (rr - ll + 1) * (rr - ll);
    save1[q[i].num] = ans - (rr - ll + 1);
    save2[q[i].num] = cnt;
    }
    for(re int i = 1; i <= m; i++)
    {
    if(save1[i] != 0 && save2[i] != 0) g = gcd(save1[i],save2[i]);
    else g = 1;
    if(save1[i] == 0 || save2[i] == 0) {printf("0/1\n"); continue ;}
    printf("%d/%d\n",save1[i] / g,save2[i] / g);
    }
    return 0;
    }
    Author: wflight
    Link: http://yoursite.com/2019/08/02/小Z的袜子-题解/
    Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
    Donate
    • 微信
    • 支付寶

    Comment