第二回日本最強プログラマー学生選手権 : F - Max Matrix

F,GとHの難易度差が大きい。
https://atcoder.jp/contests/jsc2021/tasks/jsc2021_f

問題

N要素の整数列AとM要素の整数列Bを考える。初期状態ではいずれの要素も0である。
ここで、1つの要素の値を書き換えるクエリが与えられる。
クエリ毎に、max(A[i],B[j])の総和を求めよ。

解法

まず登場する値は事前に座標圧縮しておく。
A及びBに対し2つずつBITを持って置き、各値を持つ要素がいくつあるか、またその総和はいくつかを管理できるようにしておこう。

値の上書きを直接考えるのは大変なので、A,Bのある値を0に戻す、または0からある値に変えるを別々に考えよう。
上書きの際はこれらを連続して処理すればよい。

例えば0であるAの要素をvにすることを考える。
この場合、総和は、B[j]≦vである要素の分だけ増加する。そこで、そのような要素数がa個、その総和がbなら、全体の総和はv*a-bだけ増加する。
Bの値を変える場合や、A,Bの要素を0に戻す場合も似たような処理で行える。

int N,M,Q;
int T[202020],X[202020],Y[202020];
vector<int> V;
int A[202020],B[202020];

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,20> Anum,Asum,Bnum,Bsum;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	V.push_back(0);
	cin>>N>>M>>Q;
	FOR(i,Q) {
		cin>>T[i]>>X[i]>>Y[i];
		X[i]--;
		V.push_back(Y[i]);
	}
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	Anum.add(0,N);
	Bnum.add(0,M);
	ll sum=0;
	FOR(i,Q) {
		Y[i]=lower_bound(ALL(V),Y[i])-V.begin();
		if(T[i]==1) {
			//del
			x=A[X[i]];
			sum-=Bnum(x)*V[x];
			sum+=Bsum(x);
			Anum.add(x,-1);
			Asum.add(x,-V[x]);
			//add
			x=A[X[i]]=Y[i];
			sum+=Bnum(x)*V[x];
			sum-=Bsum(x);
			Anum.add(x,1);
			Asum.add(x,V[x]);
		}
		else {
			//del
			x=B[X[i]];
			sum-=Anum(x)*V[x];
			sum+=Asum(x);
			Bnum.add(x,-1);
			Bsum.add(x,-V[x]);
			//add
			x=B[X[i]]=Y[i];
			sum+=Anum(x)*V[x];
			sum-=Asum(x);
			Bnum.add(x,1);
			Bsum.add(x,V[x]);
		}
		cout<<sum<<endl;
	}
	
	
}

まとめ

わかってしまえばシンプル。