[CF842D]Vitya and Strange Lesson 题解

[CF842D]Vitya and Strange Lesson 题解

题目地址:Codeforces:Problem – 842D – Codeforces、vjudge:Vitya and Strange Lesson – CodeForces 842D – Virtual Judge

题目描述

Today at the lesson Vitya learned a very interesting function — mex. Mex of a sequence of numbers is the minimum non-negative number that is not present in the sequence as element. For example, mex([4, 33, 0, 1, 1, 5]) = 2 and mex([1, 2, 3]) = 0.
Vitya quickly understood all tasks of the teacher, but can you do the same?
You are given an array consisting of n non-negative integers, and m queries. Each query is characterized by one number x and consists of the following consecutive steps:

  1. Perform the bitwise addition operation modulo 2 (xor) of each array element with the number x.
  2. Find mex of the resulting array.

Note that after each query the array changes.
给一个数列,每次查询给出一个值x,先对数列中每个元素异或上x,然后查询数列的mex值(即数列中不包含的最小非负整数)。

输入输出格式

输入格式:
First line contains two integer numbers n and m (1 ≤ n, m ≤ 3 \cdot 10^5) — number of elements in array and number of queries.
Next line contains n integer numbers ai (0 ≤ ai ≤ 3 \cdot 10^5) — elements of then array.
Each of next m lines contains query — one integer number x (0 ≤ x ≤ 3 \cdot 10^5).
输出格式:
For each query print the answer on a separate line.

输入输出样例

输入样例#1:

2 2
1 3
1
3

输出样例#1:

1
0

输入样例#2:

4 3
0 1 5 6
1
2
4

输出样例#2:

2
0
0

输入样例#3:

5 4
0 1 5 6 7
1
1
4
5

输出样例#3:

2
2
0
2

题解

冷静分析一下这题,发现异或操作是对整个数列的,这个直接在外面维护标记就行了,因为异或满足结合律。找mex是一个难点,需要用01Trie处理。
先把数列元素去个重插入01Trie中,预先算好发现数据最大是大约19位二进制,那就存20位算了,插入的同时统计一下每个子树中有多少数。每次查询的时候先把查询的这一位异或上,即如果要异或的数为1,则1当0处理,0当1处理。要异或的数为0时,选择0子树肯定是比较小的,但是要看一下这个子树有没有满,满了只能向1走,否则向0走,当然如果子树为空直接返回即可。每次走的时候维护一个结果,如果向1走要在结果的这一位上设成1。这个结果就是询问的答案。

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>

int trie[6000005][2], tot = 1, has[6000005];

inline void insert(int n) {
    int t = 1;
    for(int i = 20; i > 0; i--) {
        has[t]++;
        if(n & (1 << (i - 1))) {
            if(!trie[t][1]) trie[t][1] = ++tot;
            t = trie[t][1];
        } else {
            if(!trie[t][0]) trie[t][0] = ++tot;
            t = trie[t][0];
        }
    }
    has[t]++;
}

int dlt = 0;

inline int query() {
    int t = 1, res = 0;
    for(int i = 20; i > 0; i--) {
        if(dlt & (1 << (i - 1))) {
            if(!trie[t][1]) {
                return res;
            } else if(has[trie[t][1]] < (1 << (i - 1))) {
                t = trie[t][1];
            } else {
                t = trie[t][0];
                res += (1 << (i - 1));
            }
        } else {
            if(!trie[t][0]) {
                return res;
            } else if(has[trie[t][0]] < (1 << (i - 1))) {
                t = trie[t][0];
            } else {
                t = trie[t][1];
                res += (1 << (i - 1));
            }
        }
    }
    return res;
}

int n, m, a[300005], t;

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    std::sort(a, a + n);
    n = std::unique(a, a + n) - a;
    for(int i = 0; i < n; i++) {
        insert(a[i]);
    }
    for(int i = 0; i < m; i++) {
        scanf("%d", &t);
        dlt ^= t;
        printf("%d\n", query());
    }
    return 0;
}


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据