04/12
16:10
OI

[HEOI2013]ALO

[HEOI2013]ALO

正解可持久化Trie。于是抄洛谷题解打了个暴力,A了。。。不过bzoj被加强版数据搞WA。

就是假设每个位置是区间第二大,向左右暴力扩展这样。不细讲了,因为是错的:比如有数据7 5 3 2,第二小是5,5^2=7,但是按照暴力解法是6。当然暴力可以加上同时考虑两边的就能过了。贴一下洛谷AC代码。

#include <bits/stdc++.h>
using namespace std;

inline int rd() {
    int a = 1, b = 0; char c = getchar();
    while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
    while (isdigit(c)) b = b * 10 + c -'0', c = getchar();
    return a ? b : -b;
}

const int N = 50233;
int n, a[N], cnt, ans, x;

int main() {
    n = rd();
    for (int i = 1; i <= n; ++i)
        a[i] = rd();
    for (int i = 1; i <= n; ++i) {
        x = cnt = 0;
        for (int j = i - 1; j >= 1; --j) {
            if (a[j] > a[i]) ++cnt;
            if (cnt > 1) {
                ans = max(ans, x);
                break;
            }
            x = max(x, a[i] ^ a[j]);
        }
        if (cnt == 1) ans = max(ans, x);
        x = cnt = 0;
        for (int j = i + 1; j <= n; ++j) {
            if (a[j] > a[i]) ++cnt;
            if (cnt > 1) {
                ans = max(ans, x);
                break;
            }
            x = max(x, a[i] ^ a[j]);
        }
    }
    cout << ans << endl;
    return 0;
}

正解:枚举每个值做次大值,然后如果能快速找出一个值和它xor之后最大就行了。考虑使用可持久化01Trie,把数字按位放进Trie里,可持久化一下,就可以给定一个区间,在树上对于每一位,尽可能去走和它相反的位,以快速找到最大值。

把所有值从大到小排序,然后按顺序考虑,把值出现位置插入set中。取出当前位置,因为set中已有的位置的数都比当前大,所以显然[前驱的前驱+1,后驱的后驱-1]是可以考虑与当前值xor的位置。在此区间内查询一下就可以了。

复杂度O(nlogn)

#include <bits/stdc++.h>
using namespace std;

namespace kai586123 {
inline int rd() {
    int a = 1, b = 0; char c = getchar();
    while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
    while (isdigit(c)) b = b * 10 + c -'0', c = getchar();
    return a ? b : -b;
}

const int N = 50000 + 2333, INF = 0x3f3f3f3f;

int ch[N * 50][2], num, root[N * 50], sum[N * 50];
set<int> st;

struct Node {
    int val, id;
} a[N];

bool operator<(const Node &n1, const Node &n2) {
    return n1.val > n2.val;
}

int insert(int p, int val) {
    int now, tmp = now = ++num;
    for (int i = 30; i >= 0; --i) {
        int t = (val >> i) & 1;
        ch[now][0] = ch[p][0];
        ch[now][1] = ch[p][1];
        p = ch[p][t];
        now = ch[now][t] = ++num;
        sum[now] = sum[p] + 1;
    }
    return tmp;
}

int query(int val, int l, int r) {
    int ans = 0;
    for (int i = 30; i >= 0; --i) {
        int t = (val >> i) & 1;
        if (sum[ch[r][t ^ 1]] - sum[ch[l][t ^ 1]]) {
            l = ch[l][t ^ 1];
            r = ch[r][t ^ 1];
            ans |= 1 << i;
        }
        else {
            l = ch[l][t];
            r = ch[r][t];
        }
    }
    return ans;
}

void main() {
    int n = rd(), ans = 0;
    for (int i = 1; i <= n; ++i) {
        a[i].val = rd(); a[i].id = i;
        root[i] = insert(root[i - 1], a[i].val);
    }
    sort(a + 1, a + n + 1);
    st.insert(-INF); st.insert(-INF - 1);
    st.insert(INF); st.insert(INF + 1);
    st.insert(a[1].id);
    for (int i = 2; i <= n; ++i) {
        int l = max(1, *--(--st.lower_bound(a[i].id)) + 1),
            r = min(n, *(++st.upper_bound(a[i].id)) - 1);
        if (l <= r) {
            ans = max(ans, query(a[i].val, root[l - 1], root[r]));
            st.insert(a[i].id);
        }
    }
    cout << ans << endl;
}
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen("data.txt", "r", stdin);
    #endif
    return kai586123::main(), 0;
}