BZOJ2770 YY的Treap

今天考试题的弱化版。只用求LCA是谁，不用求它的深度。所以直接用线段树找下区间最值就搞定了。然后long的范围有负数坑了一发。

好像在不平衡的平衡树上的题也比较热啊。而且我还做得比较少。是要补一补。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair <int, int> vpr;
typedef pair <bool, vpr> dpr;
struct seg {
	int l, r;
	dpr d;
	seg *ls, *rs;
};
struct query {
	int t, a, b;
};

const int maxn = 400009;

int n, m, vl[maxn], tv;
vpr a[maxn];
query q[maxn];
seg slst[maxn * 3], *sp(slst), *rt;

inline int gpos(int x) {
	return lower_bound(vl, vl + tv, x) - vl;
}

#define midp(p) ((p->l+p->r)>>1)
inline seg* sgtBuild(int l, int r) {
	seg* p(sp ++);
	p-> l = l;
	p-> r = r;
	p-> d = dpr(1, vpr(0, 0));
	if (l + 1 < r) {
		p-> ls = sgtBuild(l, midp(p));
		p-> rs = sgtBuild(midp(p), r);
	}
	return p;
}
inline void sgtChg(seg* p, int p0, dpr v0) {
	if (p-> l + 1 == p-> r)
		p-> d = v0;
	else {
		if (p0 < midp(p))
			sgtChg(p-> ls, p0, v0);
		else 
			sgtChg(p-> rs, p0, v0);
		p-> d = min(p-> ls-> d, p-> rs-> d);
	}
}
inline dpr sgtQry(seg* p, int l, int r) {
	if (p-> l == l && p-> r == r)
		return p-> d;
	else if (r <= midp(p))
		return sgtQry(p-> ls, l, r);
	else if (l >= midp(p))
		return sgtQry(p-> rs, l, r);
	else
		return min(sgtQry(p-> ls, l, midp(p)), sgtQry(p-> rs, midp(p), r));
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d", &n, &m);
	tv = 0;
	for (int i = 0; i < n; ++ i) {
		scanf("%d", &a[i]. second);
		vl[tv ++] = a[i]. second;
	}
	for (int i = 0; i < n; ++ i)
		scanf("%d", &a[i]. first);
	for (int i = 0; i < m; ++ i) {
		char opt[3];
		scanf("%s", opt);
		if (opt[0] == 'I') {
			q[i]. t = 1;
			scanf("%d%d", &q[i]. a, &q[i]. b);
			vl[tv ++] = q[i]. a;
		}
		else if (opt[0] == 'D') {
			q[i]. t = 2;
			scanf("%d", &q[i]. a);
		}
		else {
			q[i]. t = 3;
			scanf("%d%d", &q[i]. a, &q[i]. b);
		}
	}
	sort(vl, vl + tv);
	tv = unique(vl, vl + tv) - vl;
	rt = sgtBuild(0, tv);
	for (int i = 0; i < n; ++ i)
		sgtChg(rt, gpos(a[i]. second), dpr(0, a[i]));
	for (int i = 0; i < m; ++ i)
		if (q[i]. t == 1)
			sgtChg(rt, gpos(q[i]. a), dpr(0, vpr(q[i]. b, q[i]. a)));
		else if (q[i]. t == 2)
			sgtChg(rt, gpos(q[i]. a), dpr(1, vpr(0, 0)));
		else {
			int u(gpos(q[i]. a)), v(gpos(q[i]. b));
			if (u > v)
				swap(u, v);
			printf("%d\n", sgtQry(rt, u, v + 1). second. second);
		}
}