【学习笔记】CF626G Raffles-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学习笔记】CF626G Raffles。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

这还是道数据结构题。~~事实上看数据范围就能看出来。~~

类似莫队，考虑在上一个询问的基础上求出答案。

有一个非常显然的结论，每次调整是 $O (1)$ 的。道理非常简单，设 $a_{i,j}$ 表示 $i$ 号奖池第 $j$ 张彩票的贡献，当 $l_i$ 增加 $1$ 时，显然会拿 $i$ 奖池的彩票去换比它更大的，因为 $a'_{i,j-1}>a_{i,j}$ ，那么既然原来的第 $j$ 张换不过，那么改变过后的 $j - 1$ 肯定也换不过，同理 $l_i$ 减少 $1$ 时也最多换一张。

那么直接用线段树就做完了。文章来源地址https://www.toymoban.com/news/detail-433963.html

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
#define db long double
#define cpx complex<db>
using namespace std;
const int N=2e5+5;
int n,m,Q;
ll sz[N],L[N],val[N];
db res;
struct node{
    db min,max;
    int posmin,posmax;
}t[N<<2];
void pushup(int p){
    t[p].max=max(t[p<<1].max,t[p<<1|1].max);
    t[p].posmax=(t[p<<1].max>t[p<<1|1].max)?t[p<<1].posmax:t[p<<1|1].posmax;
    t[p].min=min(t[p<<1].min,t[p<<1|1].min);
    t[p].posmin=(t[p<<1].min<t[p<<1|1].min)?t[p<<1].posmin:t[p<<1|1].posmin;
}
void init(int p,int l){
    t[p].max=(sz[l]<L[l])?(1.0*val[l]*L[l]/(sz[l]+L[l])/(sz[l]+L[l]+1)):-inf;
    t[p].min=sz[l]?(1.0*val[l]*L[l]/(sz[l]+L[l]-1)/(sz[l]+L[l])):inf;
    t[p].posmin=t[p].posmax=l;
}
void build(int p,int l,int r){
    if(l==r){
        init(p,l);
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    pushup(p);
}
db getval(int x){
    return 1.0*sz[x]/(sz[x]+L[x])*val[x];
}
db calcnow(int x){
    return 1.0*val[x]*L[x]/(sz[x]+L[x]-1)/(sz[x]+L[x]);
}
db calcnext(int x){
    return 1.0*val[x]*L[x]/(sz[x]+L[x])/(sz[x]+L[x]+1);
}
void modify(int p,int l,int r,int x,int type){
    if(l==r){
        sz[l]+=type;
        init(p,l);
        return;
    }
    int mid=l+r>>1;
    x<=mid?modify(p<<1,l,mid,x,type):modify(p<<1|1,mid+1,r,x,type);
    pushup(p);
}
void getans(){
    build(1,1,n);
    while(m&&t[1].max>0){
        int x=t[1].posmax;
        modify(1,1,n,x,1);
        m--;
    }
    for(int i=1;i<=n;i++)res+=getval(i);
}
void Add(int x){
    res-=getval(x),L[x]++;
    modify(1,1,n,x,0);
    res+=getval(x);
}
void Move(int x){
    res-=getval(x),L[x]--;
    if(sz[x]>L[x]){
        modify(1,1,n,x,-1);
        m++;
    }
    else modify(1,1,n,x,0);
    res+=getval(x);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++)cin>>val[i];
    for(int i=1;i<=n;i++)cin>>L[i];
    cout.precision(20);
    getans();
    for(int i=1;i<=Q;i++){
        int op,x;
        cin>>op>>x;
        if(op==1)Add(x);
        else Move(x);
        while(m&&t[1].max>0){
            int x=t[1].posmax;
            res-=getval(x);
            modify(1,1,n,x,1);
            res+=getval(x),m--;
        }
        if(sz[x]){
            int y=t[1].posmax;
            if(y!=x&&t[1].max>calcnow(x)){
                res-=getval(x)+getval(y);
                modify(1,1,n,x,-1),modify(1,1,n,y,1);
                res+=getval(x)+getval(y);
            }
        }
        int y=t[1].posmin;
        if(y!=x&&sz[x]<L[x]&&calcnext(x)>t[1].min){
            res-=getval(x)+getval(y);
            modify(1,1,n,x,1),modify(1,1,n,y,-1);
            res+=getval(x)+getval(y);
        }
        cout<<res<<"\n";
    }
}