Korney Korneevich and XOR (hard version) (Codeforces 1582F2)
Tags: Greedy, two pointers

This is a harder version of the problem with bigger constraints.Korney Korneevich dag up an array $$$a$$$ of length $$$n$$$. Korney Korneevich has recently read about the operation bitwise XOR, so he wished to experiment with it. For this purpose, he decided to find all integers $$$x \ge 0$$$ such that there exists an increasing subsequence of the array $$$a$$$, in which the bitwise XOR of numbers is equal to $$$x$$$.It didn't take a long time for Korney Korneevich to find all such $$$x$$$, and he wants to check his result. That's why he asked you to solve this problem!A sequence $$$s$$$ is a subsequence of a sequence $$$b$$$ if $$$s$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.A sequence $$$s_1, s_2, \ldots , s_m$$$ is called increasing if $$$s_1 < s_2 < \ldots < s_m$$$.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 5000$$$) — the elements of the array $$$a$$$.

Output: In the first line print a single integer $$$k$$$ — the number of found $$$x$$$ values.In the second line print $$$k$$$ integers in increasing order $$$x_1, x_2, \ldots x_k$$$ ($$$0 \le x_1 < \ldots < x_k$$$) — found $$$x$$$ values.

Note: In the first test case:  To get value $$$x = 0$$$ it is possible to choose and empty subsequence  To get value $$$x = 2$$$ it is possible to choose a subsequence $$$[2]$$$  To get value $$$x = 4$$$ it is possible to choose a subsequence $$$[4]$$$  To get value $$$x = 6$$$ it is possible to choose a subsequence $$$[2, 4]$$$ 

Sample Inputs:
4
4 2 2 4

8
1 0 1 7 12 5 3 2

Sample Outputs:
4
0 2 4 6

12
0 1 2 3 4 5 6 7 10 11 12 13

Solution (Python):
import sys, math
MAX = 1 << 13
z = int(input())
d = [MAX] * MAX
d[0] = 0
flag = [0] * (MAX + 1)
for _ in input().split():
    a = int(_)
    if flag[a]:
        continue
    flag[a] = 1
    for i in range(MAX):
        if d[i] < a:
            if d[i ^ a] > a:
                for j in range(a + 1, d[i ^ a] + 1):
                    flag[j] = 0
                d[i ^ a] = a
r = [str(i) for i in range(MAX) if d[i] < MAX]
print(len(r))
print(' '.join(r))

Solution (Python):
MAX = 1 << 13
n = int(input())
d = [MAX] * MAX
d[0] = 0
flag = [0] * (MAX + 1)
for _ in input().split():
    a = int(_)
    if flag[a]:
        continue
    flag[a] = 1
    for i in range(MAX):
        if d[i] < a:
            if d[i ^ a] > a:
                for j in range(a + 1, d[i ^ a] + 1):
                    flag[j] = 0
                d[i ^ a] = a
r = [str(i) for i in range(MAX) if d[i] < MAX]
print(len(r))
print(' '.join(r))

Solution (Python):
MAX = 1 << 13
n = int(input())
d = [MAX] * MAX
d[0] = 0
flag = [0] * (MAX + 1)
for _ in input().split():
    a = int(_)
    if flag[a]:
        continue
    flag[a] = 1
    for i in range(MAX):
        if d[i] < a:
            if d[i ^ a] > a:
                for j in range(a + 1, d[i ^ a] + 1):
                    flag[j] = 0
                d[i ^ a] = a
r = [str(i) for i in range(MAX) if d[i] < MAX]
print(len(r))
print(' '.join(r))