AtCoder ARC #126 : E - Infinite Operations

うーん、実装は軽いが考察・数学パートが難しい。
https://atcoder.jp/contests/arc126/tasks/arc126_e

問題

N要素の整数列Aに対し、以下の手順を繰り返す。

• A[i]+2x≦A[j]、i＜jとなるi,j,x(xは正の実装)を選ぶ
• A[i]にxを加算、A[j]からxを減算し、スコアxを得る。

f(A)を、最適な手順を繰り返した場合に得られるAの総スコアとする。

ここで、Aの1要素を更新するクエリが与えられる。
クエリ毎に、更新後のAに対するf(A)を求めよ。

解法

細かい考察をEditorialに任せるとすると、
g(A) = sum(i＜j)(|A[i]-A[j]|) とすると、f(A)=g(A)/2である。

g(A)をクエリ毎に更新すればよいので、(クエリで登場する値も含め)Aに登場する値を座標圧縮しておき、後は各値の登場頻度とその総和をBITで持っておけば、クエリ毎にO(logN)で求められる。

int N,Q;
ll A[303030];
const ll mo=998244353;
ll X[606060],Y[303030];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<ll,21> num,sum;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	vector<ll> Vs;
	FOR(i,N) {
		cin>>A[i];
		A[i]=(A[i]<<30)+i;
		Vs.push_back(A[i]);
	}
	FOR(i,Q) {
		cin>>X[i]>>Y[i];
		X[i]--;
		Y[i]=(Y[i]<<30)+N+i;
		Vs.push_back(Y[i]);
	}
	
	sort(ALL(Vs));
	Vs.erase(unique(ALL(Vs)),Vs.end());
	
	FOR(i,N) {
		A[i]=lower_bound(ALL(Vs),A[i])-Vs.begin();
		num.add(A[i],1);
		sum.add(A[i],Vs[A[i]]>>30);
	}
	ll tsum=0;
	FOR(i,N) {
		x=num(A[i]);
		y=Vs[A[i]]>>30;
		tsum+=1LL*(x-1)*y%mo;
		tsum-=1LL*(N-x)*y%mo;
	}
	FOR(i,Q) {
		x=X[i];
		y=Vs[A[x]]>>30;
		k=num(A[x]);
		tsum-=1LL*(k-1)*y%mo;
		tsum+=1LL*(N-k)*y%mo;
		tsum+=sum(A[x]-1)%mo;
		tsum-=(sum(1<<20)-sum(A[x]))%mo;
		num.add(A[x],-1);
		sum.add(A[x],-y);
		
		A[x]=lower_bound(ALL(Vs),Y[i])-Vs.begin();
		y=Vs[A[x]]>>30;

		num.add(A[x],1);
		sum.add(A[x],y);

		k=num(A[x]);
		tsum+=1LL*(k-1)*y%mo;
		tsum-=1LL*(N-k)*y%mo;
		tsum-=sum(A[x]-1)%mo;
		tsum+=(sum(1<<20)-sum(A[x]))%mo;
		tsum=(tsum%mo+mo)%mo;
		cout<<tsum*(mo+1)/2%mo<<endl;
		
	}
	
	
}

まとめ

うーん考察パート。