AtCoder ABC #287 (ユニークビジョンプログラミングコンテスト2023 新春) : G - Balance Update Query

中盤の立ち振る舞いがまずかったな…。
https://atcoder.jp/contests/abc287/tasks/abc287_g

問題

N種類のカードがあり、各種類のカードの得点A[i]と使用可能枚数B[i]が与えられる。
以下のクエリに順次答えよ。

• 1つの種類の得点を変更する
• 1つの種類の使用可能枚数を変更する
• カードを各種類使用可能枚数の範囲で計X枚選ぶとき、得点の総和の最大値

解法

先にカード得点を座標圧縮しておく。
次に以下を高速に算出できるBITをそれぞれ準備する。

• f(n) := 得点n以下のカード枚数
• g(n) := 得点n以下のカードの得点の総和

前者2つのクエリに対しては、BITを適宜更新していけばよい。
3つ目のクエリに対し、カード総枚数をSとすると、カード全体得点の総和から、得点の低い(S-X)枚分の得点を取り除けばよい。
これは前者のBITを二分探索すれば、(S-X)番目に低い得点のカードの得点がわかるので、両BITを使い(S-X)枚分の得点の総和を算出できる。

int N;
ll A[202020],B[202020];
int Q;
ll T[202020],X[202020],Y[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> num,sum;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<int> Xs={0};
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		Xs.push_back(A[i]);
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>T[i];
		if(T[i]==1) {
			cin>>X[i]>>Y[i];
			X[i]--;
			Xs.push_back(Y[i]);
		}
		if(T[i]==2) {
			cin>>X[i]>>Y[i];
			X[i]--;
		}
		if(T[i]==3) {
			cin>>X[i];
		}
	}
	sort(ALL(Xs));
	Xs.erase(unique(ALL(Xs)),Xs.end());
	FOR(i,N) {
		A[i]=lower_bound(ALL(Xs),A[i])-Xs.begin();
		num.add(A[i],B[i]);
		sum.add(A[i],Xs[A[i]]*B[i]);
	}
	FOR(k,Q) {
		if(T[k]==1) {
			i=X[k];
			num.add(A[i],-B[i]);
			sum.add(A[i],-Xs[A[i]]*B[i]);
			A[i]=lower_bound(ALL(Xs),Y[k])-Xs.begin();
			num.add(A[i],B[i]);
			sum.add(A[i],Xs[A[i]]*B[i]);
		}
		if(T[k]==2) {
			i=X[k];
			num.add(A[i],-B[i]);
			sum.add(A[i],-Xs[A[i]]*B[i]);
			B[i]=Y[k];
			num.add(A[i],B[i]);
			sum.add(A[i],Xs[A[i]]*B[i]);
		}
		if(T[k]==3) {
			ll a=X[k];
			ll tot=num(1<<19);
			ll tot2=sum(1<<19);
			if(tot<a) {
				cout<<-1<<endl;
			}
			else {
				ll rem=tot-a;
				x=num.lower_bound(rem);
				y=num(x-1);
				tot2-=sum(x-1);
				tot2-=(rem-y)*Xs[x];
				cout<<tot2<<endl;
			}
			
			
		}
	}
	
}

まとめ

これはだいぶ典型色強い問題な気がする。