【Codeforces 626G】Raffles
贪心，堆。
题目大意：
有 $n$ 个奖池，你有 $t$ 张彩票，要下注到奖池里以获得奖金（你可以不全部下注）。
第 $i$ 个奖池里有 $p_i$ 元的奖金，别人已经在这个奖池下注了 $l_i$ 张彩票了。
你在第 $i$ 个奖池里下注 $k_i$ 张彩票能获得的期望奖金为 $p\times \frac{k_i}{l_i+k_i}$ 元。你下注的张数 $k_i$ 必须满足 $k_i\leq l_i$。
你需要合理地分配你的彩票，使得期望获得的总奖金最多。
有 $q$ 个操作，每个操作给定 $u$，会令 $l_u$ 增加 $1$ 或减少 $1$（保证任意时刻有 $l_i\gt 0$）。
要求执行完每步操作后，回答期望总奖金最高是多少。
题解：
考虑没有修改的情况。
先不管每个奖池的奖金，单独考虑一个奖池。
设奖金都为单位 $1$。我们令 $F(l,k)$ 表示在一个奖池中，原来有 $l$ 张，加入 $k$ 张能获得的期望奖金比加入 $k-1$ 张能获得的期望奖金多多少。
当 $l$ 固定时，$F(l,k)$ 的值是关于 $k$ 单调递减的。
所以对于没有修改的情况，我们可以每次贪心地选择插入一张彩票能增加贡献最多的奖池，插入彩票。可以使用堆来对寻找最大值的过程进行加速。时间复杂度 $O((n+t)\log n)$。
考虑修改 $l_i$ 会产生的影响。如果不改变投注的方案，那么答案的变化量是可以 $O(1)$ 计算的。而如果需要修改投注方案，我们显然是把一张最劣的彩票取回，再投注一张最优的彩票。相当于单点修改，全局最值查询，可以使用线段树/堆/ set 等方法实现。
这样单次修改方案的时间复杂度是 $O(\log n)$ 的，我们需要证明，每次 $l_i$ 变化 $1$，最多只会修改 $1$ 张彩票的投注。我们只考虑 $l_i$ 加 $1$，减 $1$ 可以视为它的逆操作。
从贪心的正确性上看，由于我们 $l_i$ 加 $1$ 只会使奖池 $i$ 的彩票变劣，所以替换的只能是奖池 $i$ 中的彩票。设原来投注 $k$ 张，那么原来最后一张的贡献为 $F(l,k)$，说明所有贡献大于 $F(l,k)$ 的都已经被投注了。现在最后一张的贡献为 $F(l+1,k)$，如果没有 $(F(l+1,k),F(l,k)]$ 之间的贡献，那么这张彩票不会被替换。否则，这个奖池的最后一张的贡献为 $F(l+1,k-1)$，严格大于 $F(l,k)$，因此这个奖池不会再被替换。其他奖池因为已经最优因此也不会再替换。故只修改了 $1$ 张彩票。
所以时间复杂度 $O((n+q+t)\log n)$。
Code：
#include<cstdio>
#include<queue>
typedef long long LL;
using namespace std;
const int N=2e5+6,eps=1e-7;
int n,t,q,L[N],a[N],p[N],tm[N];
int nw;
double ans;
struct data{
double d;int id;
inline bool operator<(const data&rhs)const{return d<rhs.d;}
};
struct info{
double d;int id,tim;
inline bool operator<(const info&rhs)const{return d<rhs.d;}
inline bool operator>(const info&rhs)const{return d>rhs.d;}
};
priority_queue<info>last;
priority_queue<info,vector<info>,greater<info> >your;
inline double calc(int i,const int&dlt=0){
return p[i]*(1.*(a[i]+dlt)/(a[i]+L[i]+dlt)-1.*(a[i]+dlt-1)/(a[i]+L[i]+dlt-1));
}
inline double get(int i){
return p[i]*1.*a[i]/(a[i]+L[i]);
}
void init(){
priority_queue<data>q;
for(int i=1;i<=n;++i)q.push((data){p[i]*1./(1+L[i]),i});
while(nw<t&&!q.empty()){
++nw;
data x=q.top();
q.pop();
ans+=x.d;
++a[x.id];
if(a[x.id]!=L[x.id]){
x.d=calc(x.id,1);
q.push(x);
}
}
for(int i=1;i<=n;++i){
if(a[i])
your.push((info){calc(i),i,0});
if(a[i]<L[i])
last.push((info){calc(i,1),i,0});
}
}
int era=0,add=0;
void update(const int&tim){
while(!your.empty()){
info x=your.top();
your.pop();
if(x.tim!=tm[x.id])continue;
--nw;
ans-=x.d;
tm[x.id]=3*tim-1;
last.push((info){x.d,x.id,3*tim-1});
if(--a[x.id])
your.push((info){calc(x.id),x.id,3*tim-1});
break;
}
while(nw<t&&!last.empty()){
info x=last.top();
last.pop();
if(x.tim!=tm[x.id])continue;
++nw;
ans+=x.d;
tm[x.id]=3*tim;
your.push((info){x.d,x.id,3*tim});
if(++a[x.id]<L[x.id])
last.push((info){calc(x.id,1),x.id,3*tim});
}
}
int main(){
scanf("%d%d%d",&n,&t,&q);
for(int i=1;i<=n;++i)scanf("%d",p+i);
for(int i=1;i<=n;++i)scanf("%d",L+i);
init();
add=t;
for(int T=1;T<=q;++T){
int op,i;
scanf("%d%d",&op,&i);
ans-=get(i);
if(op==1)++L[i];else --L[i];
ans+=get(i);
tm[i]=3*T-2;
if(a[i]>L[i])
ans-=calc(i),--nw,--a[i];
if(a[i]){
your.push((info){calc(i),i,3*T-2});
}
if(a[i]<L[i])
last.push((info){calc(i,1),i,3*T-2});
update(T);
printf("%.12f\n",ans);
}
return 0;
}