题意:两种类型的魔法,一种火魔法造成x点伤害,另一种电魔法造成x点伤害并使后一次魔法造成伤害翻倍,n(2e5)次操作,每次获得或失去一种魔法,求每次能造成的最大伤害.
用small和big两个set记录较小和较大两部分和,其中big大小等于elec大小,每次插入或删除一个数更新big和small两个set,复杂度为logn;k个电魔法可使k或k-1个魔法伤害翻倍,令sum = sumsmall + sumbig + sumbig,即使较大的k个魔法伤害翻倍的结果;当电魔法存在且火魔法为空时,电魔法只能加倍n-1个魔法,当电魔法最小伤害比火魔法最大伤害还要大时,因为电魔法最多能翻倍k-1个点魔法,所以需要加倍的电魔法最小伤害替换为火魔法的最大伤害
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 1;
int n;
int main(){cin>>n;set<int>small,big;set<int>fire, elec;ll sumbig = 0 , sumsmall = 0;for(int i = 0; i < n; ++i) {int x,y;cin>>x>>y;if(y > 0){(x == 0 ? fire : elec).insert(y);if(big.empty() || y < *big.begin()) {small.insert(y);sumsmall += y;}else {big.insert(y);sumbig += y;}}else {y *= -1;(x == 0 ? fire : elec).erase(y);if(big.count(y))big.erase(y), sumbig -= y;else small.erase(y), sumsmall -= y;;if(fire.count(y))fire.erase(y);else elec.erase(y);}while(big.size() > elec.size()) {sumbig -= *big.begin();sumsmall += *big.begin();small.insert(*big.begin());big.erase(big.begin());}while(big.size() < elec.size()) {sumbig += *small.rbegin();sumsmall -= *small.rbegin();big.insert(*small.rbegin());small.erase(*small.rbegin());}ll ans = sumbig + sumbig + sumsmall;if(elec.size() && (fire.empty() || *elec.begin() > *fire.rbegin())) {ans -= *elec.begin();if(!fire.empty()) {ans += *fire.rbegin(); }}cout << ans <<endl;}
}