//
// Created by 罗炳国 on 2023/7/22.
//

#ifndef PFJ_CODE11_MOSTXOR_H
#define PFJ_CODE11_MOSTXOR_H

#include "commonHeader.h"

/**
 * 数组中所有数都异或起来的结果，叫做异或和。给定一个数组arr，可以任意切分成若干个不相交的子数组。
 * 其中一定存在一种最优方案，使得切出异或和为0的子数组最多，返回这个最多数量。
 * */

class code11_mostXor {
public:
    // 待被验证的方法
    int mostXor(vector<int> &nums) {
        int N = nums.size();
        vector<int> dp(N, 0);

        int tmpxor = nums[0];
        // 异或前缀和及最后一次出现的索引
        unordered_map<int, int> xorIndex;
        xorIndex[0] = -1;
        xorIndex[nums[0]] = 0;
        dp[0] = nums[0] == 0 ? 1 : 0;
        for (int i = 1; i < N; i++) {
            tmpxor ^= nums[i];
            auto iter = xorIndex.find(tmpxor);
            if (iter != xorIndex.end())
                dp[i] = iter->second == -1 ? 1 : (dp[iter->second] + 1);
            dp[i] = std::max(dp[i], dp[i - 1]);
            xorIndex[tmpxor] = i;
        }

        return dp[N - 1];
    }

    // 暴力对数器方法
    int mostXorRight(vector<int> &nums) {
        int ans = 0;
        // 前缀异或和，用来加速子数组异或和求取
        vector<int> eors;
        int eor = 0;
        for (auto &v : nums) {
            eor ^= v;
            eors.push_back(eor);
        }
        list<int> parts;
        ans = process(eors, 1, parts);
        return ans;
    }
    // 深度优先遍历
    // eor前缀异或和数组 index 决定 index - 1的位置要不要分段
    int process(vector<int> &eors, int index, std::list<int> &parts) {
        int ans = 0;
        // 到尾端了，收集答案
        if (index == eors.size()) {
            parts.push_back(index);
            ans = xorZeroParts(eors, parts);
            parts.pop_back(); //恢复现场
        } else {
            // index - 1 位置分段
            parts.push_back(index);
            int ans1 = process(eors, index + 1, parts);
            parts.pop_back(); // 恢复现场
            // index - 1位置不分段
            int ans2 = process(eors, index + 1, parts);
            ans = max(ans1, ans2);
        }
        return ans;
    }

    // parts 中的值代表 前一位分段了
    int xorZeroParts(vector<int> &eors, std::list<int> &parts) {
        int L = 0;
        int ans = 0;
        for (auto &v : parts) {
            // 要取到 L 到 v(不含v) 之间的异或和，L前前一位到v前一位，异或和异或
            if ((eors[v - 1] ^ (L == 0 ? 0 : eors[L - 1])) == 0)
                ans++;
            L =  v;
        }
        return ans;
    }

    void test() {
        vector<int> vec1 {1, 1, 2, 3, 0, 0, 0}; //答案是4
        int ans = mostXorRight(vec1);
        int ans2 = mostXor(vec1);
        std::cout << "ans: " << ans << " ans2: " << ans2 << std::endl;

        vector<int> vec2 {0, 0, 0, 0, 0}; // 答案是5
        ans  = mostXorRight(vec2);
        ans2 = mostXor(vec2);
        std::cout << "ans: " << ans << " ans2: " << ans2 << std::endl;

        vector<int> vec3 {1, 1, 3, 3, 2, 2}; // 答案是3
        ans  = mostXorRight(vec3);
        ans2 = mostXor(vec3);
        std::cout << "ans: " << ans << " ans2: " << ans2 << std::endl;

        vector<int> vec4 {4, 1, 1, 3, 3, 2, 2}; // 答案是0
        ans  = mostXorRight(vec4);
        ans2 = mostXor(vec4);
        std::cout << "ans: " << ans << " ans2: " << ans2 << std::endl;

        vector<int> vec5 {4, 1}; // 答案是0
        ans  = mostXorRight(vec5);
        ans2 = mostXor(vec5);
        std::cout << "ans: " << ans << " ans2: " << ans2 << std::endl;
    }

    void finalTest() {
        int testLoop = 50000;
        for (int i = 0; i < testLoop; i++) {
            vector<int> vec;
            int ilen = getRand(1, 15);
            getRandomArray(vec, ilen);
            int ans1 = mostXorRight(vec);
            int ans2 = mostXorRight(vec);
            if (ans1 != ans2) {
                std::cout << "fucking fucked.err ans1:" << ans1 << " ans2:" << ans2 << endl;
                vecShow(vec);
                return;
            } else {
                if ((i + 1) % 100 == 0) {
                    std::cout << i + 1 <<"/" << testLoop << " passed." << endl;
                }
            }
        }
    }

};


#endif //PFJ_CODE11_MOSTXOR_H