IO

namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
// print the remaining part
inline void flush() {
    fwrite(obuf, 1, oS - obuf, stdout);
    oS = obuf;
}
// putchar
inline void putc(char x) {
    *oS++ = x;
    if (oS == oT) flush();
}
// input a signed integer
template <class I>
inline void read(I &x) {
    for (f = 1, c = gc(); c < '0' || c > '9'; c = gc())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
    x *= f;
}
// print a signed integer
template <class I>
inline void print(I x) {
    if (!x) putc('0');
    if (x < 0) putc('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putc(qu[qr--]);
}
struct Flusher_ {
    ~Flusher_() {
        flush();
    }
} io_flusher_;
}  // namespace io
using io ::print;
using io ::putc;
using io ::read;

数据结构

树状数组

普通树状数组

int lowbit(int x){
	return x & (-x);
}
//求1~x的前缀和 
int GetSum(int x){
	int ret = 0;
	while(x){
		ret += c[x];
		x -= lowbit(x);
	}
	return ret;
}
//c[x] += d 
void Add(int x , int d , int n){
	while(x <= n){
		c[x] += d;	
		x += lowbit(x);
	}
}

二维树状数组

#include <bits/stdc++.h>
using namespace std;

int C1[2060][2060] , C2[2060][2060] , C3[2060][2060] , C4[2060][2060];

int N , M;

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

int Sum(int x , int y) {
    int res = 0;
    for(int i = x; i > 0; i -= Lowbit(i)) {
        for(int j = y; j > 0 ;j -= Lowbit(j)) {
            res += C1[i][j] * (x + 1) * (y + 1) - C2[i][j] * (y + 1) - C3[i][j] * (x + 1) + C4[i][j];
        }
    }
    return res;
}

void Add(int x , int y , int d , int n , int m) {
    for(int i = x; i <= n; i += Lowbit(i)) {
        for(int j = y; j <= m; j += Lowbit(j)) {
            C1[i][j] += d;
            C2[i][j] += d * x;
            C3[i][j] += d * y;
            C4[i][j] += d * x * y;
        }
    }
}

char Op;
int a , b , c , d , delta;

int main() {
    cin >> Op >> N >> M;
    while(cin >> Op >> a >> b >> c >> d) {
        if(Op == 'L') {
            cin >> delta;
            Add(a , b , delta , N , M);
            Add(a , d + 1 , -delta , N , M);
            Add(c + 1 , b , -delta , N , M);
            Add(c + 1 , d + 1 , delta , N , M);
        }
        else {
            cout << Sum(c , d) - Sum(c , b - 1) - Sum(a - 1 , d) + Sum(a - 1 , b - 1) << endl;
        }
    }
    return 0;
}

线段树

线段树

#include <bits/stdc++.h>
using namespace std;

const long long SIZE = 100010;

struct STree {
    long long LeftTree , RightTree;
    long long Sum;
    long long Add , Prod;
} Tree[SIZE * 4];

long long Num[SIZE];
long long N , M , P;

void Build(long long p , long long l, long long r) {
    Tree[p].LeftTree = l;
    Tree[p].RightTree = r;
    Tree[p].Prod = 1;
    if(l == r) {
        Tree[p].Sum = Num[l] % P;
        return;
    }
    long long Mid = l + r >> 1;
    Build(p * 2 , l , Mid);
    Build(p * 2 + 1 , Mid + 1 , r);
    Tree[p].Sum = Tree[p * 2 + 1].Sum + Tree[p * 2].Sum;
    Tree[p].Sum %= P;
}

void Spread(long long p) {
    Tree[2 * p].Sum = (Tree[p].Prod * Tree[2 * p].Sum  + Tree[p].Add * (Tree[p * 2].RightTree - Tree[p * 2].LeftTree + 1) % P) % P;
    Tree[2 * p + 1].Sum = (Tree[p].Prod * Tree[2 * p + 1].Sum + Tree[p].Add * (Tree[p * 2 + 1].RightTree - Tree[p * 2 + 1].LeftTree + 1) % P) % P;

    Tree[2 * p].Prod = Tree[p * 2].Prod * Tree[p].Prod % P;
    Tree[2 * p + 1].Prod = Tree[p * 2 + 1].Prod * Tree[p].Prod % P;

    Tree[2 * p].Add = (Tree[2 * p].Add * Tree[p].Prod + Tree[p].Add) % P;
    Tree[2 * p + 1].Add = (Tree[2 * p + 1].Add * Tree[p].Prod + Tree[p].Add) % P;

    Tree[p].Prod = 1;
    Tree[p].Add = 0;
}

long long Ask(long long p , long long l , long long r) {
    if(l <= Tree[p].LeftTree && r >= Tree[p].RightTree) 
        return Tree[p].Sum;
    Spread(p);
    long long Val = 0;
    if(l <= (Tree[p].LeftTree + Tree[p].RightTree >> 1))
        Val = (Ask(p * 2 , l , r) + Val) % P;
    if(r > (Tree[p].LeftTree + Tree[p].RightTree >> 1))
        Val = (Val + Ask(p * 2 + 1 , l , r)) % P;
    return Val;
}

void Add(long long p , long long l , long long r , long long d) {
    if(l <= Tree[p].LeftTree && r >= Tree[p].RightTree)  {
        Tree[p].Sum = (Tree[p].Sum + d * (Tree[p].RightTree - Tree[p].LeftTree + 1)) % P;
        Tree[p].Add += d;
        Tree[p].Add %= P;
        return;
    }
    Spread(p);
    if(l <= (Tree[p].LeftTree + Tree[p].RightTree >> 1))
        Add(p * 2 , l , r , d);
    if(r > (Tree[p].LeftTree + Tree[p].RightTree >> 1))
        Add(p * 2 + 1 , l , r , d);
    Tree[p].Sum = Tree[p * 2 + 1].Sum + Tree[p * 2].Sum;
    Tree[p].Sum %= P;
}

void Mu(long long p , long long l , long long r , long long k) {
    if(l <= Tree[p].LeftTree && r >= Tree[p].RightTree) {
        Tree[p].Add = (Tree[p].Add * k) % P;
        Tree[p].Prod = (Tree[p].Prod * k) % P;
        Tree[p].Sum = (Tree[p].Sum * k) % P;
        return;
    }
    Spread(p);
    if(l <= (Tree[p].LeftTree + Tree[p].RightTree >> 1))
        Mu(p * 2 , l , r , k);
    if(r > (Tree[p].LeftTree + Tree[p].RightTree >> 1))
        Mu(p * 2 + 1 , l , r , k);
    Tree[p].Sum = Tree[p * 2 + 1].Sum + Tree[p * 2].Sum;
    Tree[p].Sum %= P;
}


signed main() {
    ios::sync_with_stdio(false);
    cin >> N >> M >> P;
    for(long long i = 1; i <= N; i++)
        cin >> Num[i];
    Build(1 , 1 , N);
    long long op , x , y , k;
    while(M--) {
        cin >> op >> x >> y;
        if(op == 1) {
            cin >> k;
            Mu(1 , x , y , k);
        }
        else if(op == 2) {
            cin >> k;
            Add(1 , x , y , k);
        }
        else {
            cout << Ask(1 , x , y) << endl;
        }
    }
    return 0;
}

扫描线

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;

int N;
int Cnt;
int X[MAXN * 2];

long long Ans;

struct ScanLine {
    long long Left , Right , High;
    int Mark;
    bool operator < (const ScanLine &o) const {
        return High < o.High;
    }
} Line[MAXN * 2];

struct STree {
    int LeftTree , RightTree;
    int Sum;
    long long Len;
} Tree[MAXN * 4];

void Build(int p , int l, int r) {
    Tree[p].LeftTree = l;
    Tree[p].RightTree = r;
    if(l == r) return;
    long long Mid = l + r >> 1;
    Build(p * 2 , l , Mid);
    Build(p * 2 + 1 , Mid + 1 , r);
    return;
}

void Cal(int x) {
    int l = Tree[x].LeftTree;
    int r = Tree[x].RightTree;
    if(Tree[x].Sum) Tree[x].Len = X[r + 1] - X[l];
    else Tree[x].Len = Tree[2 * x].Len + Tree[2 * x + 1].Len;
}

void Add(int p , int l , int r , int d) {
    if(X[Tree[p].RightTree + 1] <= l || r <= X[Tree[p].LeftTree]) return;
    if(l <= X[Tree[p].LeftTree] && X[Tree[p].RightTree + 1] <= r) {
        Tree[p].Sum += d;
        Cal(p);
        return;
    }
    Add(p * 2 , l , r , d);
    Add(p * 2 + 1 , l , r , d);
    Cal(p);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N;
    for(int i = 1 , a , b , c , d; i <= N; i++) {
        cin >> a >> b >> c >> d;
        X[2 * i - 1] = a;
        X[2 * i] = c;
        Line[2 * i - 1] = (ScanLine) {a , c , b , 1};
        Line[2 * i] = (ScanLine) {a , c , d , -1};
    }
    N *= 2;
    sort(X , X + 1 + N);
    sort(Line + 1 , Line + 1 + N);
    int ToT = unique(X + 1 , X + 1 + N) - X - 1;
    Build(1 , 1 , ToT - 1);
    for(int i = 1; i < N; i++) {
        Add(1 , Line[i].Left , Line[i].Right , Line[i].Mark);
        Ans += Tree[1].Len * (Line[i + 1].High - Line[i].High);
    }
    cout << Ans << endl;
    return 0;
}

珂朵莉树

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

struct Node {
    ll l , r;
    mutable ll v;
    Node(const ll &il , const ll &ir , const ll &iv) : l(il) , r(ir) , v(iv) { }
    inline bool operator < (const Node &o) const { 
        return l < o.l; 
    }
};

typedef set<Node>::iterator sit;

set<Node> ODT;
ll N , M , seed , vmax , Num[100010];

sit Split(ll Pos) {
    sit it = ODT.lower_bound(Node(Pos , 0 , 0));
    if(it != ODT.end() && it -> l == Pos) return it;
    it--;
    ll l = it -> l;
    ll r = it -> r;
    ll v = it -> v;
    ODT.erase(it);
    ODT.insert(Node(l , Pos - 1 , v));
    return ODT.insert(Node(Pos , r , v)).first;
}

void Assign(ll l , ll r , ll v) {
    sit itr = Split(r + 1);
    sit itl = Split(l);
    ODT.erase(itl , itr);
    ODT.insert(Node(l , r , v));
}

void Add(ll l , ll r , ll v) {
    sit itr = Split(r + 1);
    sit itl = Split(l);
    for(sit it = itl ; it != itr; it++) {
        it -> v += v;
    }
}

ll Rank(ll l , ll r , ll k) {
    sit itr = Split(r + 1);
    sit itl = Split(l);
    vector<pair<ll , ll> > v;
    v.clear();
    for(sit it = itl; it != itr; it++) {
        v.push_back(make_pair(it -> v , it -> r - it -> l + 1));
    }
    sort(v.begin() , v.end());
    ll i;
    for(i = 0; i < v.size(); i++) {
        if(v[i].second < k) {
            k -= v[i].second;
        }
        else {
            break;
        }
    }
    return v[i].first;
}

ll BinPower(ll x , ll y , ll p) {
    ll res = 1;
    x %= p;
    while(y) {
        if(y & 1) res = res * x % p;
        x = x * x  % p;
        y >>= 1;
    }
    return res;
}

ll Cal_p(ll l , ll r , const ll x , const ll y) {
    sit itr = Split(r + 1);
    sit itl = Split(l);
    ll Ans = 0;
    for(sit it = itl; it != itr; it++) {
        Ans = (Ans + BinPower(it -> v , x , y) * (it -> r - it -> l + 1) % y) % y;
    }
    return Ans;
}

ll rnd() {
    ll res = seed;
    seed = (seed * 7 + 13) % MOD;
    return res;
}


int main() {
    ios::sync_with_stdio(false);
    cin >> N >> M >> seed >> vmax;
    for(int i = 1; i <= N; i++) {
        Num[i] = (rnd() % vmax) + 1;
        ODT.insert(Node(i , i , Num[i]));
    }
    for(int i = 1; i <= M; i++) {
        ll op , l , r , x , y;
        op = (rnd() % 4) + 1;
        l = (rnd() % N) + 1;
        r = (rnd() % N) + 1;
        if(l > r) swap(l , r);
        if(op == 3) x = (rnd() % (r - l + 1)) + 1;
        else x = (rnd() % vmax) + 1;
        if(op == 4) y = (rnd() % vmax) + 1;
        if(op == 1) Add(l , r , x);
        else if(op == 2) Assign(l , r , x);
        else if(op == 3) cout << Rank(l , r , x) << endl;
        else cout << Cal_p(l , r , x , y) << endl;
    }
    return 0;
}

平衡树

红黑树

#include <iostream>
using namespace std;

template<class T>
class RB_Tree {
private:
	static const bool RED = 0;
	static const bool BLACK = 1;
	struct Node { //红黑树节点
		T Value;
		int Size;
		bool Color;
		Node* LeftTree, * RightTree, * Parent;
		Node() : Value(0), Size(0) , Color(RED), LeftTree(NULL), RightTree(NULL), Parent(NULL) { }
		Node* GrandParent() {
			if (Parent == NULL)
				return NULL;
			else 
				return Parent->Parent;
		}
		Node* Uncle() {
			if (GrandParent() == NULL)
				return NULL;
			if (Parent == GrandParent()->RightTree)
				return GrandParent()->LeftTree;
			else
				return GrandParent()->RightTree;
		}
		Node* Sibling() {
			if (Parent->LeftTree == this)
				return Parent->RightTree;
			else
				return Parent->LeftTree;
		}
	};
	void Rotate_Right(Node* p) { //右旋
		Node* gp = p->GrandParent();
		Node* fa = p->Parent;
		Node* y = p->RightTree;

		fa->LeftTree = y;

		if (y != NIL)
			y->Parent = fa;
		p->RightTree = fa;
		fa->Parent = p;

		if (root == fa)
			root = p;
		p->Parent = gp;

		fa->Size -= 1 + p->LeftTree->Size;
		p->Size++;

		if (gp != NULL) {
			if (gp->LeftTree == fa)
				gp->LeftTree = p;
			else
				gp->RightTree = p;
		}
	}  
	void Rotate_Left(Node* p) { //左旋
		if (p->Parent == NULL) {
			root = p;
			return;
		}
		Node* gp = p->GrandParent();
		Node* fa = p->Parent;
		Node* y = p->LeftTree;

		fa->RightTree = y;

		if (y != NIL)
			y->Parent = fa;
		p->LeftTree = fa;
		fa->Parent = p;

		if (root == fa)
			root = p;
		p->Parent = gp;

		fa->Size -= 1 + p->RightTree->Size;
		p->Size++;

		if (gp != NULL) {
			if (gp->LeftTree == fa)
				gp->LeftTree = p;
			else
				gp->RightTree = p;
		}
	}
	void Inorder(Node* p) { //中根遍历
		if (p == NIL)
			return;

		if (p->LeftTree)
			inorder(p->LeftTree);

		cout << p->Value << " ";

		if (p->rightTree)
			inorder(p->RightTree);
	}
	string OutPutColor(bool color) { //输出颜色
		return color ? "BLACK" : "RED";
	}
	Node* GetSmallestChild(Node* p) { //最小键
		if (p->LeftTree == NIL)
			return p;
		return GetSmallestChild(p->LeftTree);
	}
	Node* GetBiggestChild(Node* p) { //最大键
		if (p->RightTree == NIL)
			return p;
		return GetSmallestChild(p->RightTree);
	}
	bool Delete_Child(Node* p, T Date) { //删除
		if (p->Value > Date) {
			if (p->LeftTree == NIL)
				return false;
			return Delete_Child(p->LeftTree, Date);
		}
		else if (p->Value < Date) {
			if (p->RightTree == NIL)
				return false;
			return Delete_Child(p->RightTree, Date);
		}
		else if (p->Value == Date) {
			if (p->RightTree == NIL) {
				p->Parent->Size--;
				Delete_One_Child(p);
				return true;
			}
			Node* smallest = GetSmallestChild(p->RightTree);
			swap(p->Value, smallest->Value);
			smallest->Parent->Size--;
			Delete_One_Child(smallest);
			return true;
		}
		else {
			return false;
		}
		p->Size = p->LeftTree->Size + p->RightTree->Size + 1;
	}
	void Delete_One_Child(Node* p) {
		Node* child = p->LeftTree == NIL ? p->RightTree : p->LeftTree;
		if (p->Parent == NULL && p->LeftTree == NIL && p->RightTree == NIL) {
			p = NULL;
			root = p;
			return;
		}

		if (p->Parent == NULL) {
			delete  p;
			child->Parent = NULL;
			root = child;
			root->Color = BLACK;
			return;
		}

		if (p->Parent->LeftTree == p)
			p->Parent->LeftTree = child;
		else
			p->Parent->RightTree = child;

		child->Parent = p->Parent;

		if (p->Color == BLACK) {
			if (child->Color == RED)
				child->Color = BLACK;
			else
				Delete_Case(child);
		}
		delete p;
	}
	void Delete_Case(Node* p) {
		if (p->Parent == NULL) {
			p->Color = BLACK;
			return;
		}
		if (p->Sibling()->Color == RED) {
			p->Parent->Color = RED;
			p->Sibling()->Color = BLACK;
			if (p == p->Parent->LeftTree)
				Rotate_Left(p->Parent);
			else
				Rotate_Right(p->Parent);
		}
		if (p->Parent->Color == BLACK && p->Sibling()->Color == BLACK && p->Sibling()->LeftTree->Color == BLACK && p->Sibling()->RightTree->Color == BLACK) {
			p->Sibling()->Color = RED;
			Delete_Case(p->Parent);
		}
		else if (p->Parent->Color == RED && p->Sibling()->Color == BLACK && p->Sibling()->LeftTree->Color == BLACK && p->Sibling()->RightTree->Color == BLACK) {
			p->Sibling()->Color = RED;
			p->Parent->Color = BLACK;
		}
		else {
			if (p->Sibling()->Color == BLACK) {
				if (p == p->Parent->LeftTree && p->Sibling()->LeftTree->Color == RED && p->Sibling()->RightTree->Color == BLACK) {
					p->Sibling()->Color = RED;
					p->Sibling()->LeftTree->Color = BLACK;
					Rotate_Right(p->Sibling()->LeftTree);
				}
				else if (p == p->Parent->RightTree && p->Sibling()->LeftTree->Color == BLACK && p->Sibling()->RightTree->Color == RED) {
					p->Sibling()->Color = RED;
					p->Sibling()->RightTree->Color = BLACK;
					Rotate_Left(p->Sibling()->RightTree);
				}
			}
			p->Sibling()->Color = p->Parent->Color;
			p->Parent->Color = BLACK;
			if (p == p->Parent->LeftTree) {
				p->Sibling()->RightTree->Color = BLACK;
				Rotate_Left(p->Sibling());
			}
			else {
				p->Sibling()->LeftTree->Color = BLACK;
				Rotate_Right(p->Sibling());
			}
		}
	}
	void Insert(Node* p, T Data) { //插入
		if (p->Value >= Data) {
			if (p->LeftTree != NIL)
				Insert(p->LeftTree, Data);
			else {
				Node* tmp = new Node();
				tmp->Value = Data;
				tmp->LeftTree = tmp->RightTree = NIL;
				tmp->Parent = p;
				p->LeftTree = tmp;
				tmp->Size = 1;
				p->Size = p->LeftTree->Size + p->RightTree->Size + 1;
				Insert_case(tmp);
			}
		}
		else {
			if (p->RightTree != NIL)
				Insert(p->RightTree, Data);
			else {
				Node* tmp = new Node();
				tmp->Value = Data;
				tmp->LeftTree = tmp->RightTree = NIL;
				tmp->Parent = p;
				p->RightTree = tmp;
				tmp->Size = 1;
				p->Size = p->LeftTree->Size + p->RightTree->Size + 1;
				Insert_case(tmp);
			}
		}
	}
	void Insert_case(Node* p) {
		if (p->Parent == NULL) {
			root = p;
			p->Color = BLACK;
			return;
		}
		if (p->Parent->Color == RED) {
			if (p->Uncle()->Color == RED) {
				p->Parent->Color = p->Uncle()->Color = BLACK;
				p->GrandParent()->Color = RED;
				Insert_case(p->GrandParent());
			}
			else {
				if (p->Parent->RightTree == p && p->GrandParent()->LeftTree == p->Parent) {
					Rotate_Left(p);
					p->Color = BLACK;
					p->Parent->Color = RED;
					Rotate_Right(p);
				}
				else if (p->Parent->LeftTree == p && p->GrandParent()->RightTree == p->Parent) {
					Rotate_Right(p);
					p->Color = BLACK;
					p->Parent->Color = RED;
					Rotate_Left(p);
				}
				else if (p->Parent->LeftTree == p && p->GrandParent()->LeftTree == p->Parent) {
					p->Parent->Color = BLACK;
					p->GrandParent()->Color = RED;
					Rotate_Right(p->Parent);
				}
				else if (p->Parent->RightTree == p && p->GrandParent()->RightTree == p->Parent) {
					p->Parent->Color = BLACK;
					p->GrandParent()->Color = RED;
					Rotate_Left(p->Parent);
				}
			}
		}
	}
	bool Find(Node* p, T Date) {
		if (p->Value > Date) {
			if (p->LeftTree == NIL)
				return false;
			return Find(p->LeftTree, Date);
		}
		else if (p->Value == Date) {
			return true;
		}
		else if (p->Value < Date) {
			if (p->RightTree == NIL)
				return false;
			return Find(p->RightTree, Date);
		}
		else {
			return false;
		}
	}
	void Delete_Tree(Node* p) { //删除红黑树
		if (!p || p == NIL) {
			return;
		}
		Delete_Tree(p->LeftTree);
		Delete_Tree(p->RightTree);
		delete p;
	}
public:
	RB_Tree() {
		NIL = new Node;
		NIL->Color = BLACK;
		root = NULL;
	}
	~RB_Tree() {
		if (root)
			Delete_Tree(root);
		delete NIL;
	}
	void Inorder() { //中根遍历
		if (root == NULL)
			return;
		Inorder(root);
		cout << endl;
	}
	void Insert(T x) { //插入
		if (root == NULL) {
			root = new Node();
			root->Color = BLACK;
			root->LeftTree = root->RightTree = NIL;
			root->Size = 1;
			root->Value = x;
		}
		else {
			Insert(root, x);
		}
	}
	bool Delete(T data) { //删除
		return Delete_Child(root, data);
	}
	int Size() {
		if (root == NULL)
			return 0;
		return root->Size;
	}
	bool Find(T Date) {
		return Find(root, Date);
	}
private:
	Node* root, * NIL;
};

RB_Tree<int> test;

int main() {

	return 0;
}

Splay

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

int Root , ToT , Fa[MAXN] , Tree[MAXN][2] , Val[MAXN] , Cnt[MAXN] , Size[MAXN];

struct splay {
	void UpDate(int x) {
		Size[x] = Size[Tree[x][0]] + Size[Tree[x][1]] + Cnt[x];
	}
	bool Get(int x) {
		return x == Tree[Fa[x]][1];
	}
	void Rotate(int x) {
		int y = Fa[x];
		int z = Fa[Fa[x]];
		int Check = Get(x);
		Tree[y][Check] = Tree[x][Check ^ 1];
		if(Tree[x][Check ^ 1]) {
			Fa[Tree[x][Check ^ 1]] = y;
		}
		Tree[x][Check ^ 1] = y;
		Fa[y] = x;
		Fa[x] = z;
		if(z) {
			Tree[z][y == Tree[z][1]] = x;
		}
		UpDate(x);
		UpDate(y);
	}
	void Splay(int x) {
		for(int f = Fa[x]; f = Fa[x] , f; Rotate(x)) {
			if(Fa[f]) {
				Rotate(Get(x) == Get(f) ? f : x);
			}
		}
		Root = x;
	}
	void Insert(int k) {
		if(!Root) {
			Val[++ToT] = k;
			Cnt[ToT]++;
			Root = ToT;
			UpDate(Root);
			return;
		}
		int Cur = Root , f = 0;
		while(true) {
			if(Val[Cur] == k) {
				Cnt[Cur]++;
				UpDate(Cur);
				UpDate(f);
				Splay(Cur);
				return;
			}
			f = Cur;
			Cur = Tree[Cur][Val[Cur] < k];
			if(!Cur) {
				Val[++ToT] = k;
				Cnt[ToT]++;
				Fa[ToT] = f;
				Tree[f][Val[f] < k] = ToT;
				UpDate(ToT);
				UpDate(f);
				Splay(ToT);
				break;
			}
		}
	}
	int Rank(int k) {
		int res = 0;
		int Cur = Root;
		while(true) {
			if(k < Val[Cur]) {
				Cur = Tree[Cur][0];
			}
			else {
				res += Size[Tree[Cur][0]];
				if(k == Val[Cur]) {
					Splay(Cur);
					return res + 1;
				}
				res += Cnt[Cur];
				Cur = Tree[Cur][1];
			}
		}
	}
	int Kth(int k) {
		int Cur = Root;
		while(true) {
			if(Tree[Cur][0] && k <= Size[Tree[Cur][0]]) {
				Cur = Tree[Cur][0];
			}
			else {
				k -= Cnt[Cur] + Size[Tree[Cur][0]];
				if(k <= 0) {
					Splay(Cur);
					return Val[Cur];
				}
				Cur = Tree[Cur][1];
			}
		}
	}
	void Find(int x) {
		int Cur = Root;
		if(!Root) return;
		while(Val[Cur] != x) {
			if(Val[Cur] > x) {
				if(!Tree[Cur][0]) break;
				Cur = Tree[Cur][0];
			}
			else {
				if(!Tree[Cur][1]) break;
				Cur = Tree[Cur][1];
			}
		}
		Splay(Cur);
	}
	int Min() {
		int Cur = Tree[Root][0];
		if(!Cur) return Cur;
		while(Tree[Cur][1]) Cur = Tree[Cur][1];
		Splay(Cur);
		return Cur;
	}
	int Max() {
		int Cur = Tree[Root][1];
		if(!Cur) return Cur;
		while(Tree[Cur][0]) Cur = Tree[Cur][0];
		Splay(Cur);
		return Cur;
	}
	void Clear(int x) {
		Tree[x][0] = Tree[x][1] = Fa[x] = Val[x] = Size[x] = Cnt[x] = 0;
	}
	void Delete(int k) {
		Rank(k);
		if(Cnt[Root] > 1) {
			Cnt[Root]--;
			UpDate(Root);
			return;
		}
		if(!Tree[Root][0] && !Tree[Root][1]) {
			Clear(Root);
			Root = 0;
			return;
		}
		if(!Tree[Root][0]) {
			int Cur = Root;
			Root = Tree[Root][1];
			Fa[Root] = 0;
			Clear(Cur);
			return;
		}
		if(!Tree[Root][0]) {
			int Cur = Root;
			Root = Tree[Root][0];
			Fa[Root] = 0;
			Clear(Cur);
		}
		int Cur = Root;
		int x = Min();
		Fa[Tree[Cur][1]] = x;
		Tree[x][1] = Tree[Cur][1];
		Clear(Cur);
		UpDate(Root);
	}
	int GetPre(int x) {
		Insert(x);
		int ans = Val[Min()];
		Delete(x);
		return ans;
	}
	int GetNext(int x) {
		Insert(x);
		int ans = Val[Max()];
		Delete(x);
		return ans;
	}
} tree;

int N , Op , X , M;
string s;
int P[MAXN] , cnt;

int main() {
	
	return 0;
}

自顶向下Splay(快得多)

//By 石皓文(洛谷@ShwStone
#include <bits/stdc++.h>
using namespace std;

#define ls son[0]
#define rs son[1]

const int maxn = 1e5 + 5;

template <class _Tp> class splay_tree {
private:
	struct node; 
	typedef node* pos; 
	node buf[maxn]; 
       	int buf_cnt, fix_cnt; 
	pos need_fix[maxn]; 
	struct node {
		_Tp val;
		int cnt, size;
		pos son[2]; // 0ls, 1rs
		node() { cnt = size = 0; val = 0; ls = rs = NULL; }
	};
	inline pos new_node(_Tp val, int cnt) { 
		pos res = buf + (++buf_cnt); 
		res -> ls = res -> rs = buf; 
		res -> val = val; res -> cnt = res -> size = cnt;
		return res; 
	}
	pos root;
public:
	splay_tree() { buf -> ls = buf -> rs = buf; buf -> cnt = buf -> size = 0; root = buf; }
	void insert(_Tp val) { root = __insert(val, 1, root); }
	void insert(_Tp val, int cnt) { root = __insert(val, cnt, root); }
	void remove(_Tp val) { root = __remove(val, root); }
	void print() { __print(root); }
	void debug() {
		putchar('\n');
		printf("root: %d\n", root - buf);
		for (int i = 0; i <= buf_cnt; i++) {
			printf("node#%d  val: %d  cnt: %d  size: %d ls: %d rs: %d\n", i, buf[i].val, buf[i].cnt, buf[i].size, buf[i].ls - buf, buf[i].rs - buf);
		}
		putchar('\n');
	}
	inline int rank(_Tp val) {
		root = splay_val(val, root);
		return rank_min(root);
	}
	inline _Tp kth(int k) {
		root = splay_rank(k, root);
		return root -> val;
	}
	_Tp pre(_Tp val) {
		pos t = root;
	       	_Tp ans;
		while (t != buf) {
			if (t -> val < val) {
				ans = t -> val;
				t = t -> rs;
			}
			else t = t -> ls;
		}
		return ans;
	}
	_Tp nxt(_Tp val) {
		pos t = root;
	       	_Tp ans;
		while (t != buf) {
			if (t -> val > val) {
				ans = t -> val;
				t = t -> ls;
			}
			else t = t -> rs;
		}
		return ans;
	}
private:
	inline void fix_up(pos x) { x -> size = x -> ls -> size + x -> rs -> size + x -> cnt; }
	inline pos rotate(pos x, int with) {
		pos y = x -> son[with];
		x -> son[with] = y -> son[with ^ 1]; y -> son[with ^ 1] = x;
		fix_up(x); fix_up(y);
		return y;
	}
	pos splay_val(_Tp val, pos t) {
		node header; header.ls = header.rs = buf;
		pos tmp[2] = {&header, &header}; // 0ls_max, 1rs_min
		fix_cnt = 0;
		while (t -> val != val) {
			int f1 = (val > t -> val); // 0ls, 1rs
			if (t -> son[f1] == buf) break;
			if (t -> son[f1] -> val != val) {
				int f2 = (val > t -> son[f1] -> val); // 0ls, 1rs
				if (f1 == f2) t = rotate(t, f1);
				if (t -> son[f1] == buf) break;
			}
			tmp[f1 ^ 1] -> son[f1] = t; tmp[f1 ^ 1] = t;
			need_fix[++fix_cnt] = t;
			t = t -> son[f1];
		}
		tmp[0] -> rs = t -> ls; tmp[1] -> ls = t -> rs;
		t -> ls = header.rs; t -> rs = header.ls;
		for (int i = fix_cnt; i >= 1; i--) fix_up(need_fix[i]);
		fix_up(t);
		return t;
	}
	inline int rank_min(pos t) { return t -> ls -> size + 1; }
	inline int rank_max(pos t) { return t -> ls -> size + t -> cnt; }
	pos splay_rank(int k, pos t) {
		node header; header.ls = header.rs = buf;
		pos tmp[2] = {&header, &header}; // 0ls_max, 1rs_min
		fix_cnt = 0;
		while (rank_min(t) > k || rank_max(t) < k) {
//			printf("#%d %d %d\n", t - buf, rank_min(t), rank_max(t));
			int f1 = (rank_max(t) < k); // 0ls, 1rs
			if (f1 == 1) k -= rank_max(t);
//			printf("f1: %d\n", f1);
			if (t -> son[f1] == buf) break;
			if (rank_min(t -> son[f1]) > k || rank_max(t -> son[f1]) < k) {
				int f2 = (rank_max(t -> son[f1]) < k); // 0ls, 1rs
//				printf("f2: %d\n", f2);
				if (f1 == f2) {
					if (f2 == 1) k -= rank_max(t -> son[f1]);
					t = rotate(t, f1);
				}
				if (t -> son[f1] == buf) break;
			}
			tmp[f1 ^ 1] -> son[f1] = t; tmp[f1 ^ 1] = t;
			need_fix[++fix_cnt] = t;
			t = t -> son[f1];
//			debug();
		}
		tmp[0] -> rs = t -> ls; tmp[1] -> ls = t -> rs;
		t -> ls = header.rs; t -> rs = header.ls;
		for (int i = fix_cnt; i >= 1; i--) fix_up(need_fix[i]);
		fix_up(t);
		return t;
	}	
	pos __insert(_Tp val, int cnt, pos t) {
		pos p = new_node(val, cnt);
		if (t == buf) t = p;
		else {
			t = splay_val(val, t);
			if (t -> val == val) {
				t -> cnt++; t -> size++; 
				buf_cnt--;
				return t;
			}
			int f = (val > t -> val); // 0ls, 1rs
			p -> son[f] = t -> son[f]; p -> son[f ^ 1] = t; t -> son[f] = buf;
			fix_up(t); t = p; fix_up(t);
		}
		return t;
	}
	pos __remove(_Tp val, pos t) {
		if (t != buf) {
			t = splay_val(val, t);
			if (val == t -> val) {
				t -> size--; t -> cnt--;
				if (t -> cnt == 0) {
					pos p;
    					if (t -> ls == buf) p = t -> rs;
    					else {
    						p = t -> ls;
    						p = splay_val(val, p);
    						p -> rs = t -> rs;
    						fix_up(p);
    					}
    					t -> ls = t -> rs = buf;
    					t = p;
				}
			}
		}
		return t;
	}
	void __print(pos t) {
		if (t == buf) return;
		__print(t -> ls);
		for (int i = 1; i <= t -> cnt; i++) printf("%d ", t -> val);
		__print(t -> rs);
	}
};

splay_tree<int> st;

LCT

#include <bits/stdc++.h>
using namespace std;

namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
// print the remaining part
inline void flush() {
    fwrite(obuf, 1, oS - obuf, stdout);
    oS = obuf;
}
// putchar
inline void putc(char x) {
    *oS++ = x;
    if (oS == oT) flush();
}
// input a signed integer
template <class I>
inline void read(I &x) {
    for (f = 1, c = gc(); c < '0' || c > '9'; c = gc())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
    x *= f;
}
// print a signed integer
template <class I>
inline void print(I x) {
    if (!x) putc('0');
    if (x < 0) putc('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putc(qu[qr--]);
}
struct Flusher_ {
    ~Flusher_() {
        flush();
    }
} io_flusher_;
}  // namespace io
using io ::print;
using io ::putc;
using io ::read;

const int MAXN = 1e5 + 10;

struct Link_Cut_Tree {
    int Son[MAXN][2], Value[MAXN], Xor_Sum[MAXN], Fa[MAXN];
    bool Tag[MAXN];

    bool IsRoot(int p) {
        return Son[Fa[p]][0] != p && Son[Fa[p]][1] != p;
    }

    void PushUp(int p) {
        Xor_Sum[p] = Xor_Sum[Son[p][0]] ^ Xor_Sum[Son[p][1]] ^ Value[p];
    }

    void PushDown(int p) {
        if (Tag[p]) {
            swap(Son[p][0], Son[p][1]);
            if (Son[p][0]) Tag[Son[p][0]] ^= 1;
            if (Son[p][1]) Tag[Son[p][1]] ^= 1;
            Tag[p] ^= 1;
        }
    }

    int Get(int p) {
        return Son[Fa[p]][1] == p;
    }

    void Rotate(int x) {
        int y = Fa[x], z = Fa[y], k = Get(x);
        if (!IsRoot(y)) Son[z][Son[z][1] == y] = x;
        Son[y][k] = Son[x][!k];
        Fa[Son[x][!k]] = y;
        Son[x][!k] = y;
        Fa[y] = x;
        Fa[x] = z;
        PushUp(y);
        PushUp(x);
        return;
    }

    void UpDate(int x) {
        if (!IsRoot(x)) UpDate(Fa[x]);
        PushDown(x);
        return;
    }

    void Splay(int x) {
        UpDate(x);
        for (int fa; fa = Fa[x], !IsRoot(x); Rotate(x)) {
            if (!IsRoot(fa)) Rotate(Get(fa) == Get(x) ? fa : x);
        }
    }

    int Access(int x) {
        int p = 0;
        for (p = 0; x; p = x, x = Fa[x]) {
            Splay(x);
            Son[x][1] = p;
            PushUp(x);
        }
        return p;
    }

    int Find(int p) {
        Access(p);
        Splay(p);
        while (Son[p][0]) {
            PushDown(p);
            p = Son[p][0];
        }
        return p;
    }

    void MakeRoot(int p) {
        Access(p);
        Splay(p);
        Tag[p] ^= 1;
        return;
    }

    void Link(int x, int y) {
        MakeRoot(x);
        Fa[x] = y;
    }

    void Split(int x, int y) {
        MakeRoot(x);
        Access(y);
        Splay(y);
    }

    void Cut(int x, int y) {
        Split(x, y);
        if (Son[y][Get(x) ^ 1] || Fa[x] != y || Son[x][1]) return;
        Fa[x] = Son[y][0] = 0;
        PushUp(y);
    }
} LCT;

int N, M;

int main() {
    read(N);
    read(M);
    for (int i = 1; i <= N; i++) {
        read(LCT.Value[i]);
        LCT.PushUp(i);
    }

    while (M--) {
        int opt, x, y;
        read(opt);
        read(x);
        read(y);

        if (opt == 0) {
            LCT.Split(x, y);
            cout << LCT.Xor_Sum[y] << endl;
        }

        if (opt == 1) {
            if (LCT.Find(x) != LCT.Find(y))
                LCT.Link(x, y);
        }

        if (opt == 2) {
			if(LCT.Find(x) == LCT.Find(y)) LCT.Cut(x, y);
        }

		if(opt == 3) {
			LCT.Splay(x);
			LCT.Value[x] = y;
			LCT.PushUp(x);
		}
    }
    return 0;
}