【题解】[CQOI2012]组装
考虑化为代数的形式，序列(left[a_i ight])表示选取的(i)种类仓库的坐标。
(ans=Sigma(a_i-x)^2,(*))，展开:
(ans=nx^2-2Sigma a_ix+Sigma a_i^2(**))
(*)是二次函数看到没？初中填空题第一题。最小值的对称轴(frac{Sigma a_i}{n})。
至于选取(a_i)，根据(*)贪心选取(a_i)即可,（意思就是选近的）。
考虑用莫队的形式维护(Sigma a_i)和(Sigma a_i^2)，把复杂度降到(O(n))
我们假设仓库在所有点的左侧，我们先把所有颜色最靠左的点选中。
然后仓库慢慢右移
考虑枚举变化点，需要选取的(a_i)变化，当且仅当我们假定的仓库的位置越过了相邻的相同种类的中点(根据(*)式)，把变化的信息记录下来像莫队一样的加入待处理的队列，每次改变直接根据二次函数的性质查询最小值和对称轴就好了。
至于有时候对称轴可能不在我们假定的仓库位置，没关系，我们的目的是取到最小值，只关心(**)式的系数，不关心实际位置。
看不懂解释就看代码就好了，但是那两个式子一定要理解。
复杂度是上限是(sort)导致的，最后的时间复杂度是(O(nlogn))。
考场代码(没开(long) (long)见了三十分祖宗)
#include<bits/stdc++.h>
#define RP(t,a,b) for(register int (t)=(a),edd_=(b);t<=edd_;++t)
#define DRP(t,a,b) for(register int (t)=(a),edd_=(b);t>=edd_;--t)
#define ERP(t,a) for(int t=head[a];t;t=e[t].nx)
#define Max(a,b) ((a)<(b)?(b):(a))
#define Min(a,b) ((a)<(b)?(a):(b))
#define pushup(x) seg[(x)]=seg[(x)<<1]+seg[(x)<<1|1]
#define midd register int mid=(l+r)>>1
#define chek if(R<l||r<L)return
#define TMP template<class ccf>
#define rgt L,R,mid,r,pos<<1|1
#define lef L,R,l,mid,pos<<1
#define all 1,n,1
using namespace std;typedef long long ll;
TMP inline ccf qr(ccf k){
char c=getchar();
ccf x=0;
int q=1;
while(c<48||c>57)q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)x=x*10+c-48,c=getchar();
return q==-1?-x:x;
}
const int maxn=2e4+15;
ll ai2,ai;
vector < int > p[maxn];
struct node{
int id,pos;
inline bool operator < (node x)const{
return pos<x.pos;
}
}data[200005];
struct chd{
double pos;
int col,last,to;
inline bool operator < (chd x)const{
return pos<x.pos;
}
}C[200005];
int ccnt;
int cnt;
double n;
int m;
int t1,t2;
inline void mk(int col,int last,int to,double pos){
ccnt++;
C[ccnt].col=col;C[ccnt].last=last;C[ccnt].to=to;C[ccnt].pos=pos;
}
//就是此处见祖宗 注意upd参数的类型！
//请改为long long
inline void upd(int last,int to){
ai-=last;ai2-=last*last;
ai+=to; ai2+=to*to;
}
inline double f(double x){
return (double)n*x*x-(double)2*ai*x+(double)ai2;
}
double ans,anspos;
int main(){
#ifndef ONLINE_JUDGE
freopen("battle.in","r",stdin);
freopen("battle.out","w",stdout);
#endif
cnt=qr(1);m=qr(1);
n=cnt;
RP(t,1,m){
t1=qr(1);
t2=qr(1);
data[t].pos=t1;
data[t].id=t2;
}
sort(data+1,data+m+1);
RP(t,1,m){
p[data[t].id].push_back(data[t].pos);
}
RP(t,1,cnt){
RP(i,1,p[t].size()-1){
mk(t,p[t][i-1],p[t][i],(p[t][i-1]+p[t][i])/2.0);
}
}
sort(C+1,C+ccnt+1);
RP(t,1,cnt){
ai+=p[t][0];
ai2+=p[t][0]*p[t][0];
}
ans=f(ai/n);
anspos=ai/n;
RP(t,1,ccnt){
upd(C[t].last,C[t].to);
register double psj=ai/n,yyb=f(ai/n);
//if(psj>C[t].pos)
//puts("PSJAKIOI");
//puts("yybAKIOI");
if(yyb<ans||(yyb==ans&&psj<anspos)){
anspos=psj;
ans=yyb;
}
}
printf("%.4lf
",anspos);
return 0;
}
/*
考虑化为代数的形式
ans=Sigma(a_i-x)^2
ans=nx^2-2Sigma a_ix+Sigma a_i^2
二次函数看到没？
考虑用莫队的形式维护Sigma a_i和Sigma a_i^2
考虑枚举断点，显然选取的a_i是会变化的，预处理相同颜色的中点即可。
*/