Codeforces #793 : Div2 F. MCMF?

ややこしい問題設定。
https://codeforces.com/contest/1682/problem/F

問題

N要素の整数列A,Bが与えられる。
部分列A[L,R]、B[L,R]からなるクエリに対し、以下を求めよ。
なお、B[L,R]の和は0である。

以下のグラフを考える。

• B[x]＜0の場合、sourceからx番の頂点に容量-B[x]、コスト0の辺を張る
• B[x]＞0の場合、x番の頂点からsinkに容量B[x]、コスト0の辺を張る
• B[x]＜0、B[y]＞0の対に対し、x番の頂点からy番の頂点に容量無限、コスト|A[x]-A[y]|の辺を張る。

このグラフの最大フローにおける最小コストを求めよ。

解法

B[L,R]の和は0なので、最大フローはB[L,R]中正の値の総和に確定する。
あとはB[x]＞0となるxとB[y]＜0となるyに対し、A[x]、A[y]の小さい順にペアにしていけばよい。

f(x) := A[0,x],B[0,x]を対象としたクエリに対する解
とし、f(R)-f(L-1)を求めればA[L,R]とB[L,R]に対する解になる。
あとはBITを使いf(x)は求めて行こう。

int N,Q;
ll A[302020],B[302020],SB[202020];
ll ret[303030];

ll mo=1000000007;
template<class V, int ME> class BIT_mod {
public:
	V bit[1<<ME];
	BIT_mod(){ZERO(bit);};
	V operator()(int e) { if(e<0) return 0; ll s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s%mo;}
	void add(int e,V v) { e++; while(e<=1<<ME) { bit[e-1]+=v; bit[e-1] -= (bit[e-1]>=mo)?mo:0; e+=e&-e;}}
};
BIT_mod<ll,20> sum,mul;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	FOR(r,2) {
		ZERO(sum.bit);
		ZERO(mul.bit);
		vector<ll> Bs;
		Bs.push_back(0);
		FOR(i,N) {
			SB[i+1]=SB[i]+B[i];
			Bs.push_back(SB[i+1]);
			Bs.push_back(SB[i+1]-B[i]);
		}
		sort(ALL(Bs));
		Bs.erase(unique(ALL(Bs)),Bs.end());
		FOR(i,N) if(B[i]>0) {
			x=lower_bound(ALL(Bs),SB[i+1]-B[i])-Bs.begin();
			y=lower_bound(ALL(Bs),SB[i+1])-Bs.begin();
			sum.add(0,A[i]*B[i]%mo);
			sum.add(x,mo-A[i]*B[i]%mo);
			sum.add(y,mo-A[i]*B[i]%mo);
			
			mul.add(x,mo-2*A[i]%mo);
			mul.add(y,2*A[i]%mo);
			sum.add(x,A[i]*(2*SB[i+1]%mo-B[i])%mo);
			sum.add(y,mo-A[i]*(2*SB[i+1]%mo-B[i])%mo);
		}
		FOR(i,N) {
			x=lower_bound(ALL(Bs),SB[i+1]-B[i])-Bs.begin();
			y=lower_bound(ALL(Bs),SB[i+1])-Bs.begin();
			ret[i]+=sum(x)+SB[i]%mo*mul(x)%mo;
			if(B[i]>0) {
				/*
				cout<<i<<" "<<B[i]<<" "<<SB[i]<<" "<<A[i]<<endl;
				FOR(j,Bs.size()) cout<<" "<<j<<" "<<Bs[j]<<" "<<sum(j)<<" + "<<Bs[j]<<"*"<<mul(j)<<" = "<<(sum(j)+Bs[j]*mul(j))<<endl;
				*/
				
				sum.add(0,mo-A[i]*B[i]%mo);
				sum.add(x,A[i]*B[i]%mo);
				sum.add(y,A[i]*B[i]%mo);

				mul.add(x,2*A[i]%mo);
				mul.add(y,mo-2*A[i]%mo);
				sum.add(x,mo-A[i]*(2*SB[i+1]%mo-B[i])%mo);
				sum.add(y,A[i]*(2*SB[i+1]%mo-B[i])%mo);
			}
		}
		
		FOR(i,N) B[i]=-B[i];
		//FOR(i,N+1) cout<<"!"<<i<<" "<<(ret[i]+mo)%mo<<endl;
		
	}
	
	FOR(i,Q) {
		int L,R;
		cin>>L>>R;
		cout<<((ret[R]-ret[L-1])%mo+mo)%mo<<endl;
	}
	
}

まとめ

ややこしい設定の問題、良く思いつくなぁ。