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;
}