splay

T了后六个点

感觉是弱智问题

#include <cstdio>
#include <cstring>
#define max(A, B) (A < B ? B : A)
#define INF 0x7f7f7f7f

const int MX = 200010;

namespace splay
{
int fa[MX], son[MX][2], key[MX], val[MX], mark[MX], mx[MX], rt, tot;

#define get(x) (son[fa[x]][1] == x)
#define update(x) (mx[x] = max(max(mx[son[x][0]], mx[son[x][1]]), val[x] - key[x]))

inline void push_down(int p)
{
	if (mark[p])
	{
		key[son[p][0]] += mark[p];
		key[son[p][1]] += mark[p];
		mx[son[p][0]] -= mark[p];
		mx[son[p][1]] -= mark[p];
		mark[son[p][0]] += mark[p];
		mark[son[p][1]] += mark[p];
		mark[p] = 0;
	}
	mx[0] = 0;
}

inline void rotate(int x)
{
	if (fa[x] == rt)
	{
		rt = x;
	}
	int ffa = fa[fa[x]], dr = get(x);
	son[ffa][get(fa[x])] = x;
	fa[son[x][not dr]] = fa[x];
	son[fa[x]][dr] = son[x][not dr];
	son[x][not dr] = fa[x];
	fa[fa[x]] = x;
	fa[x] = ffa;
	update(son[x][not dr]);
	update(x);
}

inline void splay(int x, int to = 0)
{
	while (fa[x] != to)
	{
		if (fa[fa[x]] != to)
		{
			rotate(get(x) == get(fa[x]) ? fa[x] : x);
		}
		rotate(x);
	}
}

inline void ins(int k, int v)
{
	if (not rt)
	{
		rt = ++tot;
	}
	else
	{
		int p = rt, pfa;
		while (p)
		{
			pfa = p;
			push_down(p);
			p = son[p][key[p] < k];
		}
		son[pfa][key[pfa] < k] = ++tot;
		fa[tot] = pfa;
	}
	key[tot] = k;
	val[tot] = v;
	update(tot);
	splay(tot);
}

inline int pre(int x)
{
	int p = rt, ret;
	while (p)
	{
		push_down(p);
		if (key[p] < x)
		{
			ret = p;
			p = son[p][1];
		}
		else
		{
			p = son[p][0];
		}
	}
	return ret;
}

inline int nxt(int x)
{
	int p = rt, ret;
	while (p)
	{
		push_down(p);
		if (x < key[p])
		{
			ret = p;
			p = son[p][0];
		}
		else
		{
			p = son[p][1];
		}
	}
	return ret;
}

inline int split(int l, int r)
{
	int p = pre(l);
	splay(p);
	splay(nxt(r), p);
	return son[son[rt][1]][0];
}

inline void add(int l, int r, int v)
{
	int p = split(l, r);
	key[p] += v;
	mx[p] -= v;
	mark[p] += v;
}

inline int query(int l, int r)
{
	return mx[split(l, r)];
}

#undef get
#undef update
}

int s[MX], t[MX];

int main()
{
	int n, ans = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", s + i, t + i);
	}
	splay::ins(-INF, 0);
	splay::ins(INF, 0);
	splay::ins(0, 0);
	for (int i = n, tim; i; i--)
	{
		tim = splay::query(-n, s[i]) + s[i] + t[i];
		splay::add(-n, s[i] - 1, -1);
		ans = max(ans, tim);
		splay::ins(s[i], tim + 1);
	}
	printf("%d", ans);
}