这东西都没什么板子着实让我很难受啊，只能到网上抄抄补补，
记下两个用到的博客
https://blog.csdn.net/clove_unique/article/details/50630280
https://blog.csdn.net/ophunter_lcm/article/details/18157185
BZOJ 3224
复制粘贴？…
#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>
#include <queue>
#include <math.h>
#include <string>
#include <algorithm>
#include <time.h> #define SIGMA_SIZE 26
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) (x&-x)
#define foe(i, a, b) for(int i=a; i<=b; i++)
#define fo(i, a, b) for(int i=a; i<b; i++);
#pragma warning ( disable : 4996 ) using namespace std;
typedef long long LL;
inline LL LMax(LL a, LL b) { return a>b ? a : b; }
inline LL LMin(LL a, LL b) { return a>b ? b : a; }
inline LL lgcd(LL a, LL b) { return b == ? a : lgcd(b, a%b); }
inline LL llcm(LL a, LL b) { return a / lgcd(a, b)*b; } //a*b = gcd*lcm
inline int Max(int a, int b) { return a>b ? a : b; }
inline int Min(int a, int b) { return a>b ? b : a; }
inline int gcd(int a, int b) { return b == ? a : gcd(b, a%b); }
inline int lcm(int a, int b) { return a / gcd(a, b)*b; } //a*b = gcd*lcm
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = ;
const double eps = 1e-;
const int inf = 0x3f3f3f3f;
const int maxk = 1e6 + ;
const int maxn = 1e5 + ; int Size, root;
int ch[maxn<<][];
int f[maxn<<];
int key[maxn<<];
int cnt[maxn<<];
int siz[maxn<<]; inline void clear(int x)
{ ch[x][] = ch[x][] = f[x] = cnt[x] = key[x] = siz[x] = ; } //判断当前点是它父节点的左儿子还是右儿子
inline int get(int x)
{ return ch[f[x]][] == x; } //更新当前点size值(用于修改之后)
inline void update(int x)
{
if (x) {
siz[x] = cnt[x];
if (ch[x][]) siz[x] += siz[ch[x][]];
if (ch[x][]) siz[x] += siz[ch[x][]];
}
} inline void rotate(int x)
{
int old = f[x], oldf = f[old], which = get(x);
ch[old][which] = ch[x][which^]; f[ch[old][which]] = old;
f[old] = x; ch[x][which^] = old;
f[x] = oldf;
if (oldf)
ch[oldf][ch[oldf][]==old] = x;
update(old); update(x);
} inline void splay(int x)
{
for( int fa; (fa=f[x]); rotate(x))
if ( f[fa] )
rotate((get(x)==get(fa) ? fa : x));
root = x;
} inline void insert(int v)
{
if ( root == )
{
Size++; ch[Size][] = ch[Size][] = f[Size] = ; key[Size] = v;
cnt[Size] = ; siz[Size] = ; root = Size; return;
} int now = root, fa = ;
while ()
{
if (key[now] == v) {
cnt[now]++;
update(now); update(fa);
splay(now);
break;
}
fa = now;
now = ch[now][key[now]<v];
if (now == ) {
Size++;
ch[Size][] = ch[Size][] = ;
key[Size] = v; siz[Size] = ;
cnt[Size] = ; f[Size] = fa;
ch[fa][key[fa]<v] = Size;
update(fa);
splay(Size);
break;
}
}
} inline int find(int v)
{
int ans = , now = root;
while ()
{
if ( v < key[now] )
now = ch[now][];
else {
ans += (ch[now][] ? siz[ch[now][]] : );
if ( v == key[now] ) { splay(now); return ans+; } ans += cnt[now];
now = ch[now][];
}
}
} inline int findx(int x)
{
int now = root;
while ()
{
if ( ch[now][] && x <= siz[ch[now][]] )
now = ch[now][];
else {
int tmp = ( ch[now][] ? siz[ch[now][]] : ) + cnt[now]; if ( x <= tmp )
return key[now];
x -= tmp;
now = ch[now][];
}
}
} inline int pre()
{
int now = ch[root][];
while ( ch[now][] ) now = ch[now][];
return now;
} inline int next()
{
int now = ch[root][];
while ( ch[now][] ) now = ch[now][];
return now;
} inline void del(int x) {
int whatever = find(x);
if (cnt[root]>) { cnt[root]--; return; }
//Only One Point
if (!ch[root][] && !ch[root][]) { clear(root); root = ; return; }
//Only One Child
if (!ch[root][]) {
int oldroot = root; root = ch[root][]; f[root] = ; clear(oldroot); return;
}
else if (!ch[root][]) {
int oldroot = root; root = ch[root][]; f[root] = ; clear(oldroot); return;
}
//Two Children
int leftbig = pre(), oldroot = root;
splay(leftbig);
f[ch[oldroot][]] = root;
ch[root][] = ch[oldroot][];
clear(oldroot);
update(root);
return;
} int main()
{
int n, opt, x;
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
scanf("%d%d", &opt, &x);
switch (opt) {
case : insert(x); break;
case : del(x); break;
case : printf("%d\n", find(x)); break;
case : printf("%d\n", findx(x)); break;
case : insert(x); printf("%d\n", key[pre()]); del(x); break;
case : insert(x); printf("%d\n", key[next()]); del(x); break;
}
} return ;
}
BZOJ 1251(区间翻转和区间增加一个值V)
这份代码比较清晰易懂
https://blog.csdn.net/whai362/article/details/47298133（加了一些注释
/*bzoj 1251 序列终结者
题意：
给定一个长度为N的序列，每个序列的元素是一个整数。要支持以下三种操作：
1. 将[L,R]这个区间内的所有数加上V;
2. 将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1;
3. 求[L,R]这个区间中的最大值;
最开始所有元素都是0。
限制：
N <= 50000, M <= 100000
思路：
伸展树
关键点：
1. 伸展树为左小右大的二叉树，所以旋转操作不会影响树的性质
2. 区间操作为：
int u = select(L - 1), v = select(R + 1);
splay(u, 0); splay(v, u); //通过旋转操作把询问的区间聚集到根的右子树的左子树下
因为伸展树为左小右大的二叉树，旋转操作后的所以对于闭区间[L, R]之间的所有元素都聚集在根的右子树的左子树下
因为闭区间[L, R]，
1) 所以每次都要查开区间(L - 1, R + 1)，
2) 所以伸展树元素1对应的标号为2，
3) 所以node[0]对应空节点，node[1]对应比所以元素标号都小的点，node[2 ~ n + 1]对应元素1 ~ n，node[n + 2]对应比所有元素标号都打的点，其中node[0], node[1], node[n + 2]都是虚节点，不代表任何元素。
*/
#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>
#include <queue>
#include <math.h>
#include <string>
#include <algorithm>
#include <time.h>#define SIGMA_SIZE 26
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) (x&-x)
#define foe(i, a, b) for(int i=a; i<=b; i++)
#define fo(i, a, b) for(int i=a; i<b; i++);
#pragma warning ( disable : 4996 )using namespace std;
typedef long long LL;
inline LL LMax(LL a, LL b) { return a>b ? a : b; }
inline LL LMin(LL a, LL b) { return a>b ? b : a; }
inline LL lgcd(LL a, LL b) { return b == ? a : lgcd(b, a%b); }
inline LL llcm(LL a, LL b) { return a / lgcd(a, b)*b; } //a*b = gcd*lcm
inline int Max(int a, int b) { return a>b ? a : b; }
inline int Min(int a, int b) { return a>b ? b : a; }
inline int gcd(int a, int b) { return b == ? a : gcd(b, a%b); }
inline int lcm(int a, int b) { return a / gcd(a, b)*b; } //a*b = gcd*lcm
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = ;
const double eps = 1e-;
const int inf = 0x3f3f3f3f;
const int maxk = 1e6 + ;
const int maxn = 1e5 + ;#define LS(n) node[(n)].ch[0]
#define RS(n) node[(n)].ch[1]struct Splay {
struct Node {
int fa, ch[];
bool rev;
int val, add, maxx, size;
void init(int _val) {
val = maxx = _val;
size = ;
add = rev = ch[] = ch[] = ;
}
} node[maxn];
int root; ///相当于线段树的pushup和pushdown
void pushUp(int n) {
node[n].maxx = Max(node[n].val, Max(node[LS(n)].maxx, node[RS(n)].maxx));
node[n].size = node[LS(n)].size + node[RS(n)].size + ;
} void pushDown(int n) {
if (n == ) return;
if (node[n].add) {
if (LS(n)) {
node[LS(n)].val += node[n].add;
node[LS(n)].maxx += node[n].add;
node[LS(n)].add += node[n].add;
}
if (RS(n)) {
node[RS(n)].val += node[n].add;
node[RS(n)].maxx += node[n].add;
node[RS(n)].add += node[n].add;
}
node[n].add = ;
}
if (node[n].rev) {
if (LS(n)) node[LS(n)].rev ^= ;
if (RS(n)) node[RS(n)].rev ^= ;
swap(LS(n), RS(n));
node[n].rev = ;
}
} ///kind = 0为左旋
///kind = 1为右旋
void rotate(int n, bool kind) {
int fn = node[n].fa;
int ffn = node[fn].fa;
node[fn].ch[!kind] = node[n].ch[kind];
node[node[n].ch[kind]].fa = fn; node[n].ch[kind] = fn;
node[fn].fa = n; node[ffn].ch[RS(ffn) == fn] = n;
node[n].fa = ffn;
pushUp(fn);
} void splay(int n, int goal) {
while (node[n].fa != goal) {
int fn = node[n].fa;
int ffn = node[fn].fa;
//三连pushDown
pushDown(ffn); pushDown(fn); pushDown(n);
bool rotate_n = (LS(fn) == n);
bool rotate_fn = (LS(ffn) == fn);
if (ffn == goal) rotate(n, rotate_n);
else {
if (rotate_n == rotate_fn) rotate(fn, rotate_fn);
else rotate(n, rotate_n);
rotate(n, rotate_fn);
}
}
pushUp(n);
if (goal == ) root = n;
} ///通过数组中的位置找在树中的位置
int select(int pos) {
int u = root;
pushDown(u);
while (node[LS(u)].size != pos) {
if (pos < node[LS(u)].size)
u = LS(u);
else {
pos -= node[LS(u)].size + ;
u = RS(u);
}
pushDown(u);
}
return u;
} int query(int L, int R) {
int u = select(L - ), v = select(R + );
splay(u, ); splay(v, u); ///通过旋转操作把询问的区间聚集到根的右子树的左子树下
return node[LS(v)].maxx;
} void pushUpdate(int L, int R, int val) {
int u = select(L - ), v = select(R + );
splay(u, ); splay(v, u);
node[LS(v)].val += val;
node[LS(v)].maxx += val;
node[LS(v)].add += val;
} void reverse(int L, int R) {
int u = select(L - ), v = select(R + );
splay(u, ); splay(v, u);
node[LS(v)].rev ^= ;
} ///返回子树的根节点
int build(int L, int R) {
if (L > R) return ;
if (L == R) return L;
int mid = (L + R) >> ;
int r_L, r_R;
LS(mid) = r_L = build(L, mid - );
RS(mid) = r_R = build(mid + , R);
node[r_L].fa = node[r_R].fa = mid;
pushUp(mid);
return mid;
} ///按照数组的下标顺序作为建树依据
///而不是按照数组内的元素大小做依据
void init(int n) {
///0号节点最大值和值都是负无穷
node[].init(-inf); node[].size = ;
node[].init(-inf);
node[n + ].init(-inf);
for (int i = ; i <= n + ; ++i)
node[i].init(); root = build(, n + );
node[root].fa = ; node[].fa = ;
LS() = root;
}
} splay_tree;int main() {
int n, m;
scanf("%d%d", &n, &m);
splay_tree.init(n);
for (int i = ; i < m; ++i) {
int op, l, r, v;
scanf("%d", &op);
if (op == ) {
scanf("%d%d%d", &l, &r, &v);
splay_tree.pushUpdate(l, r, v);
}
else if (op == ) {
scanf("%d%d", &l, &r);
splay_tree.reverse(l, r);
}
else {
scanf("%d%d", &l, &r);
printf("%d\n", splay_tree.query(l, r));
}
}
return ;
}
