分块

Posted on Edited on In Views:
Symbols count in article: 16k
题目 1 2 3 4 5 6 7 8 9
通过情况 O O O O O O O O O

说明

本博文大部分内容参考「分块」数列分块入门1 – 9 by hzwer，主要是个人的巩固训练。

方法总结

分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。

○ 数列的简单分块一般要考虑三个问题：\
①不完整的块的 $O \left( \sqrt{n} \right)$ 个元素怎么处理\
②$O \left( \sqrt{n} \right)$ 个整块怎么处理\
③要预处理什么信息(复杂度一般不超过$O \left( n \sqrt{n} \right)$）

○ 分块的大小可以直接计算，也可以可以生成一些大数据，然后用两份分块大小不同的代码来对拍，还可以根据运行时间尝试调整分块大小，减小常数。

○ 在块内使用其他数据结构进行维护（入门2、3、6、9）

○ 块的重构/重新分块（入门6）

分块入门 1

题面

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

代码

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
/*
 * @题目: LOJ 6277 数列分块入门 1
 * @算法: 分块
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-16 22:34:48
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-16 23:08:41
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 50010
#define maxm 100010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, size;
int v[maxn], block[maxn], lazytag[maxn];
void add(int l, int r, int c)
{
    rep(i, l, min(block[l] * size, r)) v[i] += c;
    if (block[l] != block[r])
        rep(i, (block[r] - 1) * size + 1, r) v[i] += c;
    rep(i, block[l] + 1, block[r] - 1)
        lazytag[i] += c;
}
int main()
{
    n = read(), size = sqrt(n);
    rep(i, 1, n) v[i] = read();
    rep(i, 1, n) block[i] = (i - 1) / size + 1; //划分块
    rep(i, 1, n)
    {
        int opt = read(), l = read(), r = read(), c = read();
        if (opt == 0)
            add(l, r, c);
        else if (opt == 1)
            printf("%d\n", v[r] + lazytag[block[r]]);
    }
    return 0;
}

分块入门 2

题面

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

代码

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
/*
 * @题目: LOJ 6277 数列分块入门 2
 * @算法: 分块
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-16 23:00:10
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-16 23:29:29
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define maxn 50010
#define pb push_back
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, size;
int v[maxn], block[maxn], lazytag[maxn];
vector<int> ve[505];
void reset(int x)
{
    ve[x].clear();
    rep(i, (x - 1) * size + 1, min(x * size, n)) ve[x].pb(v[i]);
    sort(ve[x].begin(), ve[x].end());
}
void add(int l, int r, int c)
{
    rep(i, l, min(block[l] * size, r)) v[i] += c;
    reset(block[l]);
    if (block[l] != block[r])
    {
        rep(i, (block[r] - 1) * size + 1, r) v[i] += c;
        reset(block[r]);
    }
    rep(i, block[l] + 1, block[r] - 1)
        lazytag[i] += c;
}
int query(int l, int r, int c)
{
    int res = 0;
    rep(i, l, min(block[l] * size, r)) if (v[i] + lazytag[block[l]] < c) res++;
    if (block[l] != block[r])
        rep(i, (block[r] - 1) * size + 1, r) if (v[i] + lazytag[block[r]] < c) res++;
    rep(i, block[l] + 1, block[r] - 1)
    {
        int k = c - lazytag[i];
        res += lower_bound(ve[i].begin(), ve[i].end(), k) - ve[i].begin();
    }
    return res;
}
int main()
{
    n = read(), size = sqrt(n);
    rep(i, 1, n) v[i] = read();
    rep(i, 1, n)
    {
        block[i] = (i - 1) / size + 1;
        ve[block[i]].pb(v[i]);
    }
    rep(i, 1, block[n])
        sort(ve[i].begin(), ve[i].end());
    rep(i, 1, n)
    {
        int opt = read(), l = read(), r = read(), c = read();
        if (opt == 0)
            add(l, r, c);
        else if (opt == 1)
            printf("%d\n", query(l, r, c * c));
    }
    return 0;
}

分块入门 3

题面

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

代码

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
/*
 * @题目: LOJ 6279 数列分块入门 3
 * @算法: 分块
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-16 23:30:27
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-16 23:52:01
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
#define maxn 100010
#define pb push_back
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, size;
int v[maxn], block[maxn], lazytag[maxn];
multiset<int> s[105];
void add(int l, int r, int c)
{
    rep(i, l, min(block[l] * size, r))
    {
        s[block[l]].erase(v[i]);
        v[i] += c;
        s[block[l]].insert(v[i]);
    }
    if (block[l] != block[r])
    {
        rep(i, (block[r] - 1) * size + 1, r)
        {
            s[block[r]].erase(v[i]);
            v[i] += c;
            s[block[r]].insert(v[i]);
        }
    }
    rep(i, block[l] + 1, block[r] - 1)
        lazytag[i] += c;
}
int query(int l, int r, int c)
{
    int res = -1;
    rep(i, l, min(block[l] * size, r))
    {
        int val = v[i] + lazytag[block[l]];
        if (val < c)
            res = max(val, res);
    }
    if (block[l] != block[r])
        rep(i, (block[r] - 1) * size + 1, r)
        {
            int val = v[i] + lazytag[block[r]];
            if (val < c)
                res = max(val, res);
        }
    rep(i, block[l] + 1, block[r] - 1)
    {
        int k = c - lazytag[i];
        set<int>::iterator it = s[i].lower_bound(k);
        if (it == s[i].begin())
            continue;
        --it;
        res = max(res, *it + lazytag[i]);
    }
    return res;
}
int main()
{
    n = read(), size = 1000;
    rep(i, 1, n) v[i] = read();
    rep(i, 1, n)
    {
        block[i] = (i - 1) / size + 1;
        s[block[i]].insert(v[i]);
    }
    rep(i, 1, n)
    {
        int opt = read(), l = read(), r = read(), c = read();
        if (opt == 0)
            add(l, r, c);
        else if (opt == 1)
            printf("%d\n", query(l, r, c));
    }
    return 0;
}

分块入门 4

题面

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

代码

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
/*
 * @题目: LOJ 6280 数列分块入门 4
 * @算法: 分块
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-17 17:13:21
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-17 18:05:40
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
#define maxn 50010
#define pb push_back
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, size;
ll v[maxn], lazytag[maxn];
int blo[maxn];
ll sum[maxn];
void add(int l, int r, int c)
{
    rep(i, l, min(blo[l] * size, r))
    {
        v[i] += c;
        sum[blo[l]] += c;
    }
    if (blo[l] != blo[r])
        rep(i, (blo[r] - 1) * size + 1, r)
        {
            v[i] += c;
            sum[blo[r]] += c;
        }
    rep(i, blo[l] + 1, blo[r] - 1) lazytag[i] += c;
}
ll query(int l, int r)
{
    ll res = 0;
    rep(i, l, min(blo[l] * size, r)) res += v[i] + lazytag[blo[i]];
    if (blo[l] != blo[r])
        rep(i, (blo[r] - 1) * size + 1, r)
        {
            res += v[i] + lazytag[blo[i]];
        }
    rep(i, blo[l] + 1, blo[r] - 1) res += sum[i] + size * lazytag[i];
    return res;
}
int main()
{
    n = read(), size = sqrt(n);
    rep(i, 1, n) v[i] = read();
    rep(i, 1, n)
    {
        blo[i] = (i - 1) / size + 1;
        sum[blo[i]] += v[i];
    }
    rep(i, 1, n)
    {
        int opt = read(), l = read(), r = read(), c = read();
        if (opt == 0)
            add(l, r, c);
        else if (opt == 1)
            printf("%lld\n", query(l, r) % (c + 1));
    }
    return 0;
}

分块入门 5

题面

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

代码

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
/*
 * @题目: LOJ 6281 数列分块入门 5
 * @算法: 分块
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-17 18:10:39
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-17 18:22:45
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#define maxn 50010
#define pb push_back
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, size;
int v[maxn], flag[maxn];
int blo[maxn];
int sum[maxn];
void solve_sqrt(int x)
{
    if (flag[x])
        return;
    flag[x] = 1, sum[x] = 0;
    rep(i, (x - 1) * size + 1, x * size)
    {
        v[i] = sqrt(v[i]), sum[x] += v[i];
        if (v[i] > 1)
            flag[x] = 0;
    }
}
void add(int l, int r, int c)
{
    rep(i, l, min(blo[l] * size, r))
    {
        sum[blo[l]] -= v[i];
        v[i] = sqrt(v[i]);
        sum[blo[l]] += v[i];
    }
    if (blo[l] != blo[r])
        rep(i, (blo[r] - 1) * size + 1, r)
        {
            sum[blo[r]] -= v[i];
            v[i] = sqrt(v[i]);
            sum[blo[r]] += v[i];
        }
    rep(i, blo[l] + 1, blo[r] - 1) solve_sqrt(i);
}
int query(int l, int r)
{
    int res = 0;
    rep(i, l, min(blo[l] * size, r)) res += v[i];
    if (blo[l] != blo[r])
        rep(i, (blo[r] - 1) * size + 1, r)
            res += v[i];
    rep(i, blo[l] + 1, blo[r] - 1) res += sum[i];
    return res;
}
int main()
{
    n = read(), size = sqrt(n);
    rep(i, 1, n) v[i] = read();
    rep(i, 1, n)
    {
        blo[i] = (i - 1) / size + 1;
        sum[blo[i]] += v[i];
    }
    rep(i, 1, n)
    {
        int opt = read(), l = read(), r = read(), c = read();
        if (opt == 0)
            add(l, r, c);
        else if (opt == 1)
            printf("%d\n", query(l, r));
    }
    return 0;
}

分块入门 6

题面

给出一个长为n的数列，以及n个操作，操作涉及单点插入，单点询问。

代码

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
/*
 * @题目: LOJ 6282 数列分块入门 6
 * @算法: 分块
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-17 18:48:01
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-18 09:31:11
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#define maxn 100010
#define pb push_back
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, m, size; //m为块的总数
int v[maxn];
vector<int> ve[1005];
int st[200010], top;
pair<int, int> query(int r)
{
    int x = 1;
    while (r > ve[x].size())
        r -= ve[x].size(), x++;
    return make_pair(x, r - 1);
}
void rebuild()
{
    top = 0;
    rep(i, 1, m)
    {
        for (vector<int>::iterator j = ve[i].begin(); j != ve[i].end(); j++)
            st[++top] = *j;
        ve[i].clear();
    }
    int size2 = sqrt(top);
    rep(i, 1, top) ve[(i - 1) / size2 + 1].pb(st[i]);
    m = (top - 1) / size2 + 1;
}
void insert(int l, int r)
{
    pair<int, int> t = query(l);
    ve[t.first].insert(ve[t.first].begin() + t.second, r);
    if (ve[t.first].size() > 20 * size)
        rebuild();
}
int main()
{
    n = read(), size = sqrt(n);
    rep(i, 1, n) v[i] = read();
    rep(i, 1, n) ve[(i - 1) / size + 1].pb(v[i]);
    m = (n - 1) / size + 1;
    rep(i, 1, n)
    {
        int opt = read(), l = read(), r = read(), c = read();
        if (opt == 0)
            insert(l, r);
        else if (opt == 1)
        {
            pair<int, int> t = query(r);
            printf("%d\n", ve[t.first][t.second]);
        }
    }
    return 0;
}

分块入门 7

题面

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

代码

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
/*
 * @题目: LOJ 6283 数列分块入门 7
 * @算法: 分块
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-18 09:30:34
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-18 09:57:20
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#define maxn 100010
#define pb push_back
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
const int mod = 10007;
int n, size;
int v[maxn], block[maxn], atag[1005], mtag[1005];
void reset(int x)
{
    rep(i, (x - 1) * size + 1, min(x * size, n))
        v[i] = (v[i] * mtag[x] + atag[x]) % mod;
    atag[x] = 0, mtag[x] = 1;
}
void solve(int opt, int l, int r, int c)
{
    reset(block[l]);
    rep(i, l, min(block[l] * size, r))
    {
        if (opt == 0)
            v[i] += c;
        else
            v[i] *= c;
        v[i] %= mod;
    }
    if (block[l] != block[r])
    {
        reset(block[r]);
        rep(i, (block[r] - 1) * size + 1, r)
        {
            if (opt == 0)
                v[i] += c;
            else
                v[i] *= c;
            v[i] %= mod;
        }
    }
    rep(i, block[l] + 1, block[r] - 1)
    {
        if (opt == 0)
            atag[i] = (atag[i] + c) % mod;
        else
        {
            atag[i] = (atag[i] * c) % mod;
            mtag[i] = (mtag[i] * c) % mod;
        }
    }
}
int main()
{
    n = read(), size = sqrt(n);
    rep(i, 1, n) v[i] = read();
    rep(i, 1, n) block[i] = (i - 1) / size + 1;
    rep(i, 1, block[n]) mtag[i] = 1;
    rep(i, 1, n)
    {
        int opt = read(), l = read(), r = read(), c = read();
        if (opt == 2)
            printf("%d\n", (v[r] * mtag[block[r]] + atag[block[r]]) % mod);
        else
            solve(opt, l, r, c);
    }
    return 0;
}

分块入门 8

题面

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

代码

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
/*
 * @题目: LOJ 6284 数列分块入门 8
 * @算法: 分块
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-18 09:58:45
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-18 10:31:28
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#define maxn 100010
#define pb push_back
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, size;
int v[maxn], block[maxn], tag[maxn];
void reset(int x)
{
    if (tag[x] == -1)
        return;
    rep(i, (x - 1) * size + 1, min(n, x * size))
        v[i] = tag[x];
    tag[x] = -1;
}
int solve(int l, int r, int c)
{
    int res = 0;
    reset(block[l]);
    rep(i, l, min(block[l] * size, r))
    {
        if (v[i] != c)
            v[i] = c;
        else
            res++;
    }
    if (block[l] != block[r])
    {
        reset(block[r]);
        rep(i, (block[r] - 1) * size + 1, r)
        {
            if (v[i] != c)
                v[i] = c;
            else
                res++;
        }
    }
    rep(i, block[l] + 1, block[r] - 1)
    {
        if (tag[i] != -1)
        {
            if (tag[i] != c)
                tag[i] = c;
            else
                res += size;
        }
        else
        {
            rep(j, (i - 1) * size + 1, i * size)
            {
                if (v[j] != c)
                    v[j] = c;
                else
                    res++;
            }
            tag[i] = c;
        }
    }
    return res;
}
int main()
{
    memset(tag, -1, sizeof(tag));
    n = read(), size = sqrt(n);
    rep(i, 1, n) v[i] = read();
    rep(i, 1, n) block[i] = (i - 1) / size + 1;
    rep(i, 1, n)
    {
        int l = read(), r = read(), c = read();
        printf("%d\n", solve(l, r, c));
    }
    return 0;
}

分块入门 9

题面

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

代码

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
/*
 * @题目: LOJ 6285 数列分块入门 9
 * @算法: 分块
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-07-18 09:58:56
 * @LastEditors: Blore
 * @LastEditTime: 2021-07-18 11:46:57
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <map>
#define maxn 100010
#define pb push_back
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, size;
int v[maxn], block[maxn];
int f[505][505];
map<int, int> mp;
int val[maxn], cnt[maxn];
vector<int> ve[maxn];
void init(int x)
{
    memset(cnt, 0, sizeof(cnt));
    int mx = 0, ans = 0;
    rep(i, (x - 1) * size + 1, n)
    {
        cnt[v[i]]++;
        int t = block[i];
        if (cnt[v[i]] > mx || (cnt[v[i]] == mx && val[v[i]] < val[ans]))
            ans = v[i], mx = cnt[v[i]];
        f[x][t] = ans;
    }
}
int find(int l, int r, int x)
{
    int t = upper_bound(ve[x].begin(), ve[x].end(), r) - lower_bound(ve[x].begin(), ve[x].end(), l);
    return t;
}
int query(int l, int r)
{
    int ans = f[block[l] + 1][block[r] - 1];
    int mx = find(l, r, ans);
    rep(i, l, min(block[l] * size, r))
    {
        int t = find(l, r, v[i]);
        if (t > mx || (t == mx && val[v[i]] < val[ans]))
            ans = v[i], mx = t;
    }
    if (block[l] != block[r])
    {
        rep(i, (block[r] - 1) * size + 1, r)
        {
            int t = find(l, r, v[i]);
            if (t > mx || (t == mx && val[v[i]] < val[ans]))
                ans = v[i], mx = t;
        }
    }
    return ans;
}
int main()
{
    n = read(), size = 200;
    int id = 0;
    rep(i, 1, n)
    {
        v[i] = read();
        if (!mp[v[i]])
        {
            mp[v[i]] = ++id;
            val[id] = v[i];
        }
        v[i] = mp[v[i]];
        ve[v[i]].pb(i);
    }
    rep(i, 1, n) block[i] = (i - 1) / size + 1;
    rep(i, 1, block[n]) init(i);
    rep(i, 1, n)
    {
        int l = read(), r = read();
        if (l > r)
            swap(l, r);
        printf("%d\n", val[query(l, r)]);
    }
    return 0;
}