一道平衡樹維護區間翻轉的練習題

題意：

給一個長度為 n n n的序列，有兩種操作，将一段區間翻轉，求一段區間允許修改一個值得到的最小方差。

解法：

操作1：直接用splay或fhq-treap維護，在平衡樹上打翻轉标記就可以了

操作2：首先推式子發現方差等于 ∑ a i 2 n − ( ∑ a i ) 2 n 2 \frac{\sum ai^2} {n}-\frac{(\sum ai)^2} {n^2} n∑ai2​−n2(∑ai)2​ r然後欽點一個數并修改它的最優方案就是 2 ∗ ( ∑ a i ) − a p o s ( n − 1 ) 2*\frac{(\sum ai)-apos}{(n-1)} 2∗(n−1)(∑ai)−apos​,其實就是其它數的平均數*2,然後根據感覺，可以發現一定隻可能改最小的或最大的。然後就可以在平衡樹中維護 ∑ a i , ∑ a i 2 , m n , m x \sum ai,\sum ai^2,mn,mx ∑ai,∑ai2,mn,mx就可以維護這些資訊了。

然後處理時主要的細節就是注意維護翻轉資訊。

#include<bits/stdc++.h>
using namespace std;
#define double long double
const int maxn=2e5+5;
inline int read(){
	char c=getchar();int t=0,f=1;
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}
	return t*f;
}
struct node{
	int l,r,rd,sz,rev;
	double sum,mx,mn,val,sum2;
}t[maxn];
int cnt;
inline int newnode(double x){
	cnt++;
	t[cnt].l=t[cnt].r=t[cnt].rev=0;t[cnt].sz=1;
	t[cnt].val=t[cnt].sum=t[cnt].mn=t[cnt].mx=x;
	t[cnt].sum2=x*x;t[cnt].rd=rand();
	return cnt;
}
#define ls t[x].l
#define rs t[x].r
inline void pushup(int x){
	t[x].sum=t[ls].sum+t[rs].sum+t[x].val;
	t[x].sz=t[ls].sz+t[rs].sz+1;
	t[x].mn=t[x].val;
	t[x].mx=t[x].val;
	t[x].sum2=t[ls].sum2+t[rs].sum2+t[x].val*t[x].val;
	if(ls){t[x].mn=min(t[x].mn,t[ls].mn);t[x].mx=max(t[x].mx,t[ls].mx);}
	if(rs){t[x].mn=min(t[x].mn,t[rs].mn);t[x].mx=max(t[x].mx,t[rs].mx);}
}
inline void pushdown(int x){
	swap(ls,rs);
	if(ls)t[ls].rev^=1;
	if(rs)t[rs].rev^=1;
	t[x].rev=0;
}
inline int merge(int x,int y){
	if(t[x].rev)pushdown(x);
	if(t[y].rev)pushdown(y);
	if((!x)||(!y)){return x^y;}
	if(t[x].rd<t[y].rd){
		t[x].r=merge(t[x].r,y);
		pushup(x);return x;
	}
	else{
		t[y].l=merge(x,t[y].l);
		pushup(y);return y;
	}
}
inline void split(int x,int &l,int &r,int k){
	if(!x){l=r=0;return ;}
	if(t[x].rev)
	pushdown(x);
	if(t[ls].sz>=k){
		r=x;
		split(ls,l,ls,k);
	}
	else{
		l=x;
		split(rs,rs,r,k-t[ls].sz-1);
	}
	pushup(x);
}
int q,n,rt,x,y,z,l,r;
double sum2,sum1,len,mx,mn;
double calc(double ai){
	sum1=t[y].sum;sum2=t[y].sum2;
	len=r-l+1;
	sum2-=ai*ai;sum1-=ai;
	ai=2*sum1/(2*len-2);
	sum2+=ai*ai;sum1+=ai;
	return sum2/len-((sum1*sum1)/len/len);
}
void print(int x){
	if(ls)print(ls);
	printf("%.0Lf ",t[x].val);
	if(rs)print(rs);
}
int main(){
	//freopen("c.in","r",stdin);
	//freopen("c.out","w",stdout);
	n=read();q=read();
	for(int i=1;i<=n;i++){
		int x=read();
		rt=merge(rt,newnode(x));
	}
	char s;
	while(q--){
		s=getchar();
		while((s!='q')&&(s!='r'))s=getchar();
		l=read(),r=read();
		split(rt,x,z,r);
		split(x,x,y,l-1);
		if(s=='r'){
			t[y].rev^=1;
		}
		else{
			if(l==r){
				puts("0.000000");
			}
			else{
				mn=t[y].mn;mx=t[y].mx;
				printf("%.6Lf\n",min(calc(mn),calc(mx)));
			}
		}
		rt=merge(x,merge(y,z));
	//	print(rt);
	//	puts("");
	}
	return 0;
}