[洛谷P5105]不强制在线的动态快速排序

题目大意：有一个可重集$S$，有两个操作：

1. $1\;l\;r：$表示把$S$变为$S\cup[l,r]$
2. $2：$表示将$S$从小到大排序，记为$a_1,a_2,\dots,a_n$，然后求出$\bigoplus\limits_{i=2}^n(a_i^2-a_{i-1}^2)$，$\bigoplus$表示异或

题解：假设$a_1,a_2,\dots,a_n=[l,l+n)$，发现$\bigoplus\limits_{i=2}^n(a_i^2-a_{i-1}^2)=(2l+1)\oplus(2l+3)\oplus\dots\oplus(2l+2n-1)$，然后这玩意儿肯定可以打表找规律什么的$O(1)$求。

题目转化为如何维护这东西，发现这个集合重复不重复没有关系（写一下式子就知道了），可以动态开点线段树，把整个区间都被覆盖的节点打个标记，处理一下两个区间交接的地方就好了

卡点：无

C++ Code：

#include <algorithm>

#include <cstdio>

#include <cctype>

namespace __IO {

	namespace R {

		int x, ch;

		inline int read() {

			while (isspace(ch = getchar())) ;

			for (x = ch & 15; isdigit(ch = getchar()); ) x = x * 10 + (ch & 15);

			return x;

		}

	}

}

using __IO::R::read;

#define maxn 300010

inline int calc(const int x) {

	switch (x & 3) {

		case 0: return 1;

		case 1: return x - 1 << 1;

		case 2: return 3;

		case 3: return x << 1;

	}

	return 20040826;

}

inline long long sqr(const int x) { return static_cast<long long> (x) * x; }

namespace SgT {

#define N (maxn * 19)

	const int maxl = 1, maxr = 1e9;

	long long V[N];

	bool tg[N];

	int lc[N], rc[N], Lp[N], Rp[N];

	int root, idx;

	int L, R;

	void __modify(int &rt, const int l, const int r) {

		if (!rt) rt = ++idx;

		if (tg[rt]) return ;

		if (L <= l && R >= r) {

			Lp[rt] = l, Rp[rt] = r, tg[rt] = true;

			V[rt] = calc(r) ^ calc(l);

			return ;

		}

		const int mid = l + r >> 1;

		if (L <= mid) __modify(lc[rt], l, mid);

		if (R > mid) __modify(rc[rt], mid + 1, r);

		const int lc = SgT::lc[rt], rc = SgT::rc[rt];

		Lp[rt] = Lp[lc] ? Lp[lc] : Lp[rc];

		Rp[rt] = Rp[rc] ? Rp[rc] : Rp[lc];

		if (Rp[lc] && Lp[rc]) V[rt] = V[lc] ^ V[rc] ^ (sqr(Lp[rc]) - sqr(Rp[lc]));

		else V[rt] = V[lc] | V[rc];

		if (tg[lc] && tg[rc]) tg[rt] = true;

	}

	void modify(const int __L, const int __R) {

		L = __L, R = __R;

		__modify(root, maxl, maxr);

	}

#undef N

}

int main() {

	for (int n = read(); n; --n) {

		int op = read();

		if (op == 1) {

			static int l, r;

			l = read(), r = read();

			SgT::modify(l, r);

		} else printf("%lld\n", SgT::V[SgT::root]);

	}

	return 0;

}