线段树区间合并

区间的数出现次数最多的数
地址

struct node{
	int l, r;
	int ms, ls, rs;
	int lval, rval;
	int mid(){return (l+r)/2;}
	int soon(){return l == r;}
	int size() {return (r-l+1);}
}tr[maxn<<2];
int cc[maxn];
void pushup(int rt) {
	tr[rt].ls = tr[rt<<1].ls;
	tr[rt].rs = tr[rt<<1|1].rs;
	tr[rt].lval = tr[rt<<1].lval;
	tr[rt].rval = tr[rt<<1|1].rval;
	tr[rt].ms = max(tr[rt<<1].ms, tr[rt<<1|1].ms);
	if(tr[rt<<1].rval == tr[rt<<1|1].lval) {
		if(tr[rt<<1].ls == tr[rt<<1].size()) tr[rt].ls += tr[rt<<1|1].ls;
		if(tr[rt<<1|1].rs == tr[rt<<1|1].size()) tr[rt].rs += tr[rt<<1].rs;
		tr[rt].ms = max(tr[rt].ms, tr[rt<<1].rs+tr[rt<<1|1].ls);
	}
}
void build(int rt, int l, int r) {
	tr[rt].l = l;tr[rt].r = r;
	if(l == r) {
		scanf("%d", &tr[rt].lval);tr[rt].rval = tr[rt].lval;
		tr[rt].ls = tr[rt].rs = tr[rt].ms = 1;
		return;
	}
	int mid = tr[rt].mid();
	build(rt<<1, l, mid);
	build(rt<<1|1, mid+1, r);
	pushup(rt);
}
int query(int rt, int l, int r) {
	if(tr[rt].l == l && tr[rt].r == r) return tr[rt].ms;
	int mid = tr[rt].mid();
	if(r <= mid) return query(rt<<1, l, r);
	else if(mid<l) return query(rt<<1|1, l, r);
	else {
		if(tr[rt<<1].rval == tr[rt<<1|1].lval) 
			return max(min(tr[rt<<1].rs, mid-l+1)+min(tr[rt<<1|1].ls, r-mid), max(query(rt<<1, l, mid), query(rt<<1|1, mid+1, r)));
		else return max(query(rt<<1, l, mid), query(rt<<1|1, mid+1, r));
	}
}

求区间内最大连续和

struct node{
	int l, r;
	int ls, ms, rs;
	int mid(){return (l+r)/2;}
	int sum;
}tr[maxn<<2];
void build(int rt, int l, int r) {
	tr[rt].l = l;tr[rt].r = r;
	if(l == r){
		scanf("%d", &cc[l]);
		tr[rt].ls = tr[rt].rs = tr[rt].ms = tr[rt].sum = cc[l];
		return;
	}
	int mid = tr[rt].mid();
	build(rt<<1, l, mid);build(rt<<1|1, mid+1, r);
	tr[rt].sum = tr[rt<<1].sum + tr[rt<<1|1].sum;
	tr[rt].ls = max(tr[rt<<1].ls, tr[rt<<1].sum+tr[rt<<1|1].ls);
	tr[rt].rs = max(tr[rt<<1|1].rs, tr[rt<<1|1].sum+tr[rt<<1].rs);
	tr[rt].ms = max(max(tr[rt<<1].ms, tr[rt<<1|1].ms), tr[rt<<1].rs+tr[rt<<1|1].ls);
}
int res, pre;
void query(int rt, int l, int r) {
	if(tr[rt].l >= l && tr[rt].r <= r) {
		res = max(res, max(tr[rt].ms, tr[rt].ls+pre));
		pre = max(pre+tr[rt].sum, tr[rt].rs);
		return;
	}
	int mid = tr[rt].mid();
	if(l<=mid)query(rt<<1, l, r);
	if(mid+1<=r)query(rt<<1|1, l, r);
}