自动搬运

查看原文

来自洛谷，原作者为

	sinestrea The Red Rose returned to health

搬运于2025-08-24 22:39:10，当前版本为作者最后更新于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：

$$( ((R_1-L_1+1) \times (R_2-L_2+1) + (R-L+1) \times (R_1-L_1+1) + (R-L+1) \times (R_2-L_2+1)) \bmod 2) $$

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

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

那么对于操作 2：

$$((R_2 - L_2 + 1) \times (R_1 - L_1 + 1) \bmod 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
}