[bzoj3600]没有人的算术 替罪羊树+线段树

这道题是clj论文里面说到过的，用平衡树维护，对于每一个数赋一个实数值，询问大小时比较实数值就可以了

我们用区间(l,r),那么这个节点的实数值就是(l+r)/2，并且由于平衡树的性质，只要不爆精度就可以O(1)比较出大小（实测这道题不卡精度（黄学长整个1到n区间01就够了））

但是我们插入一个数的时候它经过的一些节点实数值会发生变化，用旋转的平衡树难以实现，由于替罪羊树特殊的性质，它在这里就派上了用场

我个傻X又搞忘替罪羊树怎么写了

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
const int N = 500000 + 5;
#define Alpha 0.8
int goat, pos[N], sta[N], top = 0; double a[N];
struct Data{
	int l, r;
	friend bool operator >  ( Data x, Data y ){ return a[x.l] == a[y.l] ? a[x.r] > a[y.r] : a[x.l] > a[y.l]; }
	friend bool operator == ( Data x, Data y ){ return x.l == y.l && x.r == y.r; }
}d[N];
struct SCT{
	Data val[N];
	int ls[N], rs[N], siz[N], id;
	void build( int &k, int l, int r, double dl, double dr ){
		if( l > r ){ k = 0; return; }
		int mid = l + r >> 1;
		double dm = ( dl + dr ) / 2.0;
		k = sta[mid]; a[k] = dm;
		build( ls[k], l, mid - 1, dl, dm );
		build( rs[k], mid + 1, r, dm, dr );
		siz[k] = siz[ls[k]] + siz[rs[k]] + 1;
	}
	void dfs( int k ){
		if( !k ) return ;
		dfs( ls[k] );
		sta[++top] = k;
		dfs( rs[k] );
	}
	void rebuild( int &k, double dl, double dr ){
		top = 0; dfs( k );
		build( k, 1, top, dl, dr );
	}
	int insert( int &k, double dl, double dr, Data v ){
		double dm = ( dl + dr ) / 2.0; int res;
		if( !k ){ k = ++id; siz[k] = 1; a[k] = dm; val[k] = v; return k; }
		if( val[k] == v ) return k;
		else{
			siz[k]++;
			if( v > val[k] ) res = insert( rs[k], dm, dr, v );
			else res = insert( ls[k], dl, dm, v );
		}
		if( (double)max( siz[ls[k]], siz[rs[k]] ) > (double)siz[k] * Alpha ) goat = k;
		else if( goat ){
			if( goat == ls[k] ) rebuild( ls[k], dl, dm );
			else rebuild( rs[k], dm, dr ); goat = 0;
		}
		return res;
	}
}sct;
int n, m, mx[N<<2], rt;
void modify( int k, int l, int r, int x ){
	if( l == r ){ mx[k] = l; return ; }
	int mid = l + r >> 1;
	if( x <= mid ) modify( k<<1, l, mid, x );
	else modify( k<<1|1, mid + 1, r, x );
	if( a[pos[mx[k<<1]]] >= a[pos[mx[k<<1|1]]] ) mx[k] = mx[k<<1];
	else mx[k] = mx[k<<1|1];
}
int query( int k, int l, int r, int L, int R ){
	if( L <= l && r <= R ) return mx[k];
	int mid = l + r >> 1, res = 0;
	if( L <= mid ) res = query( k<<1, l, mid, L, R );
	if( R >  mid ){
		int x = query( k<<1|1, mid + 1, r, L, R );
		if( a[pos[x]] > a[pos[res]] ) res = x;
	}
	return res;
}
int main(){
	scanf( "%d%d", &n, &m ); a[0] = -1;
	for( int i = 1; i <= n; i++ ) pos[i] = 1;
	sct.insert( rt, 0, 1, (Data){ 0, 0 } );
	for( int i = 1; i <= n; i++ ) modify( 1, 1, n, i );
	for( int i = 1; i <= m; i++ ){
		char opt[5]; int l, r, K;
		scanf( "%s", opt ); scanf( "%d%d", &l, &r );
		if( opt[0] == 'C' ){
			scanf( "%d", &K );
			pos[K] = sct.insert( rt, 0, 1, (Data){ pos[l], pos[r] } );
			if( goat ) sct.rebuild( rt, 0, 1 ), goat = 0;
			modify( 1, 1, n, K );
		}else printf( "%d\n", query( 1, 1, n, l, r ) );
	}
	return 0;
}
/*
5 10
C 1 1 1
C 2 1 2
Q 1 2
C 4 4 4
C 5 5 5
Q 4 5
Q 3 3
C 4 2 3
C 4 4 4
Q 3 4
*/
           

总结

重载运算符一定注意比较的是什么