CF #365 703D. Mishka and Interesting sum

题目描述

D. Mishka and Interesting sum的意思就是给出一个数组，以及若干询问，每次询问某个区间[L, R]之间所有出现过偶数次的数字的异或和。

这个东西乍看很像是经典问题，一列数字中所有数字出现偶数次，除了一个数字只出现一次，找出那个只出现过一次的数字。然而这个问题并不是要找出现奇数次数字的异或和。

算法

有一个直观的思路是求出[L, R的异或和，再异或上[L, R]之间所有出现过的数字的异或和。这样的话就可以使得数字出现次数的奇偶性发生变化。

那么怎么求出区间[L, R]所有出现过的数字的异或和呢？

先想一下如果是求区间[L, R]有多少种不同的数字怎么做？这个可以在遍历的时候保存每个数字最后出现的位置，打标记（去掉上一次的标记，更新到当前位置），去数[L, R]有多少个标记就行了。

所以求[L, R]不同数字的异或和也是类似的做法，去掉之前出现位置的标记，给当前位置打上标记，去计算[L,R]所有标记异或和。

回到原问题，有了区间不同数字的异或和，再异或上区间本身的异或值，就可以实现奇偶性翻转来得出出现偶数次的数字的异或和。

具体的流程：

需要一个异或BIT/FenwickTree，以及一个hashmap来保存元素出现位置。

按照所有询问的right值排序，遍历所有数字，每一次遍历到当前要处理的询问的R值为止。

每一步都要先往BIT中i位置加一个a[i]（要做区间本身数字的异或）。

如果当前数字是第一次出现，则向BIT中i位置加一个a[i]，hashmap中标记a[i]出现的位置为i。

如果当前数字之前已经出现过了，先去除上一次的标记，即向BIT中last[a[i]]加一个a[i]（对于异或来说就抵消了），再向当前位置i加入一个a[i]，更新hashmap中a[i]的位置为i。

可以发现，无论数字是否是第一次出现，最终hashmap中都得要给i这个位置加一个a[i]，和上述每一个位置都要插入a[i]正好就抵消效果了。

所以流程可以简化为：每一步判断hashmap中是否存在a[i]，存在的话取出位置值，BIT中往这个位置加a[i]。 在hashmap中插入<a[i], i>。

每一个询问的答案就是bit.query(R)^bit.query(L-1)

实现

public class Main {

    public static void main(String[] args) {

        InputStream inputStream = System.in;

        OutputStream outputStream = System.out;

        InputReader in = new InputReader(inputStream);

        PrintWriter out = new PrintWriter(outputStream);

        TaskD solver = new TaskD();

        solver.solve(1, in, out);

        out.close();

    }

    static class TaskD {

        public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();

            long[] a = new long[n + 1];

            for (int i = 1; i <= n; i++) {

                a[i] = in.nextLong();

            }

            int m = in.nextInt();

            Query[] queries = new Query[m];

            for (int i = 0; i < m; i++) {

                queries[i] = new Query(i, in.nextInt(), in.nextInt());

            }

            Arrays.sort(queries, (o1, o2) -> Integer.compare(o1.right, o2.right));

            Map<Long, Integer> pos = new HashMap<>();

            FenwickTree tree = new FenwickTree(n) {

                @Override

                protected long operate(long data, long value) {

                    return data ^ value;

                }

                @Override

                public long sum(int s, int t) {

                    return sum(t) ^ sum(s - 1);

                }

            };

            int i = 1;

            long[] result = new long[m];

            for (Query query : queries) {

                for (; i <= query.right; i++) {

                    if (pos.containsKey(a[i])) {

                        tree.add(pos.get(a[i]), a[i]);

                    }

                    pos.put(a[i], i);

                }

                result[query.id] = tree.sum(query.left, query.right);

            }

            for (long ret : result) {

                out.println(ret);

            }

        }

        class Query {

            int id;

            int left;

            int right;

            public Query(int id, int left, int right) {

                this.id = id;

                this.left = left;

                this.right = right;

            }

        }

    }

    static class InputReader {

        private final BufferedReader reader;

        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {

            reader = new BufferedReader(new InputStreamReader(stream));

            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 int nextInt() {

            return Integer.parseInt(next());

        }

        public long nextLong() {

            return Long.parseLong(next());

        }

    }

    static class FenwickTree {

        private final long[] data;

        public FenwickTree(int size) {

            data = new long[size + 1];

        }

        public FenwickTree(long[] data) {

            this.data = data;

        }

        private int lowBit(int x) {

            return x & -x;

        }

        protected long operate(long data, long value) {

            return data + value;

        }

        public final void add(int p, long v) {

            for (int i = p; i < data.length; i += lowBit(i)) {

                data[i] = operate(data[i], v);

            }

        }

        public final long sum(int p) {

            long ret = 0;

            for (int i = p; i > 0; i -= lowBit(i)) {

                ret = operate(ret, data[i]);

            }

            return ret;

        }

        public long sum(int s, int t) {

            return sum(t) - sum(s - 1);

        }

    }

}