11556: 【原1556】kthxor

题目

题目描述

author: yzh119 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1556

Description

给定一个数列a，数列中元素各不相同，每次可以对一个区间[l, r]进行查询，输出该区间中第2大的数与该区间所有数的异或最大值。

Input Format

第一行两个整数n,q，表示数列的长度和查询的数目。

第二行n个整数，表示这个数列。

第三行到第q+2行，每行两个整数l, r(l < r)，表示需要查询的区间。

Output Format

对于所有的查询，输出给定区间中第2大的数\(x\)与该区间所有数的异或最大值： \[\max_{l \leq i \leq r}\{ a_i \textrm{ xor } x\} \]

Sample Input

Sample Output

2
3
1

Sample Input

11 5
892644 79740 787789 423575 534594 883691 117827 628967 504689 290297 0
2 10
7 11
3 9
6 9
6 11

Sample Output

Limits

对于\(30\%\)的数据，\(n\leq 10000\)。

对于\(100\%\)的数据，\(n \leq 100000\)。

数列中所有的元素均不超过1e9。

yyong119's solution

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define N 3000010
using namespace std;
int n, Q, X[N], root[N];
int shu[N], num[N], top, tot;
int B[N];
int tsz, c[5000010][2], Sum[5000010], troot[100010];
int xsz, gs[N], ls[N], rs[N];

int find(int x) {

    int l = 1, r = tot, mid;
    while (l + 1 < r) {
        mid = (l + r) >> 1;
        if (num[mid] == x) return mid;
        if (num[mid] < x) l = mid;
        else r = mid;
    }
    if (num[l] == x) return l;
    else return r;
}

void Insert(int &x, int y, int l, int r, int p) {

    x = ++xsz;
    gs[x] = gs[y] + 1;
    ls[x] = ls[y]; rs[x] = rs[y];
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (p <= mid) Insert(ls[x], ls[y], l, mid, p);
    else Insert(rs[x], rs[y], mid + 1, r, p);
}

int Querysecond(int a, int b) {

    int L = root[a - 1], R = root[b];
    int l = 1, r = tot, mid, k = 2;
    while (l != r) {
        mid = (l + r) >> 1;
        if (gs[rs[R]] - gs[rs[L]] >= k) {
            l = mid + 1; L = rs[L]; R = rs[R];
        }
        else {
            k -= gs[rs[R]] - gs[rs[L]];
            r = mid; L = ls[L]; R = ls[R];
        }
    }
    return num[l];
}

void Trie_add(int x, int W) {

    int p = troot[W - 1], now = ++tsz;
    troot[W] = now;
    for (int i = (1 << 30); i > 0; i >>= 1) {
        Sum[now] = Sum[p] + 1;
        c[now][0] = c[p][0]; c[now][1] = c[p][1];
        if (x & i) {
            p = c[p][1];
            c[now][1] = ++tsz;
            now = c[now][1];
        }
        else {
            p = c[p][0];
            c[now][0] = ++tsz;
            now = c[now][0];
        }
    }
    Sum[now] = Sum[p] + 1;
}

int Trie_query(int x, int L, int R) {

    int res = 0, l = troot[L - 1], r = troot[R];
    for (int i = (1 << 30); i > 0; i >>= 1) {
        int p;
        if (x & i) p = 0; else p = 1;
        if (Sum[c[r][p]] - Sum[c[l][p]] > 0) {
            res += i;
            l = c[l][p]; r = c[r][p];
        }
        else {
            l = c[l][p ^ 1]; r = c[r][p ^ 1];
        }
    }
    return res;
}

int main() {

    int l, r;
    scanf("%d%d", &n, &Q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &X[i]);
        shu[++top] = X[i];
    }
    sort(shu + 1, shu + 1 + top);
    num[++tot] = shu[1];
    for (int i = 2; i <= top; i++) if (shu[i] != shu[i - 1]) num[++tot] = shu[i];
    for (int i = 1; i <= n; i++) X[i] = find(X[i]);
    for (int i = 1; i <= n; i++) {
        Insert(root[i], root[i - 1], 1, tot, X[i]);
        Trie_add(num[X[i]], i);
    }
    for (int i = 1; i <= Q; i++) {
        scanf("%d %d", &l, &r);
        int x = Querysecond(l, r);
        printf("%d\n", Trie_query(x, l, r));
    }
    return 0;
}