3.3-3.11

一周没发题解了。

我这一周干嘛了呢？

偶尔cf（cf题解过后会补上的）   剩下全都在刷数据结构，主要对splay进行了学习

贴一份我的splay模板吧。（最近的成果）

bzoj1251

splay裸题。。

#include <bits/stdc++.h>
#define N 50010
#define INF 0x7f7f7f7f
using namespace std;

inline int ReadInt()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
int size, sz[N], rt, n, m, id[N], c[N][2], fa[N], rev[N], mx[N], tag[N], v[N];

inline int min(int x, int y)
{
	if(x < y) return x;
	else return y;
}

inline int max(int x, int y)
{
	if(x > y) return x;
	else return y;
}

void push_up(int k)
{
	int l = c[k][0];
	int r = c[k][1];
	mx[k] = max(max(mx[l],mx[r]), v[k]);
	sz[k] = sz[l] + sz[r] + 1;
}

void push_down(int k)
{
	int l = c[k][0];
	int r = c[k][1];
	int t = tag[k];
	if(t)
	{
		tag[k] = 0;
		if(l)
		{
			tag[l] += t;
			mx[l] += t;
			v[l] += t;
		}
		if(r)
		{
			tag[r] += t;
			mx[r] += t;
			v[r] += t;
		}
	}
	if(rev[k])
	{
		rev[k] = 0;
		rev[l] ^= 1;
		rev[r] ^= 1;
		swap(c[k][0],c[k][1]);
	}
}

void rorate(int x, int &k)
{
	int y = fa[x], z = fa[y], l, r;
	if(c[y][0] == x) l = 0;
	else l = 1;
	r = l ^ 1;
	if(y == k) k = x;
	else
	{
		if(c[z][0] == y) c[z][0] = x;
		else c[z][1] = x;
	}
	fa[x] = z;
	fa[y] = x;
	fa[c[x][r]] = y;
	c[y][l] = c[x][r];
	c[x][r] = y;
	push_up(y);
	push_up(x);
}

void splay(int x, int &k)
{
	while(x != k)
	{
		int y = fa[x];
		int z = fa[y];
		if(y != k)
			if(c[y][0] == x ^ c[z][0] == y) rorate(x, k);
			else rorate(y, k);
		rorate(x, k);
	}
}

int find(int x, int rank)
{
	if(tag[x] || rev[x]) push_down(x);
	int l = c[x][0];
	int r = c[x][1];
	if(sz[l] + 1 == rank) return x;
	else if(sz[l] >= rank) return find(l, rank);
	else return find(r, rank - sz[l] - 1);
}

void build(int l, int r, int f)
{
	if(l > r) return;
	int now = id[l], last = id[f];
	if(l == r)
	{
		fa[now] = last;
		sz[now] = 1;
		if(l < f) c[last][0] = now;
		else c[last][1] = now;
		return;
	}
	int mid = (l + r) >> 1;
	now = id[mid];
	build(l, mid - 1, mid);
	build(mid + 1, r, mid);
	fa[now] = last;
	push_up(now);
	if(mid < f) c[last][0] = now;
	else c[last][1] = now;
}

void rever(int l, int r)
{
	int x = find(rt, l);
	int y = find(rt, r + 2);
	splay(x, rt);
	splay(y, c[x][1]);
	int z = c[y][0];
	rev[z] ^= 1;
}

void query(int l, int r)
{
	int x = find(rt, l);
	int y = find(rt, r + 2);
	splay(x, rt);
	splay(y, c[x][1]);
	int z = c[y][0];
	printf("%d\n", mx[z]);
}

void update(int l, int r, int val)
{
	int x = find(rt, l);
	int y = find(rt, r + 2);
	splay(x, rt);
	splay(y, c[x][1]);
	int z = c[y][0];
	tag[z] += val;
	v[z] += val;
	mx[z] += val;
}

int main()
{
	mx[0] = -INF;
	n = ReadInt();
	m = ReadInt();
	for(int i = 1; i <= n + 2; i ++)
		id[i] = ++ size;
	build(1, n + 2, 0);
	rt = (n + 3) >> 1;
	for(int i = 1; i <= m; i ++)
	{
		int f = ReadInt(), l, r, val;
		switch(f)
		{
			case 1:l = ReadInt();r = ReadInt();val = ReadInt();update(l,r,val);break;
			case 2:l = ReadInt();r = ReadInt();rever(l,r);break;
			case 3:l = ReadInt();r = ReadInt();query(l,r);break;
		}
	}
	return 0;
}