CSAcademy Round #13 : F. Interval Expected Max

本番時間ギリギリに完成したかと思ったら、TLが厳しくて通らず。
https://csacademy.com/contest/round-13/#task/interval-expected-max

問題

N要素の整数列Vが与えられる。

ここにQ個のクエリが与えられる。
各クエリは整数列中の区間を示す。
区間内で(重複を含め)2つの要素を等確率で抜き出すとき、大きい方の値の期待値を求めよ。

解法

平方分割でMo's Algorithmして解く。
区間の長さを1変えるとき、2要素の最大値の総和は以下のように変化する。

区間を1伸ばし、値xが追加される場合、

• xとx未満の要素が選ばれると考えると、x未満の要素の数だけ、2xが加算される。(2xは選び方が順不動なため)
• xとx以上の要素が選ばれると考えると、x以上の要素の数だけ、2*その要素が加算される。(2倍は選び方が順不動なため)
  • 言い換えると、x以上の要素の総和の2倍が加算される。
• 自身が2回選ばれる場合、xが加算される。

BITを用いて、各数値の登場回数とその総和を高速に計算可能にしておくと、上記がO(log(max(V)))で取得できる。
なお、Mo+BITでもこのも大はかなりTLが厳しい。
自分はlong longをintにしたりして細々高性能化して辛うじて通した。

int N,Q;
int V[101010];
int L[101010];
int R[101010];
const int D=400;
vector<pair<int,int>> E[1000];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,18> tot;
BIT<int,18> num;
ll TV,TOT2;
double ret[101010];

void add(int t) {
	TV += 2*(TOT2-tot(t));
	TV += 2LL*num(t)*t+t;
	num.add(t,1);
	tot.add(t,t);
	TOT2+=t;
}
void del(int t) {
	num.add(t,-1);
	tot.add(t,-t);
	TOT2-=t;
	TV -= 2*(TOT2-tot(t));
	TV -= 2LL*num(t)*t+t;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>V[i+1];
	FOR(i,Q) {
		cin>>L[i]>>R[i];
		E[L[i]/D].push_back({R[i],i});
	}
	FOR(i,D) {
		sort(ALL(E[i]));
		x=1;
		y=0;
		TV=TOT2=0;
		ZERO(num.bit);
		ZERO(tot.bit);
		FORR(r,E[i]) {
			j=r.second;
			if(x>y) x=L[j],y=L[j]-1;
			while(y<R[j]) add(V[++y]);
			while(y>R[j]) del(V[y--]);
			while(x<L[j]) del(V[x++]);
			while(x>L[j]) add(V[--x]);
			ret[j]=TV / ((R[j]-L[j]+1.0)*(R[j]-L[j]+1.0));
		}
		
		
	}
	
	FOR(i,Q) _P("%.12lf\n",ret[i]);
}

まとめ

TLもう少しゆるくても良かったのでは…。