BZOJ2038 [2009国家集训队]小Z的袜子(hose)

BZOJ2038

满足O(1)转移相邻状态的条件,显然莫队。

N50000,,所以应定义某些变量为unsigned或long long。

具体可参考hzwer的题解


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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>


const int N = 50000 + 10;


struct sock
{
    int L, R, No, a, b;
    friend bool operator < (sock T1, sock T2)
    {
        return T1.No < T2.No;
    }
};


sock a[N];
unsigned c[N], p[N], s[N], ans;


void update(int , unsigned );
unsigned gcd(unsigned , unsigned );
unsigned sqr(unsigned );
bool comp(sock , sock );
int read(void);


int main(void)
{
    int n = read(), m = read(), blk = sqrt(n);
    for (int i = 1; i <= n; ++i)
    {
        c[i] = read();
        p[i] = i / blk;
    }
    for (int i = 1; i <= m; ++i)
    {
        a[i].L = read();
        a[i].R = read();
        a[i].No = i;
    }
    std::sort(a + 1, a + m + 1, comp);
    for (int i = 1, l = 1, r = 0; i <= m; ++i)
    {
        for (; l < a[i].L; ++l)
            update(l, -1);
        for (; l > a[i].L; --l)
            update(l - 1, 1);
        for (; r < a[i].R; ++r)
            update(r + 1, 1);
        for (; r > a[i].R; --r)
            update(r, -1);
        a[i].a = ans - (a[i].R - a[i].L + 1);
        a[i].b = (a[i].R - a[i].L + 1) * (a[i].R - a[i].L);
        unsigned tmp = gcd(a[i].a, a[i].b);
        a[i].a /= tmp;
        a[i].b /= tmp;
    }
    std::sort(a + 1, a + m + 1);
    for (int i = 1; i <= m; ++i)
        printf("%d/%d\n", a[i].a, a[i].b);
   
    return 0;
}


inline void update(int T, unsigned x)
{
    ans -= sqr(s[c[T]]);
    s[c[T]] += x;
    ans += sqr(s[c[T]]);
}


inline unsigned gcd(unsigned x, unsigned y)
{
    return y ? gcd(y, x % y) : x;
}


inline unsigned sqr(unsigned T)
{
    return T * T;
}


inline bool comp(sock T1, sock T2)
{
    return (p[T1.L] == p[T2.L] ? T1.R < T2.R : p[T1.L] < p[T2.L]);
}


inline int read(void)
{
    char x;
    while (!isdigit(x = getchar()))
        ;
    int num = x - '0';
    while (isdigit(x = getchar()))
        (num *= 10) += x - '0';
    return num;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注