Sprague-Grundy numbers#11794

Sprague-Grundy numbers (Editorial)

Problem Author:	Illia Shevchenko
Prepared by:	Illia Shevchenko
Editorial by:	Illia Shevchenko

We reformulate the problem to choose a set of non-overlapping subsegments such that the $m e x$ of their $x or$ is maximized.

According to the problem statement, there are no 3 subsegments with the same $x or$ .

We will perform a binary search on the answer. For the current $mi d$ value, we need to check if we can choose subsegments such that the $m e x$ of their $x or$ is equal to $mi d$ .

To check this in $O (n^{2})$ O(n^2):

We can eliminate all subsegments with $x or$ less than $mi d$ .

Then there are several conditions: any two segments $a$ and $b$ that intersect have 2SAT condtion: $! a$ or $! b$ .

For $2$ segments $a$ and $b$ with the same $x or$ , we have that condition: $a$ or $b$ .

If it is only one segment with such $x or$ , we simply need to choose this subsegment.

All of this can be done using $2 - S A T$ 2-SAT.

To check in $O (n lo g n)$ O(n \log n):

We can note that the answer is always less than $n + 1$ n + 1.

Then we can eliminate subsegments with $x or$ less than $n + 1$ n + 1 using prefix $x or$ and a trie for the minimum $x or$ .

The total number of subsegments will be $O (n)$ .

Now we want to build a similar graph as in the first solution.

It will have 2 types of edges: Edges between subsegments with the same $x or$ can simply be added to the graph because their maximum is $n$ .

To add edges of the first type (to ensure subsegments do not intersect):

For this, we will build a Segment Tree, where each subsegment corresponds to a set of vertices in the segment tree. If 2 subsegments intersect, there will exist 2 vertices such that the first is in the decomposition of the first subsegment, and the second is in the decomposition of the second subsegment, and one is an ancestor of the other (or they may coincide).

Consider 2 cases: 1) They coincide.

Let's maintain a set of subsegments for each vertex in the Segment Tree that contains this vertex.

Then we need to ensure that at most one subsegment is chosen from this set.

Let this set be $v er [0... m]$ .

Then we add new vertices to the graph such that: vertex $p r e f [i] = v er [0] ∣ v er [1] ∣...∣ v er [i]$ pref[i] = ver[0] | ver[1] | ... | ver[i]. ( $p r e f [i]$ pref[i] is a prefix OR of variables)

Then we effectively have the condition $(! p r e f [i]$ (!pref[i] or $! v er [i + 1])$ !ver[i+1]).

2) These 2 vertices do not coincide.

Then for each vertex in the Segment Tree, we can simply maintain a vertex equal to the $or$ of all subsegments located inside (let's say for vertex $i$ , this vertex will be $a l l [i]$ all[i]).

Then we will have the conditions $(! a l l [in d$ (!all[ind_ $l e f t$ _ $so n [i]]$ or $! p r e f [m])$ !pref[m]) and $(! a l l [in d$ (!all[ind_ $r i g h t$ _ $so n [i]]$ or $! p r e f [m])$ !pref[m]), where $in d$ _ $l e f t$ _ $so n [i]$ , $in d$ _ $r i g h t$ _ $so n [i]$ are the indices of the left and right children.

The solution works in $O (n lo g^{2} n)$ O(n \log^2 n) and uses $O (n lo g n)$ O(n \log n) memory.

//#pragma gcc optimize "Ofast"
 
///In honor of TimDee
 
/*
In honor of Anton Tsypko
I want earrings with minecreaft
I want earrings with birbie
*/
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <string>
#include <queue>
#include <random>
#include <chrono>
 
 
using namespace std;
 
#define int long long
 
int inf = 10000000000000000ll;
int NADIYA = 40;
int mod = 1000000007;
int log_ = 60;
 
 
 
struct sat
{
 
 
    vector <vector <int>> g;
    vector <vector <int>> gr;
 
 
    void add_edge(int u, int v)
    {
        g[u].push_back(v);
 
 
        gr[v].push_back(u);
    }
 
    vector <int> o;
 
    vector <bool> t;
 
    void dfs(int ind)
    {
        t[ind] = true;
 
        for (int i = 0; i < g[ind].size(); i++)
        {
            int ind_s = g[ind][i];
 
 
            if (t[ind_s] == true)
                continue;
 
            dfs(ind_s);
        }
 
        o.push_back(ind);
    }
 
    vector <int> color;
    int c = 0;
    void dfs_2(int ind)
    {
        t[ind] = true;
 
        for (int i = 0; i < gr[ind].size(); i++)
        {
            int ind_s = gr[ind][i];
 
            if (t[ind_s] == true)
                continue;
 
            dfs_2(ind_s);
        }
 
        color[ind] = c;
    }
 
    void com_build()
    {
        int n = g.size();
        for (int i = 0; i < n; i++)
        {
            if (t[i] == false)
                dfs(i);
        }
        t.assign(o.size(), false);
        for (int i = o.size() - 1; i >= 0; i--)
        {
            if (t[o[i]] == false)
            {
                dfs_2(o[i]);
                c++;
            }
        }
    }
 
    void build(int n)
    {
        g.resize(2 * n);
        gr.resize(2 * n);
        color.resize(2 * n);
        t.resize(2 * n);
    }
 
    int co_()
    {
        com_build();
 
        int n = g.size();
 
        n /= 2;
        for (int i = 0; i < n; i++)
        {
            if (color[i * 2] == color[i * 2 + 1])
                return -1;
        }
 
        return 1;
    }
};
 
int ver_pl(int x)
{
    return x * 2;
}
 
int ver_op(int x)
{
    return x * 2+1;
}
 
 
struct bor
{
    vector <int> ind_l;
    vector <int> ind_r;
    vector <int> col;
    int f = 0;
 
    void init(int n)
    {
        f = 1;
 
        ind_l.resize(n, -1);
        ind_r.resize(n, -1);
        col.resize(n, 0);
    }
 
    void add(int x , int c)
    {
        int ind = 0;
        for (int i = log_ - 1; i >= 0; i--)
        {
            if ((x & (1ll << i)) == 0)
            {
                if (ind_l[ind] == -1)
                {
                    ind_l[ind] = f;
                    f++;
                }
 
                ind = ind_l[ind];
            }
            else
            {
                if (ind_r[ind] == -1)
                {
                    ind_r[ind] = f;
                    f++;
                }
 
                ind = ind_r[ind];
            }
 
            col[ind]+= c;
        }
    }
 
 
    int mn_xor(int x)
    {
        int ind = 0;
 
        int ans = 0;
        for (int i = log_ - 1; i >= 0; i--)
        {
            if ((x & (1ll << i)) == 0)
            {
                if ((ind_l[ind] == -1) or (col[ind_l[ind]] == 0))
                {
                    ind = ind_r[ind];
                    ans += (1ll << i);
                }
                else
                {
                    ind = ind_l[ind];
                }
            }
            else
            {
                if ((ind_r[ind] == -1) or (col[ind_r[ind]] == 0))
                {
                    ind = ind_l[ind];
                }
                else
                {
                    ans += (1ll << i);
                    ind = ind_r[ind];
                }
            }
 
        }
 
        return ans;
    }
 
};
 
 
vector <vector <int>> tree;
int sz = 0;
 
void modif(int ind, int l, int r, int lx, int rx, int x)
{
    if ((r <= lx) or (rx <= l))
        return;
 
    if ((lx <= l) and (r <= rx))
    {
        tree[ind].push_back(x);
        return;
    }
 
    int m = (l + r) / 2;
 
    modif(ind * 2 + 1, l, m, lx, rx, x);
    modif(ind * 2 + 2, m, r, lx, rx, x);
}
 
void init(int n)
{
    sz = 1;
 
    while (sz < n)
        sz *= 2;
 
    tree.clear();
    tree.resize(2 * sz);
}
 
signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
 
	int n;
	cin >> n;
 
 
	vector <int> a(n);
 
	for (int i = 0; i < n; i++)
		cin >> a[i];
 
    map<int, vector <int>> mp;
    mp[0].push_back(-1);
 
    vector <vector <pair <int , int>>> vp(n+10);
 
    bor b;
    b.init(log_ * n+100);
 
    b.add(0, 1);
    int c = 1;
 
    int p = 0;
    for (int i = 0; i < n; i++)
    {
        p ^= a[i];
 
        int col = 0;
 
        vector <int> x;
        while ((i+1) - col >= 1)
        {
            int y = b.mn_xor(p);
            if ((p ^ y) < n)
            {
                x.push_back(y);
 
                for (auto j : mp[y])
                    vp[p ^ y].push_back({ j + 1 , i });
 
                int C = mp[y].size();
                b.add(y , -C);
 
 
                col+= C;
            }
            else
                break;
 
 
        }
 
        for (int j = 0; j < x.size(); j++)
        {
            b.add(x[j], mp[x[j]].size());
        }
 
        b.add(p, 1);
        mp[p].push_back(i);
    }
 
 
    int lx = 0;
    int rx = n+2;
 
    while (rx - lx > 1)
    {
        int mid = (lx + rx) / 2;
 
        init(n);
        
        int f = 0;
 
        bool FF = true;
 
        sat s;
        s.build(5*n+100);
 
        for (int i = 0; i < mid; i++)
        {
            for (int j = 0; j < vp[i].size(); j++)
            {
                int l = vp[i][j].first;
                int r = vp[i][j].second;
 
 
                modif(0, 0, sz, l, r+1, f);
 
                f++;
            }
 
            if (vp[i].size() == 0)
            {
                FF = false;
                break;
            }
 
            if (vp[i].size() == 1)
            {
                s.add_edge(ver_op(f - 1), ver_pl(f - 1));
            }
 
            if (vp[i].size() == 2)
            {
                s.add_edge(ver_op(f - 1), ver_pl(f - 2));
                s.add_edge(ver_op(f - 2), ver_pl(f - 1));
            }
        }
 
 
        if (FF == false)
        {
            rx = mid;
            continue;
        }
 
        vector <int> ver(2 * sz);
        for (int i = 2 * sz - 2; i >= 0; i--)
        {
            for (int j = 0; j < tree[i].size(); j++)
            {
                if ((i * 2 + 1) <= 2 * sz - 2)
                {
                    s.add_edge(ver_pl(ver[i * 2 + 1]), ver_op(tree[i][j]));
                    s.add_edge(ver_pl(tree[i][j]), ver_op(ver[i * 2 + 1]));
                }
 
                if ((i * 2 + 2) <= 2 * sz - 2)
                {
                    s.add_edge(ver_pl(ver[i * 2 + 2]), ver_op(tree[i][j]));
                    s.add_edge(ver_pl(tree[i][j]), ver_op(ver[i * 2 + 2]));
                }
            }
 
            ver[i] = f;
            f++;
 
            if (i * 2 + 2 <= (2 * sz - 2))
            {
                s.add_edge(ver_pl(ver[i * 2 + 1]), ver_pl(ver[i]));
                s.add_edge(ver_pl(ver[i * 2 + 2]), ver_pl(ver[i]));
 
 
                s.add_edge(ver_op(ver[i]) , ver_op(ver[i * 2 + 1]));
                s.add_edge(ver_op(ver[i]), ver_op(ver[i * 2 + 2]));
            }
 
            for (int j = 0; j < tree[i].size(); j++)
            {
                s.add_edge(ver_pl(tree[i][j]), ver_pl(ver[i]));
                s.add_edge(ver_op(ver[i]) , ver_op(tree[i][j]));
            }
 
            if (tree[i].size() >= 2)
            {
                int c = tree[i][0];
 
                for (int j = 1; j < tree[i].size(); j++)
                {
                    s.add_edge(ver_pl(c), ver_op(tree[i][j]));
                    s.add_edge(ver_pl(tree[i][j]), ver_op(c));
 
 
 
                    s.add_edge(ver_pl(c), ver_pl(f));
                    s.add_edge(ver_pl(tree[i][j]), ver_pl(f));
                    
                    s.add_edge(ver_op(f) , ver_op(c));
                    s.add_edge(ver_op(f) , ver_op(tree[i][j]));
 
                    c = f;
                    f++;
                }
            }
        }
 
 
        if (s.co_() == 1)
            lx = mid;
        else
            rx = mid;
    }
 
    cout << lx;
}

C++