题解：P14109 [ZJCPC 2017] Card Game

· · 题解

思路

先考虑没有插入删除咋做，发现 \min(rx+b) 是凸的，直接三分加李超即可。

然后有插入删除也是不难的，直接线段树分治就行了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
int read(){int p=0,flg=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') flg=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*flg;}
int T,n,m,cnt,pcnt,vis[50010],ans[50010];array<int,2>lim[500010];vector<int>e[200010];struct seg{int ls,rs,u;}t[5000010];struct line{int k,b;}p[100010];
int calc(int u,int x){if(!u) return 1e18;return p[u].k*x+p[u].b;}
void ins(int &now,int l,int r,int u){
    int tmp=now;t[now=++cnt]=t[tmp];if(!t[now].u){t[now].u=u;return ;}if(l==r) return; int mid=(l+r)>>1;
    if(calc(u,mid)<calc(t[now].u,mid)) swap(u,t[now].u);
    if(calc(u,l)<calc(t[now].u,l)) ins(t[now].ls,l,mid,u);
    if(calc(u,r)<calc(t[now].u,r)) ins(t[now].rs,mid+1,r,u);
}
int query(int now,int l,int r,int x){
    if(!now) return 1e18;if(l==r) return calc(t[now].u,x);
    int mid=(l+r)>>1;if(x<=mid) return min(calc(t[now].u,x),query(t[now].ls,l,mid,x));else return min(calc(t[now].u,x),query(t[now].rs,mid+1,r,x));
}
#define lson now<<1
#define rson now<<1|1
void ins(int now,int l,int r,int L,int R,int v){
    if(L<=l&&r<=R){e[now].push_back(v);return ;}
    int mid=(l+r)>>1;if(L<=mid) ins(lson,l,mid,L,R,v);if(mid<R) ins(rson,mid+1,r,L,R,v);
}
void solve(int now,int l,int r,int rt){
    int tmp=cnt;for(auto i:e[now]) ins(rt,-1e9,1e9,i);e[now].clear();
    if(l==r){
        if(vis[l]){
            int L=lim[l][0],R=lim[l][1];while(L<R){int mid=(L+R)>>1;if(query(rt,-1e9,1e9,mid)<query(rt,-1e9,1e9,mid+1)) L=mid+1;else R=mid;}
            ans[l]=query(rt,-1e9,1e9,L);
        }cnt=tmp;return ;
    }int mid=(l+r)>>1;solve(lson,l,mid,rt);solve(rson,mid+1,r,rt);cnt=tmp;
}
void solve(){
    n=read();m=read();cnt=pcnt=0;map<array<int,2>,int>cnt,lst;for(int i=1;i<=n;i++){int x=read(),y=read();cnt[{x,y}]++;lst[{x,y}]=0;}
    for(int i=1;i<=m;i++){
        int op=read(),x=read(),y=read();vis[i]=0;if(!op) lim[i]={x,y},vis[i]=1;else if(op==1){if(!cnt[{x,y}]) lst[{x,y}]=i;cnt[{x,y}]++;}
        else{p[++pcnt]={x,y};cnt[{x,y}]--;if(!cnt[{x,y}]) ins(1,0,m,lst[{x,y}],i-1,pcnt),lst.erase({x,y});}
    }for(auto i:lst) p[++pcnt]={i.first[0],i.first[1]},ins(1,0,m,i.second,m,pcnt);
    solve(1,0,m,0);for(int i=1;i<=m;i++) if(vis[i]) cout<<ans[i]<<'\n';
}
signed main(){
    T=read();while(T--) solve();
    return 0;
}