分块

发表于 | 分类于 | | 热度: ℃

思路

分块是一种数据结构，往往把数据分为许多块来处理。让每一个 整块 维护一些信息。暴力区间两个端点的小块。时间复杂度一般带根号。

例题：loj 数列分块入门 1-9

官方题解

数列分块入门 1

Description

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，单点查值。

数据范围：$1<=n<=50000 , -2^{31}<=others,ans<=2^{31}-1$

Solution

把 $n$ 个数分成 $sqrt(n)$ 个块。$tag_i$ 表示第 $i$ 个块整个加上多少。

当遇到一个块 $i$ 被 $[l,r]$ 完全包含，使 $tag_i+=c$。如果块 $j$ 与 $[l,r]$ 有交集，暴力修改 $j$ 内被 $[l,r]$ 包含的元素。时间复杂度为 $O(n$ * $sqrt(n))$

设点 $i$ 所属的块为 $be_i$，未更改之前的值为 $a_i$，它最终的值即为 $tag_{be_i}+a_i$

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;

const int N = 100000;
int opt, l, r, c, n, unit;
int a[N], tag[N], be[N], kx[N], ky[N];

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

signed main()
{
    n = read(), unit = sqrt(n);
    memset(tag, 0, sizeof(tag));
    be[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        a[i] = read();
        be[i] = (i - 1) / unit + 1;
        if(be[i] != be[i - 1]) kx[be[i]] = i;
        ky[be[i]] = i;
    }
    for(int i = 1; i <= n; i++)
    {
        opt = read(), l = read(), r = read(), c = read();
        if(opt == 0)
        {
            for(int i = 1; i <= be[n]; i++)
            {
                if(l <= kx[i] && r >= ky[i]) tag[i] += c;
                else if(l > ky[i] || r < kx[i]) ;
                else for(int j = kx[i]; j <= ky[i]; j++)
                    if(l <= j && r >= j) a[j] += c;
            }
        }
        else
            printf("%d\n", a[r] + tag[be[r]]);
    }
    return 0;
}

数列分块入门 2

Description

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，询问区间内小于某个值 $x$ 的元素个数。

数据范围：$1<=n<=50000 , -2^{31}<=others, ans<=2^{31}-1$

Solution

对每个块内的元素进行排序，记录它原来的位置。区间加法如 $1$ 中操作。对于被完全包含的块，在块内二分，找到第一个大于等于 $x$ 的元素，该元素 $-1$ 到块的起点都是 $<x$ 的元素。可以使用 $lower$_$bound$

一个简单转换：$a_i+tag_{be_i}<x$ -> $a_i<x-tag_{be_i}$

对于不完整的块，直接暴力即可。总时间复杂度为 $O(n$*$sqrt(n)log_n)$

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define re register
using namespace std;

const int N = 60000;
struct node { int x, y; } b[N];
int n, opt, l, r, c, unit, e = 0, f = 1;
int tag[N], be[N], a[N], kx[N], ky[N];

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

bool cmp(node x, node y) { return a[x.x] < a[y.x]; }

int main()
{
    n = read(), unit = sqrt(n);
    memset(tag, 0, sizeof(tag));
    for(re int i = 1; i <= n; i++)
    {
        a[i] = read();
        b[i].x = b[i].y = i;
        e++;
        if(e == unit + 1) { f++; e = 1; kx[f] = i; }
        be[i] = f;
        ky[f] = i;
    }
    for(re int i = 1; i <= be[n]; i++)
    {
        sort(b + kx[i], b + ky[i] + 1, cmp);
        sort(a + kx[i], a + ky[i] + 1);
    }
    for(re int i = 1; i <= n; i++) b[i].x = i;
    for(re int k = 1; k <= n; k++)
    {
        opt = read(), l = read(), r = read(), c = read();
        if(opt == 0)
        {
            for(re int i = 1; i <= be[n]; i++)
            {
                if(l <= kx[i] && r >= ky[i]) tag[i] += c;
                else if(l > ky[i] || r < kx[i]) ;
                else
                {
                    for(re int j = kx[i]; j <= ky[i]; j++)
                        if(l <= b[j].y && r >= b[j].y) a[j] += c;
                    sort(b + kx[i], b + ky[i] + 1, cmp);
                    sort(a + kx[i], a + ky[i] + 1);
                    for(re int j = kx[i]; j <= ky[i]; j++) b[j].x = j;
                }
            }
        }
        if(opt == 1)
        {
            int ans = 0;
            for(re int i = 1; i <= be[n]; i++)
            {
                if(l <= kx[i] && r >= ky[i])
                    ans += lower_bound(a + kx[i], a + ky[i] + 1, c * c - tag[i]) - a - kx[i];
                else if(l > ky[i] || r < kx[i]) ;
                else
                {
                    int tot = 0;
                    for(re int j = kx[i]; j <= ky[i]; j++)
                        if(l <= b[j].y && r >= b[j].y && a[j] + tag[i] < c * c)
                            tot++;
                    ans += tot;
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

数列分块入门 3

Description

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，询问区间内小于某个值 $x$ 的前驱（比其小的最大元素）

数据范围：$1<=n<=100000 , -2^{31}<=others, ans<=2^{31}-1$

Solution

对 $2$ 稍作改动。在二分的时候取 $max$ 作为答案。

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define re register
using namespace std;

const int N = 60000;
struct node { int x, y; } b[N];
int n, opt, l, r, c, unit;
int tag[N], be[N], a[N], kx[N], ky[N];

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

bool cmp(node x, node y) { return a[x.x] < a[y.x]; }

int main()
{
    n = read(), unit = sqrt(n);
    memset(tag, 0, sizeof(tag));
    be[0] = 0;
    for(re int i = 1; i <= n; i++)
    {
        a[i] = read();
        b[i].x = b[i].y = i;
        be[i] = (i - 1) / unit + 1;
        if(be[i] != be[i - 1]) kx[be[i]] = i;
        ky[be[i]] = i;
    }
    for(re int i = 1; i <= be[n]; i++)
    {
        sort(b + kx[i], b + ky[i] + 1, cmp);
        sort(a + kx[i], a + ky[i] + 1);
    }
    for(re int i = 1; i <= n; i++) b[i].x = i;
    for(re int k = 1; k <= n; k++)
    {
        opt = read(), l = read(), r = read(), c = read();
        if(opt == 0)
        {
            for(re int i = 1; i <= be[n]; i++)
            {
                if(l <= kx[i] && r >= ky[i]) tag[i] += c;
                else if(l > ky[i] || r < kx[i]) ;
                else
                {
                    for(re int j = kx[i]; j <= ky[i]; j++)
                        if(l <= b[j].y && r >= b[j].y) a[j] += c;
                    sort(b + kx[i], b + ky[i] + 1, cmp);
                    sort(a + kx[i], a + ky[i] + 1);
                    for(re int j = kx[i]; j <= ky[i]; j++) b[j].x = j;
                }
            }
        }
        if(opt == 1)
        {
            int ans = 0;
            for(re int i = 1; i <= be[n]; i++)
            {
                if(l <= kx[i] && r >= ky[i])
                    ans += lower_bound(a + kx[i], a + ky[i] + 1, c * c - tag[i]) - a - kx[i];
                else if(l > ky[i] || r < kx[i]) ;
                else
                {
                    int tot = 0;
                    for(re int j = kx[i]; j <= ky[i]; j++)
                        if(l <= b[j].y && r >= b[j].y && a[j] + tag[i] < c * c)
                            tot++;
                    ans += tot;
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

数列分块入门 4

Description

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，区间求和。

数据范围：$1<=n<=50000 , -2^{31}<=others, ans<=2^{31}-1$

Solution

$sum_i$ 表示第 $i$ 个块的和，$tag_i$表示第 $i$ 个块整体加上多少。在整块上打 $tag$，暴力两边时更改 $sum$ 和原值。查询时，每个点的值为 $a_i+tag_{be_i}$，每个块的值为 $sum_i+tag_i$*$(end-st+1)$

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;

const int N = 60000;
int n, opt, unit, l, r, c, e = 0, f = 1;
int tag[N], be[N], a[N], kx[N], ky[N], sum[N];

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

signed main()
{
    n = read(), unit = sqrt(n);
    memset(sum, 0, sizeof(sum));
    memset(tag, 0, sizeof(tag));
    for(int i = 1; i <= n; i++)
    {
        a[i] = read();
        e++;
        if(e == unit + 1) { f++; e = 1; kx[f] = i; }
        be[i] = f;
        ky[f] = i;
    }
    for(int i = 1; i <= n; i++) sum[be[i]] += a[i];
    for(int i = 1; i <= n; i++)
    {
        opt = read(), l = read(), r = read(), c = read();
        if(opt == 0)
        {
            for(int i = 1; i <= be[n]; i++)
            {
                if(l <= kx[i] && r >= ky[i]) tag[i] += c;
                else if(l > ky[i] || r < kx[i]) ;
                else for(int j = kx[i]; j <= ky[i]; j++)
                    if(l <= j && r >= j) a[j] += c, sum[i] += c;
            }
        }
        else
        {
            int ans = 0;
            for(int i = 1; i <= be[n]; i++)
            {
                if(l <= kx[i] && r >= ky[i])
                    ans = (ans + sum[i] + tag[i] * (ky[i] - kx[i] + 1)) % (c + 1);
                else if(l > ky[i] || r < kx[i]) ;
                else for(int j = kx[i]; j <= ky[i]; j++)
                    if(l <= j && r >= j) ans = (ans + a[j] + tag[i]) % (c + 1);
            }
            printf("%d\n", ans % (c + 1));
        }
    }
    return 0;
}

数列分块入门 5

Description

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间开方，区间求和。

数据范围：$1<=n<=50000 , -2^{31}<=others, ans<=2^{31}-1$

Solution

一个数经过几次开方之后就会变成 $0$ 或 $1$，此后再开方不会改变其值。可以标记一个块内所有数值是不是已经改变不了了。如果无法改变，直接跳过。否则暴力。

Code

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>
using namespace std;

const int N = 100000;
int n, opt, l, r, c, unit;
int a[N], tag[N], sum[N], be[N], kx[N], ky[N];

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

int judge(int x)
{
    for(int i = kx[x]; i <= ky[x]; i++)
        if(a[i] != 0 && a[i] != 1) return 0;
    return 1;
}

int main()
{
    n = read(), unit = sqrt(n);
    be[0] = 0;
    memset(sum, 0, sizeof(sum));
    for(int i = 1; i <= n; i++)
    {
        a[i] = read();
        be[i] = (i - 1) / unit + 1;
        if(be[i] != be[i - 1]) kx[be[i]] = i;
        ky[be[i]] = i;
        sum[be[i]] += a[i];
    }
    memset(tag, 0, sizeof(tag));
    for(int k = 1; k <= n; k++)
    {
        opt = read(), l = read(), r = read(), c = read();
        if(opt == 0)
        {
            for(int i = 1; i <= be[n]; i++)
            {
                if(l <= kx[i] && r >= ky[i])
                {
                    if(tag[i]) continue;
                    for(int j = kx[i]; j <= ky[i]; j++)
                    {
                        sum[i] -= a[j];
                        a[j] = (int)sqrt(a[j]);
                        sum[i] += a[j];
                    }
                    tag[i] = judge(i);
                }
                else if(r < kx[i] || l > ky[i]) ;
                else
                {
                    if(tag[i]) continue;
                    for(int j = kx[i]; j <= ky[i]; j++)
                    {
                        if(l <= j && r >= j)
                        {
                            sum[i] -= a[j];
                            a[j] = (int)sqrt(a[j]);
                            sum[i] += a[j];
                        }
                    }
                    tag[i] = judge(i);
                }
            }
        }
        if(opt == 1)
        {
            int ans = 0;
            for(int i = 1; i <= be[n]; i++)
            {
                if(l <= kx[i] && r >= ky[i]) ans += sum[i];
                else if(l > ky[i] || r < kx[i]) ;
                else for(int j = kx[i]; j <= ky[i]; j++)
                    if(l <= j && r >= j) ans += a[j];
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

数列分块入门 6

Description

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及单点插入，单点询问，数据随机生成。

数据范围：$1<=n<=100000 , -2^{31}<=others, ans<=2^{31}-1$

Solution

做法1

使用链表维护，把当前数插入到 $l$ 前面，并使当前数加入 $l$ 所在块。对于每一次查询 $r$，先找出 $r$ 在哪一个块里，然后暴力这个块。

优化

如果数据不是随机的，每个块的大小会远远大于 $sqrt(n)$。每 $sqrt(n)$ 次插入之后重新分块。（代码没有优化）

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 300000;
int n, unit, opt, l, r, c, cnt;
int be[N], a[N], next[N], size[N], st[N];

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

int query(int x)
{
    int t = 0, ans;
    if(x == 0) return 0;
    for(int i = 1; i <= be[n]; i++)
    {
        int tot = t;
        if(t + size[i] >= x)
        {
            for(int j = st[i]; tot < x; j = next[j])
                tot++, ans = j;
            break;
        }
        t += size[i];
    }
    return ans;
}

int main()
{
    n = read(), unit = sqrt(n);
    cnt = n;
    be[0] = next[n] = 0;
    memset(size, 0, sizeof(size));
    for(int i = 1; i <= n; i++)
    {
        a[i] = read();
        be[i] = (i - 1) / unit + 1;
        size[be[i]]++;
        if(be[i] != be[i - 1]) st[be[i]] = i;
        next[i] = i + 1;
    }
    for(int i = 1; i <= n; i++)
    {
        opt = read(), l = read(), r = read(), c = read();
        if(opt == 0)
        {
            int s = query(l), s1 = query(l - 1), b = be[s];
            a[++cnt] = r;
            if(s1) next[s1] = cnt;
            next[cnt] = s;
            size[b]++;
            be[cnt] = b;
            if(st[b] == s) st[b] = cnt;
        }
        else printf("%d\n", a[query(r)]);
    }
    return 0;
}

数列分块入门 7

Description

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间乘法，区间加法，单点询问。

数据范围：$1<=n<=100000 , -2^{31}<=others, ans<=2^{31}-1$

Solution

设 $mul_i$ 为块 $i$ 整体乘上几，$add_i$ 为块 $i$ 整体加上几。块 $i$ 内的数乘以 $c$，$mul_i$ * $=c$，$add_i$ * $=c$。块 $i$ 内的数加上 $c$，$add_i+=c$。

特别注意：暴力两边的时候需要把乘法标记和加法标记都去掉，加到原始数组里面去。

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;

const int N = 200000, mod = 10007;
int n, unit, opt, l, r, c;
int be[N], kx[N], ky[N], a[N], mul[N], add[N];

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

signed main()
{
    n = read(), unit = sqrt(n);
    be[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        a[i] = read();
        be[i] = (i - 1) / unit + 1;
        if(be[i] != be[i - 1]) kx[be[i]] = i;
        ky[be[i]] = i;
    }
    for(int i = 1; i <= be[n]; i++) mul[i] = 1, add[i] = 0;
    for(int i = 1; i <= n; i++)
    {
        opt = read(), l = read(), r = read(), c = read();
        if(opt == 0)
        {
            for(int i = 1; i <= be[n]; i++)
            {
                if(l <= kx[i] && r >= ky[i]) add[i] = (add[i] + c) % mod;
                else if(l > ky[i] || r < kx[i]) ;
                else
                {
                    for(int j = kx[i]; j <= ky[i]; j++)
                    {
                        a[j] = (a[j] * mul[i] + add[i]) % mod;
                        if(l <= j && r >= j) a[j] = (a[j] + c) % mod;
                    }
                    mul[i] = 1, add[i] = 0;
                }
            }
        }
        if(opt == 1)
        {
            for(int i = 1; i <= be[n]; i++)
            {
                if(l <= kx[i] && r >= ky[i])
                {
                    mul[i] = (mul[i] * c) % mod;
                    add[i] = (add[i] * c) % mod;
                }
                else if(l > ky[i] || r < kx[i]) ;
                else
                {
                    for(int j = kx[i]; j <= ky[i]; j++)
                    {
                        a[j] = (a[j] * mul[i] + add[i]) % mod;
                        if(l <= j && r >= j) a[j] = (a[j] * c) % mod;
                    }
                    mul[i] = 1, add[i] = 0;
                }
            }
        }
        if(opt == 2)
            printf("%lld\n", (a[r] * mul[be[r]] + add[be[r]]) % mod);
    }
    return 0;
}

数列分块入门 8

Description

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间询问等于一个数 $c$ 的元素，并将这个区间的所有元素改为 $c$。

数据范围：$1<=n<=100000 , -2^{31}<=others, ans<=2^{31}-1$

Solution

设$tag_i$ 表示块 $i$ 的值。$hav_i$ 表示块 $i$ 内的元素是否相同。

对于整块修改，$tag_i=c/hav_i=true$。对于两边，先把整块的 $tag$ 都去掉，再使 $hav_i=0$

Code

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 200000;
int n, unit, l, r, c;
int a[N], be[N], kx[N], ky[N], tag[N], hav[N];

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

int main()
{
    n = read(), unit = sqrt(n);
    memset(hav, 0, sizeof(hav));
    be[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        a[i] = read();
        be[i] = (i - 1) / unit + 1;
        if(be[i] != be[i - 1]) kx[be[i]] = i;
        ky[be[i]] = i;
    }
    for(int k = 1; k <= n; k++)
    {
        l = read(), r = read(), c = read();
        int ans = 0;
        for(int i = 1; i <= be[n]; i++)
        {
            if(l <= kx[i] && r >= ky[i])
            {
                if(hav[i])
                {
                    if(tag[i] == c) ans += (ky[i] - kx[i] + 1);
                    continue;
                }
                for(int j = kx[i]; j <= ky[i]; j++)
                    if(a[j] == c) ans++;
            }
            else if(l > ky[i] || r < kx[i]) ;
            else
            {
                for(int j = kx[i]; j <= ky[i]; j++)
                {
                    if(hav[i]) a[j] = tag[i];
                    if(l <= j && r >= j && a[j] == c) ans++;
                }
                hav[i] = 0;
            }
        }
        printf("%d\n", ans);
        for(int i = 1; i <= be[n]; i++)
        {
            if(l <= kx[i] && r >= ky[i]) hav[i] = 1, tag[i] = c;
            else if(l > ky[i] || r < kx[i]) ;
            else
            {
                for(int j = kx[i]; j <= ky[i]; j++)
                {
                    if(hav[i]) a[j] = tag[i];
                    if(l <= j && r >= j) a[j] = c;
                }
                hav[i] = 0;
            }
        }
    }
    return 0;
}

数列分块入门 9

Description

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及询问区间的最小众数。

数据范围：$1<=n<=100000 , -2^{31}<=others, ans<=2^{31}-1$

Solution

陈立杰大神的区间众数解题报告

此题与链接中题目不同之处在于，此题没有修改操作，并且需要离散化。

由于太菜，窝的代码 $T$ 了几个点，只能拿到 $92 pts$。

Code 92pts

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
106
107
108
109
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#define re register
using namespace std;

const int N = 100010, SN = 1000;
vector <int> vec[N];
int n, unit, l, r, now = 0, id = 0;
int be[N], a[N], kx[N], ky[N], b[N], st[N], tot[N];
int f[SN][SN], c[SN][SN], cnt[N];

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

int ask(int l, int r, int x)
{
    return upper_bound(vec[x].begin(), vec[x].end(), r) - lower_bound(vec[x].begin(), vec[x].end(), l);
}

int solve(int l, int r)
{
    int maxx = c[be[l] + 1][be[r] - 1], id = f[be[l] + 1][be[r] - 1];
    for(re int i = l; i <= ky[be[l]]; i++)
    {
        int x = ask(l, r, a[i]);
        if(x > maxx || x == maxx && a[i] < id)
            maxx = x, id = a[i];
    }
    for(re int i = kx[be[r]]; i <= r; i++)
    {
        int x = ask(l, r, a[i]);
        if(x > maxx || x == maxx && a[i] < id)
            maxx = x, id = a[i];
    }
    return st[id];
}

int main()
{
    n = read(), unit = 200;
    be[0] = 0;
    for(re int i = 1; i <= n; i++)
    {
        a[i] = read();
        b[i] = a[i];
        be[i] = (i - 1) / unit + 1;
        if(be[i] != be[i - 1]) kx[be[i]] = i;
        ky[be[i]] = i;
    }
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - b - 1;
    for(re int i = 1; i <= n; i++)
    {
        int x = lower_bound(b + 1, b + m + 1, a[i]) - b;
        st[x] = a[i];
        a[i] = x;
        vec[a[i]].push_back(i);
    }
    for(re int i = 1; i <= be[n]; i++)
    {
        int maxx = 0, ans = 0x3f3f3f3f;
        memset(cnt, 0, sizeof(cnt));
        for(re int j = i; j <= be[n]; j++)
        {
            for(re int k = kx[j]; k <= ky[j]; k++)
            {
                cnt[a[k]]++;
                if(cnt[a[k]] > maxx || cnt[a[k]] == maxx && a[k] < ans)
                {
                    maxx = cnt[a[k]];
                    ans = a[k];
                }
            }
            f[i][j] = ans; c[i][j] = maxx;
        }
    }
    memset(cnt, 0, sizeof(cnt));
    for(re int i = 1; i <= n; i++)
    {
        l = read(), r = read();
        if(l > r) swap(l, r);
        if(be[l] == be[r] || be[l] == be[r] - 1)
        {
            int maxx = 0, ans = 0x3f3f3f3f;
            for(re int j = l; j <= r; j++)
            {
                cnt[a[j]]++;
                if(cnt[a[j]] > maxx || cnt[a[j]] == maxx && a[j] < ans)
                {
                    maxx = cnt[a[j]];
                    ans = a[j];
                }
            }
            for(re int j = l; j <= r; j++) cnt[a[j]] = 0;
            printf("%d\n", st[ans]);
        }
        else printf("%d\n", solve(l, r));
    }
    return 0;
}

还是借(chao)鉴(xi)一下大佬 $hzwer$ 的 $std$ 吧…