P4098 ALO

发表于2020-07-12更新于2023-09-15字数统计869阅读时长8分

ALO

Description

任意选取区间 [l,r][l,r] 并将区间次大值和区间内的某个数异或，求所有区间中异或值的最大值。

Solution

  • 设 aia_i 为次大值，则只需求出 aia_i 为次大值的最大区间范围 [li,ri][l_i,r_i]，通过可持久化trie贪心即可求出最大异或值
  • 设位置i左边第一个大于 aia_i 的数的位置为 l1l_1， 第二个大于 aia_i 为 l2l_2
  • 设位置i右边第一个大于 aia_i 的数的位置为 r1r_1， 第二个大于 aia_i 为 r2r_2
  • 则可选择的区间为 [l1+1,r2−1][l_1 + 1,r_2 − 1] 和 [l2+1,r1−1][l_2 + 1,r_1 − 1]，但其实只需求区间 [l2+1,r2−1][l_2 + 1,r_2 − 1] 的异或最大值

  • 求大于 aia_i 的数即求 aia_i 的后继，将原数组排序后一次插入平衡树(set)，则已插入的数值一定是 aia_i 的后继，只需以下标为key， lower_bound求出 l2,r2l_2,r_2
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    struct node {
        int key, pos;
        inline bool operator < (const node &other) const {
            return pos < other.pos;
        }
    }jewel[MAXN];

    sort(jewel + 1, jewel + n + 1, cmp); //按key值从大到小插入元素
    s.insert(jewel[1]); //按key值从大到小插入元素
    for (int i = 2, L, R; i <= n; i++) {
       l = r = s.lower_bound(jewel[i]); //求后继(后继已插入 按indices查找)

        if (l != s.begin()) --l;
        if (l != s.begin()) --l, L = l->pos + 1;
        else L = 1;

       if (r != s.end()) ++r;
       if (r != s.end()) R = r->pos - 1;
       else R = n;

      res = max(res, search(root[R], jewel[i].key, L));
      s.insert(jewel[i]);
    }

Code

ALO
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
#include <bits/stdc++.h>
constexpr int MAXN = 5e4 + 4;
constexpr int BIT = 30;

using namespace std;

template <typename T>
inline void read(T &x) {
    int f = 1; x = 0;
    char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct node {
    int key, pos;
    inline bool operator < (const node &other) const {
        return pos < other.pos;
    }
}jewel[MAXN];

inline bool cmp(const node &a, const node &b) {
    return a.key > b.key;
}

struct Trie {
    Trie *son[2];
    int lst;
}Tree[MAXN << 5], *root[MAXN];
using Node = Trie *;

inline Node newNode(Node &root) {
    static int nptr;
    return root = &Tree[++nptr];
}

inline void insert(Node pre, Node root, int x, int index) {
    for (int i = BIT - 1; ~i; i--) {
        int tmp = (x >> i) & 1;
        if (pre) root->son[tmp ^ 1] = pre->son[tmp ^ 1];
        root->lst = max(root->lst, index);
        root = newNode(root->son[tmp]), pre = pre ? pre->son[tmp] : NULL;
    }
    root->lst = max(root->lst, index);
}

inline int search(Node root, int x, int limit) {
    int res = 0;
    for (int i = BIT - 1; ~i; i--) {
        int tmp = (x >> i) & 1;
        if (root->son[tmp ^ 1] && root->son[tmp ^ 1]->lst >= limit)
            res |= (1 << i), root = root->son[tmp ^ 1];
        else root = root->son[tmp];
    }
    return res;
}

int main() {
    int n, res(0);
    set<node> s;
    set<node>::iterator l, r;
    read(n);
    insert(Tree, newNode(root[0]), 0, 0);
    for (int i = 1; i <= n; i++) {
        read(jewel[i].key), jewel[i].pos = i;
        insert(root[i - 1], newNode(root[i]), jewel[i].key, i);
    }
    sort(jewel + 1, jewel + n + 1, cmp); //按key值从大到小插入元素
    s.insert(jewel[1]); //按key值从大到小插入元素
    for (int i = 2, L, R; i <= n; i++) {
        l = r = s.lower_bound(jewel[i]); //求后继(后继已插入 按indices查找)

        if (l != s.begin()) --l;
        if (l != s.begin()) --l, L = l->pos + 1;
        else L = 1;

        if (r != s.end()) ++r;
        if (r != s.end()) R = r->pos - 1;
        else R = n;

        res = max(res, search(root[R], jewel[i].key, L));
        s.insert(jewel[i]);
    }
    cout << res << endl;
    return 0;
}