模板

发表于 2022-07-14 分类于信奥阅读次数：

~~老祖宗传的板子~~

IO

code

#define FILE_IO
namespace io {
    #ifdef FILE_IO
    #define FREAD
    #define FWRITE
    #endif

    #ifdef FREAD
    static char ibuf[100000], *p1 = ibuf, *p2 = ibuf;
    #define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
    #endif
  
    #ifdef FWRITE
    static char obuf[100000], *p3 = obuf;
    #define putchar(x) ((p3 - obuf < 100000) ? (*p3++ = (x)) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++ = (x)))
    struct flasher { ~flasher() { fwrite(obuf, p3 - obuf, 1, stdout); } }flash;
    #endif
    //读入失败返回true
    template <class T> bool read(T &r) {
        r = 0; static char ch = getchar(); bool f = false;
        while (ch < 48 || ch > 57) { if (ch == EOF) return true; if (ch == 45) f ^= 1; ch = getchar(); }
        while (ch >= 48 && ch <= 57) { r = r * 10 + ch - 48; ch = getchar(); }
        if (f) r = -r; return false;
    }
    template <class T> void write(T w, char end = '\n') {
        static char write_buf[55]; char *pos = write_buf;
        if (w == 0) { putchar('0'); putchar(end); return; }
        if (w < 0) { putchar('-'); w = -w; }
        while (w) {
            *(pos++) = w % 10 + '0';
            w /= 10;
        }
        while (pos != write_buf) putchar(*(--pos));
        putchar(end);
    }
};
using namespace io;

optimize优化

code

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
/*---基础优化结束---*/
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

二分 & 三分

//二分
int l, r, mid;
while (l < r) {
    mid = (l + r /* + 1*/) >> 1; //手推一下 l + 1 == r 的情况，考虑是否加一
    if (check(mid)) r = mid;
    else l = mid + 1;
}

//精度二分
double l, r, mid, eps;
while (l + eps < r) {
    mid = (l + r) / 2;
    if (check(mid)) r = mid;
    else l = mid + eps;
}

//三分求f最小值（最大值改一改）
//最优的三分不是均匀分成3块，而是在mid左右两侧取值，这样显然更快。
int l, r, mid;
while (r - l >= 3) {
    mid = (l + r) >> 1;
    if (f(mid) > f(mid + 1)) l = mid + 1;
    else r = mid;
}
//为了避免边界错误，分到只剩3个数就枚举一遍。
int ans, tmp = INT_MAX;
for (int i = l; i <= r; i++) {
    if (f(i) < tmp) {
        ans = i;
        tmp = f(i);
    }
}

网络流

最大流

code

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

template <class T> bool read(T &r) {
        r = 0; int ch = getchar(), f = 0;
        while (!isdigit(ch)) { if (ch == EOF) return true; f ^= (ch == '-'), ch = getchar(); }
        while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
        if (f) r = -r; return false;
}
template <class T, class ...Ts> bool read(T &r, Ts &... rs) { return read(r) || read(rs...); }

const int maxm = 1e5 + 5, maxn = 1e5 + 5;
const long long inf = LLONG_MAX;

int n, m, s, t;
struct Edge {
        long long w;
        int v, nxt;
} e[maxm];
int head[maxn], cur[maxn], cnt = 1;
int dep[maxn], gap[maxn];

void add(int u, int v, long long w) {
        e[++cnt].nxt = head[u];
        e[cnt].v = v, e[cnt].w = w;
        head[u] = cnt;
}
void bfs() {
        memset(dep, -1, sizeof dep); memset(gap, 0, sizeof gap);
        queue<int> q; q.emplace(t); gap[dep[t] = 0]++;
        while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int i = head[u]; i; i = e[i].nxt) {
                        if (e[i ^ 1].w && dep[e[i].v] == -1) {
                                gap[dep[e[i].v] = dep[u] + 1]++;
                                q.emplace(e[i].v);
                        }
                }
        }
}
long long dfs(int u = s, long long flow = inf) {
        if (!flow || u == t) return flow;
        long long rest = flow; for (int i = cur[u]; i; i = e[i].nxt) {
                cur[u] = i; if (e[i].w && dep[u] == dep[e[i].v] + 1) {
                        long long f = dfs(e[i].v, min(rest, e[i].w));
                        e[i].w -= f, e[i ^ 1].w += f, rest -= f;
                        if (!rest) break;
                }
        } if (rest) {
                if (!--gap[dep[u]++]) dep[s] = n + 1;
                gap[dep[u]]++;
        } return flow - rest;
}
long long iSAP() {
        long long res = 0; bfs();
        while (dep[s] < n) {
                memcpy(cur, head, sizeof cur);
                res += dfs();
        } return res;
}

int main() {
        read(n, m, s, t);
        for (int i = 1; i <= m; i++) {
                int u, v; long long w; read(u, v, w);
                add(u, v, w); add(v, u, 0);
        } printf("%lld\n", iSAP());
        return 0;
}

费用流

code

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

template <class T> bool read(T &r) {
        r = 0; int ch = getchar(), f = 0;
        while (!isdigit(ch)) { if (ch == EOF) return true; f ^= (ch == '-'), ch = getchar(); }
        while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
        if (f) r = -r; return false;
}
template <class T, class ...Ts> bool read(T &r, Ts &...rs) { return read(r) || read(rs...); }

const int maxn(5e3 + 5), maxm(1e5 + 5);
const long long inf(0x3f3f3f3f3f3f3f3f);

int n, m, s, t;
struct Edge {
        int v, nxt;
        long long c, w;
} e[maxm];
int head[maxn], cur[maxn], cnt = 1;
long long dis[maxn], ans, cost;
bool vis[maxn];

void add(int u, int v, long long w, long long c) {
        e[++cnt].nxt = head[u]; head[u] = cnt;
        e[cnt].v = v, e[cnt].w = w, e[cnt].c = c;
}

bool spfa() {
        deque<int> q; q.emplace_back(t);
        memset(vis, 0, sizeof vis); vis[t] = true;
        memset(dis, 0x3f, sizeof dis); dis[t] = 0;
        while (!q.empty()) {
                int u = q.front(); q.pop_front(); vis[u] = false;
                for (int i = head[u]; i; i = e[i].nxt) {
                        if (e[i ^ 1].w && dis[e[i].v] > dis[u] - e[i].c) {
                                dis[e[i].v] = dis[u] - e[i].c;
                                if (!vis[e[i].v]) {
                                     vis[e[i].v] = true;
                                     if (!q.empty() && dis[e[i].v] < dis[q.front()]) q.emplace_front(e[i].v);
                                     else q.emplace_back(e[i].v);
                                }
                        }
                }
        } return dis[s] != inf;
}
long long dfs(int u = s, long long flow = inf) {
        vis[u] = true; if (!flow || u == t) return flow;
        long long rest = flow; for (int i = cur[u]; i; i = e[i].nxt) {
                cur[u] = i; if (!vis[e[i].v] && e[i].w && dis[e[i].v] == dis[u] - e[i].c) {
                        long long f = dfs(e[i].v, min(e[i].w, rest));
                        e[i].w -= f, e[i ^ 1].w += f, rest -= f;
                        if (!rest) break;
                }
        } return flow - rest;
}
void mcmf() {
        while (spfa()) do {
                memset(vis, 0, sizeof vis);
                memcpy(cur, head, sizeof cur);
                long long f = dfs();
                ans += f, cost += dis[s] * f;
        } while (vis[t]);
}

int main() {
        read(n, m, s, t);
        for (int i = 1; i <= m; i++) {
                int u, v; long long w, c; read(u, v, w, c);
                add(u, v, w, c); add(v, u, 0, -c);
        } mcmf();
        printf("%lld %lld\n", ans, cost);
        return 0;
}

数据结构

单调栈 & 单调队列

单调栈一般维护当前节点往前找到的第一个小于/大于它的点，分别对应递增栈/递减栈。

//递增栈
stack<int> s;
for (int i = 1; i <= n; i++) {
    while (!s.empty() && num[s.top()] >= num[i]) s.pop();
    min_left[i] = s.top();
    s.push(i);
}
//min_left中存储向左第一个小于它的节点的下标。

单调队列一般维护当前节点往前找m个点的最大/小值，分别对应递增队列/递减队列。一般用 deque 实现。

//递增队列
while (!q.empty()) q.pop_back();
num[0] = num[n + 1] = inf;
q.push_back(0);
for (int i = 1; i < k; i++) {
    while (!q.empty() && num[q.back()] >= num[i]) q.pop_back();
    q.push_back(i);
}
for (int i = k; i <= n; i++) {
    while (!q.empty() && num[q.back()] >= num[i]) q.pop_back();
    q.push_back(i);
    while (!q.empty() && q.front() < i - k + 1) q.pop_front();
    minium[i - k + 1] = num[q.front()];
}

树状数组

普通树状数组

code

//long long !!!
#define lowbit(x) ((x) & (-x))
int c[maxn];
int ask(int pos){
	int res = 0;
	while(pos) {
		res += c[pos];
		pos -= lowbit(pos);
	}
	return res;
}
void update(int pos, int x){
	while(pos <= n){
		c[pos] += x;
		pos += lowbit(pos);
	}
}

二维树状数组

code

int c[maxn][maxn];
int ask(int pos_i, int pos_j) {
	int res = 0;
	for (int i = pos_i; i; i -= lowbit(i))
		for (int j = pos_j; j; j -= lowbit(j))
			res += c[i][j];
	return res;
}
void update(int pos_i, int pos_j, int x) {
	for (int i = pos_i; i <= n; i += lowbit(i))
		for (int j = pos_j; j <= m; j += lowbit(j))
			c[i][j] += x;
}

线段树

code

int n, m;
long long a[maxn];

struct node;
typedef node* pos;
pos new_node(int l, int r);
struct node {
private:
    void push_up() { val = ls -> val + rs -> val; /*可以更改*/ }
    void update_one(int x) { tag += x; val += x * (r - l + 1); /*可以更改*/ }
    void push_down() { ls -> update_one(tag); rs -> update_one(tag); tag = 0; }
public:
    int l, r;
    long long val, tag;
    pos ls, rs;
    node() {
        l = r = val = tag = 0;
        ls = rs = NULL;
    }
    void build() {
        if (l == r) { val = a[l]; /*可以更改*/ return; }
        int mid = (l + r) >> 1;
        ls = new_node(l, mid); ls -> build();
        rs = new_node(mid + 1, r); rs -> build();
        push_up();
    }
    void update(int _l, int _r, long long x) {
        if (l >= _l && r <= _r) { update_one(x); return; }
        push_down();
        int mid = (l + r) >> 1;
        if (mid >= _l) ls -> update(_l, _r, x);
        if (mid + 1 <= _r) rs -> update(_l, _r, x);
        push_up();
    }
    long long ask(int _l, int _r) {
        if (l >= _l && r <= _r) { return val; }
        push_down();
        int mid = (l + r) >> 1; long long res = 0;
        if (mid >= _l) res += /*可以更改*/ ls -> ask(_l, _r);
        if (mid + 1 <= _r) res += /*可以更改*/ rs -> ask(_l, _r);
        return res;
    }
};

node buf[maxn * 2];
pos root = buf, buf_pos = buf; 

pos new_node(int l, int r) {
    pos p = ++buf_pos;
    p -> ls = p -> rs = buf;
    p -> l = l, p -> r = r;
    return p;
}

珂朵莉树

By CmsMartin

code

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

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;

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

平衡树

红黑树

By CmsMartin

code

#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

code

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