P8449

sinestrea · 2023-03-10 19:53:11 · 题解

我们应该如何求逆序对呢？那当然是——归...无旋 Treap！

对于每次插入一个新的数，新增的逆序对个数，就是左（或右）子树大小，那么我们在每一次插入新的节点时，返回左（或右）子树的大小就可以惹。

对于初始时输入的数据，每输入一个数字就插入到无旋 Treap 里，那么按值分裂后的两棵子树，左子树所有的值一定都小于这个值，右子树所有的值一定都大于这个值（题目保证在任意时刻 a 中的数均互不相同），那么返回右子树的值就可以惹。

那么，对于操作 3 和操作 4，就是返回左右子树大小就好惹。

对于操作 1 和操作 2，我们可以看到，如果我们假设把一个数向一个方向移动，那么逆序对数量一定是增加 1 或减少 1，所以奇偶性只和移动次数和移动距离多少有关，我们定义左区间为 [L_1,R_1]，右区间为 [L_2,R_2]，那么两个区间中间的区间就为 [R_1 + 1,L_2 - 1]，将其定义为 [L,R]；

那么对于操作 1：

的值如果为 1，那么奇偶性改变，反之则不改变；

对于操作 2, 我们可以看到可以将其转化为操作 1，将第二个区间 [R_1 + 1,K] 定义为 [L_2, R_2]；

那么对于操作 2：

的值如果为 1，那么奇偶性改变，反之则不改变；

代码：

#include <bits/stdc++.h>

const int MAX = 5e5 + 5;

std::mt19937 GetRand(233);
// 生成伪随机数;

class CNode
{
public:
    int Data{}, Rand{}, Size{}, L{}, R{};
    // Data:数据项;
    // Rand:随机值;
    // Size:子树大小;
    // L:左子结点;
    // R:右子节点;
} Node[MAX];

class Treap
{
private:
    int Root{}, RootX{}, RootY{}, RootZ{}, Cnt{};
    // Root:根节点;
    // RootX ~ RootZ:以后要用到的暂存根节点;
    // Cnt:计数器（数组下标）;
public:
    inline int NewNode(int Data)
    {
        Node[++Cnt].Data = Data;
        Node[Cnt].Rand = GetRand();
        Node[Cnt].Size = 1;
        return Cnt;
    }
    // 新建节点

    inline void Update(int Now)
    {
        Node[Now].Size = Node[Node[Now].L].Size + Node[Node[Now].R].Size + 1;
    }
    // 更新节点左右子树大小;

    void Split(int Now, int Data, int &X, int &Y)
    {
        if (!Now)
        {
            X = Y = 0;
            return;
        }
        else if (Node[Now].Data <= Data)
        {
            X = Now;
            Split(Node[Now].R, Data, Node[Now].R, Y);
        }
        else
        {
            Y = Now;
            Split(Node[Now].L, Data, X, Node[Now].L);
        }
        Update(Now);
    }
    // 按值分裂，将"Now"节点，按照"Data"分裂成左子树"X"和右子树"Y";

    int Merge(int X, int Y)
    {
        if (!X || !Y)
            return X | Y;
        else if (Node[X].Rand <= Node[Y].Rand)
        {
            Node[X].R = Merge(Node[X].R, Y);
            Update(X);
            return X;
        }
        else
        {
            Node[Y].L = Merge(X, Node[Y].L);
            Update(Y);
            return Y;
        }
    }
    // 合并两棵树"X"和"Y";

    inline int Insert(int Data, bool Opt)
    {
        // Opt:操作;
        Split(Root, Data, RootX, RootY);
        int Ret{};
        if (Opt == 0)
            Ret = Node[RootY].Size;
        else if (Opt == 1)
            Ret = Node[RootX].Size;
        Root = Merge(Merge(RootX, NewNode(Data)), RootY);
        return Ret;
        // 如果输入为0，返回右子树大小，如果输入为1，返回右子树大小;
    }
    // 插入;
} Treap;

int N, M, Num, Opt, L1, L2, R1, R2, L, R, K;

bool Ans;

unsigned long long Test;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\Guozhi\\CIO\\IN", "r", stdin);
    freopen("C:\\Users\\Guozhi\\CIO\\OUT", "w", stdout);
#endif
    // BEGIN
    std::cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        std::cin >> Num;
        if (Treap.Insert(Num, 0) % 2)
            Ans ^= 1;
    }

    for (int i = 1; i <= M; i++)
    {
        std::cin >> Opt;
        if (Opt == 1)
        {
            std::cin >> L1 >> R1 >> L2 >> R2;
            L = R1 + 1;
            R = L2 - 1;
            if ((((R1 - L1 + 1) * (R2 - L2 + 1) + (R - L + 1) * (R1 - L1 + 1) + (R - L + 1) * (R2 - L2 + 1)) % 2))
                Ans ^= 1;
            if (Ans)
                std::cout << "odd" << std::endl;
            else
                std::cout << "even" << std::endl;
        }
        else if (Opt == 2)
        {
            std::cin >> L1 >> R1 >> K;
            L2 = R1 + 1;
            R2 = K;
            if (((R2 - L2 + 1) * (R1 - L1 + 1)) % 2)
                Ans ^= 1;
            if (Ans)
                std::cout << "odd" << std::endl;
            else
                std::cout << "even" << std::endl;
        }
        else if (Opt == 3)
        {
            std::cin >> Num;
            if (Treap.Insert(Num, 0) % 2)
                Ans ^= 1;
            if (Ans)
                std::cout << "odd" << std::endl;
            else
                std::cout << "even" << std::endl;
        }
        else if (Opt == 4)
        {
            std::cin >> Num;
            if (Treap.Insert(Num, 1) % 2)
                Ans ^= 1;
            if (Ans)
                std::cout << "odd" << std::endl;
            else
                std::cout << "even" << std::endl;
        }
    }
    // END
}