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

 

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

 

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



}