Description：

给一个序列，支持删除一个元素，询问所有没被删除的元素构成的极长连续段的逆序对个数的异或和。

$1\leqslant n\leqslant 10^5,1\leqslant q\leqslant 20000$

Solution：

首先我们用一个树状数组套主席树，这样我们就可以支持单点修改，区间查询在某个值域内的数的个数，然后我们用一个 $set$ 来维护所有的区间，每次删除元素时，就把这个元素所在的区间拿出来，分裂成两个区间，每个区间再用一个值域线段树来维护所有的数字，然后区间分裂时，暴力扫描较小的区间，从另一个区间里消除这些数的影响，然后再暴力扫描较小的区间构造这个区间的值域线段树，复杂度 $O(n\log^2n)$ ，因为可以看成启发式合并倒过来，也可以看成是分治。

Code：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n,q;

#define MAXN 150010

int a[MAXN];

#define N 1000000000

#define RE register

inline ll rd()

{

	register ll res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

namespace ST{

	struct node

	{

		int lc,rc;

		int sum;

		node(){lc = rc = sum = 0;}

	}t[MAXN * 400];

	int ptr = 0;

	int del[MAXN * 150],del_ptr = 0;

	int newnode()

	{

		int k;

		if(del_ptr)k = del[del_ptr--];

		else k = ++ptr;

		t[k].lc = t[k].rc = t[k].sum = 0;

		return k;

	}

	#define mid ((l + r) >> 1)

	void recycle(int &rt)

	{

		if(rt == 0)return;

		recycle(t[rt].lc);recycle(t[rt].rc);

		del[++del_ptr] = rt;

		rt = 0;

		return;

	}

	void add(int &rt,int p,int k,int l,int r)

	{

		if(rt == 0)rt = newnode();

		t[rt].sum += k;

		//if(t[rt].sum == 0){recycle(rt);return;}

		if(l == r)return;

		if(p <= mid)add(t[rt].lc,p,k,l,mid);

		else add(t[rt].rc,p,k,mid + 1,r);

		return;

	}

	int query(int rt,int L,int R,int l,int r)

	{

		if(L > R)return 0;

		if(rt == 0)return 0;

		if(L <= l && r <= R)return t[rt].sum;

		int res = 0;

		if(L <= mid)res += query(t[rt].lc,L,R,l,mid);

		if(R > mid)res += query(t[rt].rc,L,R,mid + 1,r);

		return res;

	}

}

namespace solve1

{

	int root[MAXN];

	int lowbit(int x){return x & (-x);}

	void add(int p,int x,int v)

	{

		for(int i = p;i <= n;i += lowbit(i))ST::add(root[i],x,v,0,N);

		return;

	}

	ll query(int p,int l,int r)

	{

		ll res = 0;

		for(int i = p;i >= 1;i -= lowbit(i))res += ST::query(root[i],l,r,0,N);

		return res;

	}

	ll query(int L,int R,int l,int r)

	{

		if(L > R || l > r)return 0;

		return query(R,l,r) - query(L - 1,l,r);

	}

}

ll ans = 0;

struct par

{

	int l,r,id;

	ll res;

	bool operator < (const par &b)const{return r < b.r;}

}p[MAXN];

int root[MAXN];

int parnum = 0;

set<par> s;

void modify(int x,int y)

{

	set<par>::iterator it = s.lower_bound((par){x,x,0,0});

	RE int d = it -> id;s.erase(it);

	ans ^= p[d].res;

	p[d].res -= solve1::query(p[d].l,x - 1,a[x] + 1,N);

	p[d].res -= solve1::query(x + 1,p[d].r,0,a[x] - 1);

	solve1::add(x,a[x],-1);

	ST::add(root[d],a[x],-1,0,N);

	a[x] = y;

	ST::add(root[d],a[x],1,0,N);

	solve1::add(x,a[x],1);

	p[d].res += solve1::query(p[d].l,x - 1,a[x] + 1,N);

	p[d].res += solve1::query(x + 1,p[d].r,0,a[x] - 1);

	ans ^= p[d].res;

	s.insert(p[d]);

	return;

}

void split(int x)

{

	RE set<par>::iterator it = s.lower_bound((par){x,x,0,0});

	ans ^= it -> res;s.erase(it);

	int d = it -> id;

	p[d].res -= solve1::query(p[d].l,x - 1,a[x] + 1,N);

	p[d].res -= solve1::query(x + 1,p[d].r,0,a[x] - 1);

	ST::add(root[d],a[x],-1,0,N);

	if(x == it -> l && x == it -> r)return;

	else if(x == it -> l){p[d].l = x + 1;ans ^= p[d].res;s.insert(p[d]);}

	else if(x == it -> r){p[d].r = x - 1;ans ^= p[d].res;s.insert(p[d]);}

	else

	{

		int e = ++parnum;

		p[e].l = x + 1;p[e].r = p[d].r;p[d].r = x - 1;p[e].id = e;

		ll res = p[d].res;p[d].res = 0;

		int rt = root[d];root[d] = 0;

		if(p[d].r - p[d].l <= p[e].r - p[e].l)

		{

			p[e].res = res;root[e] = rt;

			for(int i = p[d].l;i <= p[d].r;++i)

			{

				p[e].res -= ST::query(root[e],0,a[i] - 1,0,N);

				ST::add(root[e],a[i],-1,0,N);

				p[d].res += ST::query(root[d],a[i] + 1,N,0,N);

				ST::add(root[d],a[i],1,0,N);

			}

		}

		else

		{

			p[d].res = res;root[d] = rt;

			for(int i = p[e].r;i >= p[e].l;--i)

			{

				p[d].res -= ST::query(root[d],a[i] + 1,N,0,N);

				ST::add(root[d],a[i],-1,0,N);

				p[e].res += ST::query(root[e],0,a[i] - 1,0,N);

				ST::add(root[e],a[i],1,0,N);

			}

		}

		s.insert(p[d]);s.insert(p[e]);

		ans = ans ^ p[d].res ^ p[e].res;

	}

	return;

}

int main()

{

	freopen("baibaide.in","r",stdin);

	freopen("baibaide.out","w",stdout);

	scanf("%d%d",&n,&q);

	for(RE int i = 1;i <= n;++i)a[i] = rd();

	for(RE int i = 1;i <= n;++i)

	{

		ans += solve1::query(1,i - 1,a[i] + 1,N);

		solve1::add(i,a[i],1);

	}

	p[++parnum] = (par){1,n,1,ans};

	s.insert(p[1]);

	for(int i = 1;i <= n;++i)ST::add(root[1],a[i],1,0,N);

	RE ll lastans = 0;

	RE int opt;

	RE ll x,y;

	for(RE int i = 1;i <= q;++i)

	{

		opt = rd();x = rd() ^ lastans;

		if(opt == 0)modify(x,rd() ^ lastans);

		else split(x);

		printf("%lld\n",ans);

		lastans = ans;

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}