Codeforces ECR #093 : E. Two Types of Spells

なんとか本番中に全完できた回。
https://codeforces.com/contest/1398/problem/E

問題

色々な呪文があり、その種類は2つに大別される。

• 炎の呪文は、そのパワーがxの時、唱えると相手にxのダメージを与える
• 光の呪文は、そのパワーがxの時、唱えると相手にxのダメージを与える。加えて、次に唱える呪文の威力が倍加される。

今、呪文を覚えたり忘れたりという一連のイベントが与えられる。
各イベントの直後において、手持ちの呪文で与えられる総ダメージの最大値を求めよ。

解法

炎の呪文をa個、光の呪文をb個覚えているとする。
この時、全体で上位b個の呪文をダメージ倍加できる。
ただし、そのb個すべてを光の呪文にすることはできない。

そこで、座標圧縮後BITを使い、手持ちの呪文の上位b個の総和を求められるようにしよう。
ただし、このBITからは手持ちの光の呪文のうちパワー最小値のものは外して置き、光の呪文b個すべてか倍加されることを防ぐ。

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;

int N;
int T[202020],D[202020];
vector<int> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	V.push_back(0);
	FOR(i,N) {
		cin>>T[i]>>D[i];
		if(D[i]>0) V.push_back(D[i]);
	}
	sort(ALL(V));
	set<int> S;
	FOR(i,N) {
		x=lower_bound(ALL(V),abs(D[i]))-V.begin();
		if(D[i]>0) {
			num.add(x,1);
			sum.add(x,D[i]);
			if(T[i]) S.insert(x);
		}
		else {
			num.add(x,-1);
			sum.add(x,D[i]);
			if(T[i]) S.erase(x);
		}
		
		if(S.empty()) {
			cout<<sum(N+1)<<endl;
		}
		else {
			x=*S.begin();
			ll ret=sum(N+1);
			num.add(x,-1);
			sum.add(x,-V[x]);
			
			y=num.lower_bound(num(N+1)-S.size());
			ret+=sum(N+1)-sum(y);
			
			num.add(x,1);
			sum.add(x,V[x]);
			cout<<ret<<endl;
			
		}
		
	}
	
}

まとめ

ちょっと問題文が長め。