【洛谷P5105】不强制在线的动态快速排序【线段树】

题目大意：

题目链接：https://www.luogu.org/problem/P5105
维护两个操作：

• $1 l r$，在序列中插入$[l,r]$中的所有整数
• $2$，将序列排序后输出$⨁^{len}_{i=2}a[i]^2-a[i-1]^2$

---

思路：

这道题中虽然允许元素的重复，但是显然重复的元素对答案的贡献为0。所以我们可以不用考虑元素重复的情况。
又由于每次加入的元素是一个连续的区间，所以我们可以考虑维护一棵权值线段树。那么每次询问就把这个区间打上$lazy$标记。
那么如何计算这个区间的贡献呢？我们可以利用这个区间连续的特性。因为$x^2-(x-1)^2=(x-x+1)(x+x-1)=2x-1$必然是奇数，所以我们就是要求若干连续奇数的异或和。
打表就不难发现，从1开始，每四个连续的奇数亦或起来为0。所以这样就可以快速算出前缀异或和。

ll xorsum(ll x)  //1 xor 3 xor ... xor x
{
    int k=(x/2+1)%4;  //计算出这是第几个奇数
    if (k==0) return 0;
    if (k==1) return x;
	if (k==2) return x^(x-2);
	if (k==3) return x^(x-2)^(x-4);
}

然后区间合并的时候将这两个区间的最值用$a[i]^2-a[i-1]^2$求出来异或进去即可。
线段树要动态开点。
时间复杂度$O(nlog n)$

---

代码：

#include <cstdio>
using namespace std;
typedef long long ll;

const int N=300010;
int T,opt,tot,root,l,r;

struct Treenode
{
	ll ans,maxn,minn;
	int lc,rc;
	bool lazy;
};

ll xorsum(ll x)
{
    int k=(x/2+1)%4;
    if (k==0) return 0;
    if (k==1) return x;
	if (k==2) return x^(x-2);
	if (k==3) return x^(x-2)^(x-4);
}

struct Tree
{
	Treenode tree[N*64];
	
	void update(int x)
	{
		tree[x].ans=tree[tree[x].lc].ans^tree[tree[x].rc].ans;
		if (tree[x].lc && tree[x].rc)
			tree[x].ans^=tree[tree[x].rc].minn*tree[tree[x].rc].minn-tree[tree[x].lc].maxn*tree[tree[x].lc].maxn;
		if (tree[x].lc)	tree[x].minn=tree[tree[x].lc].minn;
			else tree[x].minn=tree[tree[x].rc].minn;
		if (tree[x].rc)	tree[x].maxn=tree[tree[x].rc].maxn;
			else tree[x].maxn=tree[tree[x].lc].maxn;
	}
	
	void pushdown(int x,int l,int r)
	{
		if (tree[x].lazy)
		{
			if (!tree[x].lc) tree[x].lc=++tot;
			if (!tree[x].rc) tree[x].rc=++tot;
			tree[tree[x].lc].lazy=tree[tree[x].rc].lazy=1;
			tree[x].lazy=0;
			int mid=(l+r)>>1;
			tree[tree[x].lc].minn=l; tree[tree[x].lc].maxn=mid;
			tree[tree[x].rc].minn=mid+1; tree[tree[x].rc].maxn=r;
			tree[tree[x].lc].ans=xorsum(tree[tree[x].lc].maxn*2-1)^xorsum(tree[tree[x].lc].minn*2-1);
			tree[tree[x].rc].ans=xorsum(tree[tree[x].rc].maxn*2-1)^xorsum(tree[tree[x].rc].minn*2-1);
		}
	}
	
	void insert(int &x,int nowl,int nowr,int l,int r)
	{
		if (l>r) return;
		if (!x) x=++tot;
		if (nowl==l && nowr==r)
		{
			tree[x].ans=xorsum(r+r-1)^xorsum(l+l-1);
			tree[x].maxn=r; tree[x].minn=l;
			tree[x].lazy=1;
			return;
		}
		pushdown(x,nowl,nowr);
		int mid=(nowl+nowr)>>1;
		if (r<=mid) insert(tree[x].lc,nowl,mid,l,r);
		else if (l>mid) insert(tree[x].rc,mid+1,nowr,l,r);
		else insert(tree[x].lc,nowl,mid,l,mid),insert(tree[x].rc,mid+1,nowr,mid+1,r);
		update(x);
	}
}t;

int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&opt);
		if (opt==1)
		{
			scanf("%d%d",&l,&r);
			t.insert(root,1,1e9,l,r);
		}
		else printf("%lld
",t.tree[1].ans);
	}
	return 0;
}