题：https://codeforces.com/contest/1398/problem/E
题意：有俩种攻击类型，第一种为tp=0的攻击，只造成d[i]的伤害，第二种为tp=1的攻击，造成d[i]的伤害同时使下次攻击造成的伤害值加倍。当d[i]>0时表示学习了此技能，否则表示忘记了此技能，问n次操作每次操作后能造成的最大伤害值是多少。
分析：其实只要考虑加倍哪些就行，那么当然，肯定使加倍前k个大的（k这里是指由k个tp=1类型的技能），此外若前k个大的全是tp=1，那么肯定至少有一个没有加倍到，那么对于这种情况，我们每次统计时只要把tp=1攻击造成伤害值最小的去掉，然后计算出前k大的和即可，用线段树维护sum（区间和，没有tp的区别），num1（全部攻击的个数，没有tp的区别），num2（tp==1的个数）
#include<bits/stdc++.h> using namespace std; #define lson root<<1,l,midd #define rson root<<1|1,midd+1,r #define pb push_back #define ull unsigned long long #define pii pair<int,int> #define MP make_pair typedef long long ll; const ll INF=1e18; const int inf=0x3f3f3f3f; const int M=1e6+6; struct node{ ll sum,num1,num2; }tr[M<<2]; int tp[M]; ll tmp[M],d[M]; void build(int root,int l,int r){ tr[root].sum=tr[root].num1=tr[root].num2=0; if(l==r) return ; int midd=(l+r)>>1; build(lson); build(rson); } void up(int root){ tr[root].sum=tr[root<<1].sum+tr[root<<1|1].sum; tr[root].num1=tr[root<<1].num1+tr[root<<1|1].num1; tr[root].num2=tr[root<<1].num2+tr[root<<1|1].num2; } void update(int pos,ll v1,ll v2,int root,int l,int r){ if(l==r){ tr[root].sum+=v1*tmp[l]; tr[root].num1+=v1; tr[root].num2+=v2; return ; } int midd=(l+r)>>1; if(pos<=midd) update(pos,v1,v2,lson); else update(pos,v1,v2,rson); up(root); } int querymin(int root,int l,int r){ if(l==r) return l; int midd=(l+r)>>1; if(tr[root<<1].num2) return querymin(lson); else return querymin(rson); } ll querysum(int k,int root,int l,int r){ if(k==0) return 0; if(tr[root].num1<=k) return tr[root].sum; if(l==r) return 1ll*k*tmp[l]; int midd=(l+r)>>1; if(tr[root<<1|1].num1>=k) return querysum(k,rson); else return tr[root<<1|1].sum+querysum(k-tr[root<<1|1].num1,lson); } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%lld",&tp[i],&d[i]),tmp[i]=abs(d[i]); sort(tmp+1,tmp+1+n); int light=0; int m=unique(tmp+1,tmp+1+n)-tmp-1; build(1,1,m); for(int i=1;i<=n;i++){ int pos=lower_bound(tmp+1,tmp+1+m,abs(d[i]))-tmp; ll val1=1,val2=0; if(d[i]<0) val1=-1; if(tp[i]==1){ if(d[i]<0) val2=-1,light--;///light个数 else val2=1,light++; } update(pos,val1,val2,1,1,m); ll ans=tr[1].sum; if(light!=0){ int minpos=querymin(1,1,m); update(minpos,-1,0,1,1,m); ans+=querysum(light,1,1,m); update(minpos,1,0,1,1,m); } printf("%lld ",ans); } return 0; }