HEOI2013 ALO

考虑枚举次大值来统计答案,记 $l1_i$ 为第 $i$ 个数字第一个大于 $a_i$ 的数字的位置,$l2_i$ 为第二个。$r1_i$,$r2_i$ 是右边的。

那么就存在两个区间 $(l1_i,r2_i)$ 和 $(l2_i,r1_i)$,所有以 $a_i$ 为次大值的区间都是这两个区间中的包含 $a_i$ 的子区间。那么只要计算 $(l2_i,r2_i)$ 中与 $a_i$ 异或值最大的结果就行了,使用可持久化 Trie 树。

#include <iostream>
#include <cstdio>
#include <algorithm>

const int MAXN = 50000;

int n, ans;
int a[MAXN | 1], pre[MAXN + 2], nxt[MAXN + 2], L[MAXN | 1], R[MAXN | 1];
std::pair < int, int > p[MAXN | 1];

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

namespace persistentTrie {
  struct Node {
    int size;
    Node *ch[2];
    Node() {}
  } *null, *root[MAXN | 1];
  Node *newNode() {
    Node *o = new Node;
    o -> size = 0;
    o -> ch[0] = o -> ch[1] = null;
    return o;
  }
  Node *update(Node *old, int val) {
    Node *New = newNode(), *o = New;
    for (int i = 31; ~i; --i) {
      int idx = (val >> i) & 1;
      o -> ch[idx] = newNode();
      o -> ch[idx ^ 1] = old -> ch[idx ^ 1];
      o -> ch[idx] -> size = old -> ch[idx] -> size + 1;
      o = o -> ch[idx];
      old = old -> ch[idx];
    }
    return New;
  }
  int query(Node *l, Node *r, int val) {
    int res = 0;
    for (int i = 31; ~i; --i) {
      int idx = ((val >> i) & 1) ^ 1;
      if (r -> ch[idx] -> size - l -> ch[idx] -> size > 0) {
        res = res << 1 | 1;
        r = r -> ch[idx];
        l = l -> ch[idx];
      } else {
        res = res << 1;
        r = r -> ch[idx ^ 1];
        l = l -> ch[idx ^ 1];
      }
    }
    return res;
  }
}

using namespace persistentTrie;

int main() {
  null = new Node;
  null -> size = 0;
  null -> ch[0] = null -> ch[1] = null;
  n = read();
  root[0] = null;
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    pre[i] = i - 1;
    nxt[i] = i + 1;
    p[i] = std::make_pair(a[i], i);
    root[i] = update(root[i - 1], a[i]);
  }
  nxt[n + 1] = n + 1;
  std::sort(p + 1, p + 1 + n);
  for (int i = 1; i <= n; ++i) {
    int l = pre[p[i].second], r = nxt[p[i].second];
    if (l == 0) L[i] = 1;
    else if (pre[l] == 0) L[i] = l;
    else L[i] = pre[l] + 1;
    if (r > n) R[i] = n;
    else if (nxt[r] == 0) R[i] = r;
    else R[i] = nxt[r] - 1;
    nxt[pre[p[i].second]] = nxt[p[i].second];
    pre[nxt[p[i].second]] = pre[p[i].second];
    ans = std::max(ans, query(root[L[i] - 1], root[R[i]], p[i].first));
  }
  printf("%d\n", ans);
  return 0;
}
最后修改:2019 年 08 月 16 日 10 : 56 AM

发表评论