区间异或和异或区间最大值异或区间最小值 --- 题解 --- （字典树好题）

 区间异或和异或区间最大值异或区间最小值 ：

题目大意：

思路解析：

题目查询的是区间异或和 ^ 最小值 ^ 最大值，如果我们确定了最小值和最大值，[l,r]，假设a[l]是最小值，a[r]是最大值，但是如果我们a[l-1] 比最小值大，也比最大值小，那我们就可以往附近扩展，所以在了最小值和最大值后，我们还要选择最有效的区间异或和。

        最大值最小值的分布也有多种情况，

                一 最大值在左边，最小值在左边

                二最大值在右边，最小值在右边

                三最大值在左边，最小值在右边

                四最大值在右边，最小值在左边

对于一二这两种情况，其实是等同的，那我们固定区间在 [i,mid]，假设最大值和最小值都在这里面，看此时可选的区间能扩展到哪里，即最大值和最小值不变的区间有多少个，在这样的区间中找到最大的答案。这样i就可以从mid到l枚举，并且这样一定不会遗漏答案。

对于第三种和第三种情况，我们先预处理区间最小值，这样就枚举左边最大值的区间，并且将这个区间的最小值和右边能选择的最小值进行判断，又因为区间最小值一定是越靠近r越小，所以遍历不会回退。那我们就可以通过两个指针维护一个右边的区间 [j1，j2] 里面的元素都小于等于右边的最大值并且[j1,j2]里面的元素都大于等于右边的最大值。那我们就可以得到 [i,j1]....[i,j2]这些有效区间，然后利用字典树来寻优即可。

代码实现：

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static int MAXN = (int) 1e5 + 5;
    static int[][] ch = new int[MAXN * 25][2];
    static int[] tag = new int[MAXN * 25];
    static int tot = 0;
    static int[] a = new int[MAXN];
    static int[] pref= new int[MAXN];
    static int[] suf = new int[MAXN];
    static int ans = 0;
    static int[] Min = new int[MAXN];
    static int INF = (int) 1e9 +100;


    public static void main(String[] args) {
        int n = f.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = f.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            pref[i] = pref[i - 1] ^ a[i];
        }
        for (int i = n; i >= 1; i--) {
            suf[i] = suf[i + 1] ^ a[i];
        }
        divide(1, n);
        System.out.println(ans);

    }

    static void divide(int l, int r){
        if (l == r){
            ans = Math.max(ans, a[l]);
            return;
        }
        int mid = (l + r) >> 1;
        divide(l, mid); divide(mid+1, r);

        // max,min in [l,mid]
        init();
        for(int i=mid,mx=a[i],mn=a[i],j=mid+1,sum=0; i>=l; --i) {
            mx=max(mx,a[i]);mn=min(mn,a[i]);sum^=a[i];
            while(j<=r && a[j]>=mn && a[j]<=mx) {ins(pref[j]);++j;}
            ans=max(ans,query(mx^mn^sum^pref[mid]));
        }

        //max,min in [mid+1,r]
        init();
        for(int i=mid+1,mx=a[i],mn=a[i],j=mid,sum=0; i<=r; ++i) {
            mx=max(mx,a[i]);mn=min(mn,a[i]);sum^=a[i];
            while(j>=l && a[j]>=mn && a[j]<=mx) {ins(suf[j]);--j;}
            ans=max(ans,query(mx^mn^sum^suf[mid+1]));
        }

        //max in [l,mid], min in [mid+1,r]
        Min[mid]=INF;
        for(int i=mid+1; i<=r; ++i) Min[i]=min(Min[i-1],a[i]);
        init();
        for(int i=mid,mx=a[i],mn=a[i],j1=mid+1,j2=mid+1,sum=0; i>=l; --i) {
            mx=max(mx,a[i]);mn=min(mn,a[i]);sum^=a[i];
            while(j2<=r && a[j2]<=mx) {ins(Min[j2]^pref[j2]);++j2;}
            while(j1<j2 && Min[j1]>mn) {del(Min[j1]^pref[j1]);++j1;}
            ans=max(ans,query(mx^sum^pref[mid]));
        }

        // min in [l,mid],max in [mid+1,r]
        Min[mid+1]=INF;
        for(int i=mid; i>=l; --i) Min[i]=min(Min[i+1],a[i]);
        init();
        for(int i=mid+1,mx=a[i],mn=a[i],j1=mid,j2=mid,sum=0; i<=r; ++i) {
            mx=max(mx,a[i]);mn=min(mn,a[i]);sum^=a[i];
            while(j2>=l && a[j2]<=mx) {ins(Min[j2]^suf[j2]);--j2;}
            while(j1>j2 && Min[j1]>mn) {del(Min[j1]^suf[j1]);--j1;}
            ans=max(ans,query(mx^sum^suf[mid+1]));
        }
    }
    static int min (int x, int y){
        return Math.min(x, y);
    }
    static int max (int x, int y){
        return Math.max(x, y);
    }

    static int newNode(){
        int root = ++tot;
        ch[root][0] = 0;
        ch[root][1] = 0;
        tag[root] = 0;
        return root;
    }

    static void init(){
        tot = 0;
        ch[0][0] =0;
        ch[0][1] = 0;
        tag[0] = 0;
    }

    static void ins(int x){
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int c = (x >> i) & 1;
            if (ch[p][c] == 0) ch[p][c] = newNode();
            p = ch[p][c];
            tag[p]++;
        }
    }

    static void del(int x){
        int p = 0;
        for(int i = 30; i >= 0; i--){
            int c = (x >> i) & 1;
            p = ch[p][c];
            tag[p]--;
        }
    }

    static int query(int x){
        int res = 0;
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int c = (x >> i) & 1;
            if (tag[ch[p][c ^ 1]] != 0){
                res |= (1 << i);
                p = ch[p][c ^ 1];
            }else {
                p = ch[p][c];
            }
        }
        return res;
    }


    static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));
    static Input f = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String str = null;
            try {
                str = reader.readLine();
            } catch (IOException e) {
                // TODO 自动生成的 catch 块
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}