Codeforces ECR #065 : F. Scalar Queries

本番Fの方がEよりあっさり通してるな。
https://codeforces.com/contest/1167/problem/F

問題

数列Aが与えられる。
要素はすべて互いに異なる。

L≦Rにおけるf(L,R)を以下のように定義する。

• 部分列A[L..R]を抜き出したものをBとする。Bをソートし、sum(i*B[i])を取った値がf(L,R)となる。

L,Rの全通りにおけるf(L,R)の総和を求めよ。

解法

Aを小さい順に処理していく。
今A[i]を処理するとき、その何倍分が総和に寄与するかを考えよう。

区間[L,R]内にA[i]より小さい値がp個ある場合、(p+1)*A[i]分だけ総和に寄与する。
あとはL,Rをずらしたときのpの総和を求めよう。
これは区間の全要素に同じ値を足せるようなBITを用いて、L,R別々に処理することができる。

int N;
int A[505050];
ll mo=1000000007;
vector<pair<int,int>> V;

template<class V, int ME> class BIT_r {
public:
	V bit[2][1<<ME];
	BIT_r(){clear();};
	void clear() {ZERO(bit);};
	
	void update(int entry, V val0, V val1) {
		entry++;
		while(entry <= 1<<ME) (bit[0][entry-1]+=val0)%=mo, (bit[1][entry-1] += val1)%=mo, entry += entry & -entry;
	}
	V total(int entry) {
		if(entry<0) return 0;
		int e=entry++;
		V v0=0,v1=0;
		while(entry>0) (v0+=bit[0][entry-1])%=mo, (v1+=bit[1][entry-1])%=mo, entry -= entry & -entry;
		return (e*v0+v1)%mo;
	}
	void add(int L, int R, V val) { // add val to L<=x<=R
		update(L,val%mo,mo-val*(L-1)%mo);
		update(R+1,mo-val%mo,val*R%mo);
	}
};
BIT_r<ll,20> lef,ri;

template<class V, int ME> class BIT {
public:
	V bit[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) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> did;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) {
		scanf("%d",&A[i]);
		V.push_back({A[i],i});
	}
	sort(ALL(V));
	ll ret=0;
	FORR(v,V) {
		x=v.second;
		int num=N-x;
		ll mor=did(x);
		ri.add(x,N-1,1);
		ret+=A[x]*(ri.total(N-1)-ri.total(x-1)-mor*num%mo)%mo*(x+1)%mo;
		mor=did(N)-did(x);
		ret+=A[x]*(lef.total(x)-mor*(x+1)%mo)%mo*num%mo;
		lef.add(0,x,1);
		did.add(x,1);
	}
	cout<<(ret%mo+mo)%mo<<endl;
}

まとめ

これ系の問題、Codeforcesでは多いけど最近AtCoderでは少ない気がする…。