AtCoder ABC #384 (トヨタ自動車プログラミングコンテスト2024#12) : G - Abs Sum

なんか今回全体的にTLが厳しく感じた。
https://atcoder.jp/contests/abc384/tasks/abc384_g

問題

N要素の2つの整数列A,Bが与えられる。
以下のクエリに答えよ。

• 整数X,Yが与えられる。Aの先頭X要素と、Bの先頭Y要素の組み合わせX*Y通りにおける、差の絶対値の総和を求めよ。

解法

Mo's Algorithmで、X,Yをずらしながら適宜総和の差分を更新していく。

そのため、あらかじめ、AやBの各要素の大小順を求めておく。
BITを4つ使い、Aの先頭X要素やBの先頭Y要素に対し、ある値の範囲における個数と総和を求められるようにしておけば、XやYを1つずらしたときの差分を高速に計算できる。

int N;
ll A[101010],B[101010];
int PA[101010],PB[101010];
int K;
int X[10101],Y[10101];


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<ll,18> Anum,Bnum,Asum,Bsum;
ll ret[101010];

const int DI=350;
vector<pair<pair<int,int>,int>> ev;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<pair<int,int>> Vs;
	FOR(i,N) {
		cin>>A[i];
		Vs.push_back({A[i],i*2});
	}
	FOR(i,N) {
		cin>>B[i];
		Vs.push_back({B[i],i*2+1});
	}
	sort(ALL(Vs));
	FOR(i,2*N) {
		x=Vs[i].second;
		if(x%2==0) PA[x/2]=i;
		else PB[x/2]=i;
	}
	cin>>K;
	FOR(i,K) {
		cin>>X[i]>>Y[i];
		ev.push_back({{X[i]/DI,Y[i]},i});
	}
	sort(ALL(ev));
	int CX=0,CY=0;
	ll sum=0;
	FORR2(a,e,ev) {
		int TX=X[e];
		int TY=Y[e];
		
		while(TX<CX) {
			CX--;
			x=PA[CX];
			ll v=A[CX];
			int over=Bnum(2*N)-Bnum(x);
			int less=Bnum(x);
			sum-=(Bsum(2*N)-Bsum(x))-over*v;
			sum-=less*v-Bsum(x);
			Anum.add(x,-1);
			Asum.add(x,-v);
		}
		while(TX>CX) {
			x=PA[CX];
			ll v=A[CX];
			int over=Bnum(2*N)-Bnum(x);
			int less=Bnum(x);
			sum+=(Bsum(2*N)-Bsum(x))-over*v;
			sum+=less*v-Bsum(x);
			Anum.add(x,1);
			Asum.add(x,v);
			CX++;
		}
		while(TY>CY) {
			x=PB[CY];
			ll v=B[CY];
			int over=Anum(2*N)-Anum(x);
			int less=Anum(x);
			sum+=(Asum(2*N)-Asum(x))-over*v;
			sum+=less*v-Asum(x);
			Bnum.add(x,1);
			Bsum.add(x,v);
			CY++;
		}
		while(TY<CY) {
			CY--;
			x=PB[CY];
			ll v=B[CY];
			int over=Anum(2*N)-Anum(x);
			int less=Anum(x);
			sum-=(Asum(2*N)-Asum(x))-over*v;
			sum-=less*v-Asum(x);
			Bnum.add(x,-1);
			Bsum.add(x,-v);
		}
		ret[e]=sum;
	}
	FOR(i,K) cout<<ret[i]<<endl;
}

まとめ

定数倍最適化をさぼってTLEになるのを繰り返してしまった。