Good Bye 2024: 2025 is NEAR : D. Refined Product Optimality

あまりペースが良くなかった回。
https://codeforces.com/contest/2053/problem/D

問題

整数列A,Bが与えられる。
AまたはBの指定された1要素をインクリメントするクエリが与えられるので、適宜以下に答えよ。

• A,Bを任意に並べ替えられるとき、Prod(min(A[i],B[i]))の最大値を求めよ。

解法

Prod(min(A[i],B[i]))の最大値だが、極力小さなA[i]と小さなB[i]でminを取るのが良い。
結局、A,Bを常にソートした状態を保って置き、積の値を差分更新すればよい。

int T,N,Q;
ll A[202020],B[202020],CA[202020],CB[202020];
const ll mo=998244353;

template<class V, int ME> class BITm {
public:
	V bit[1<<ME];
	BITm(){ for(int i=0;i<1<<ME;i++) bit[i]=1;}
	V operator()(int e) {if(e<0) return 0;V s=1;e++;while(e) (s*=bit[e-1])%=mo,e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) (bit[e-1]*=v)%=mo,e+=e&-e;}
};
BITm<ll,20> bit;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		FOR(i,N) {
			bit.add(i,modpow(bit(i)));
			cin>>A[i];
			CA[i]=A[i];
		}
		FOR(i,N) {
			cin>>B[i];
			CB[i]=B[i];
		}
		sort(CA,CA+N);
		sort(CB,CB+N);
		FOR(i,N) {
			bit.add(i,min(CA[i],CB[i]));
		}
		
		cout<<bit(N-1);
		while(Q--) {
			cin>>x>>y;
			y--;
			if(x==1) {
				i=lower_bound(CA,CA+N,A[y]+1)-CA;
				i--;
				bit.add(i,modpow(min(CA[i],CB[i])));
				CA[i]++;
				A[y]++;
				bit.add(i,min(CA[i],CB[i]));
			}
			else {
				i=lower_bound(CB,CB+N,B[y]+1)-CB;
				i--;
				bit.add(i,modpow(min(CA[i],CB[i])));
				CB[i]++;
				B[y]++;
				bit.add(i,min(CA[i],CB[i]));
			}
			cout<<" "<<bit(N-1);
		}
		cout<<"\n";
		
	}
}

まとめ

これBIT使ってるけどよく見たら要らなかったな。