2020 Multi-University Training Contest 2---- HDU--6770、Dynamic Convex Hull （离线、分治）

题面：

题意：
有一个四次函数的集合 $f_{i} (x) = (x - a_{i})^{4} + b_{i}$ 。

有以下三种操作
（1） $1$ $a$ $b$ ，往集合中添加新的四次函数 $f_{n + 1} = (x - a)^{4} + b$ ，然后 $n = n + 1$
（2） $2$ $t$ ，从集合中删除 $f_{t} (x)$
（3） $3$ $x$ ，在当前集合中询问 $f_{i} (x)$ 的最小值。

官方题解：

题解：
（1）先考虑证明一下时间复杂度，相当于我们有 $n l o g n$ 个点放在线段树上，每个点只能放在线段树的一个节点上，线段树的一个节点可以放多个点。然后我们对线段树的每个节点进行处理，每个节点处理的时间复杂度是 $O (c n t * l o g (c n t))$ 的， $c n t$ 为线段树上当前节点上面的点数， $\sum c n t = n l o g n$ ，那么总的时间复杂度就是 $O (n l o g^{2} n)$ 的。

（2）我们离线所有操作序列，按照时间建立线段树，每个函数在时间轴上的存在部分一定是一个区间，在线段树上至多对应 $l o g n$ 个区间，将函数在时间轴上的存在部分插入线段树。

对于每个询问，其在时间轴上对应一个点，在线段树上对应一个叶子节点，那么对其有贡献的四次函数 $f$ ，一定在线段树对应叶子节点到根这 $l o g n$ 个节点上。我们将一个询问拆为 $l o g n$ 个询问插入这些节点（最后再取个最小值即可）。

现在对于线段树的每个节点，有若干标记和若干询问。这是一个静态问题。下面考虑怎么在 $n l o g n$ 的时间复杂度内处理线段树的一个节点。

对于每个询问 $x$ ，分别找到 $a_{i} \leq x$ 和 $x \leq a_{i}$ 的最优函数即可。

以 $a_{i} \leq x$ 为例，考虑两个函数 $(x - a_{i})^{4} + b_{i}$ 以及 $(x - a_{j})^{4} + b_{j}$ ，其中 $a_{i} \leq a_{j}$ 。

如果对于当前的 $x_{k}$ 来说， $(x_{k} - a_{i})^{4} + b_{i} > = (x_{k} - a_{j})^{4} + b_{j}$ ，那么对于所有的 $x_{p} > = x_{k}$ ，上式均成立（两个四次函数开口向上，大小相同，只有对称轴和底端点不同）。
即如果 $a_{i}$ 不是 $x_{k}$ 的最优解，那么 $a_{i}$ 不是 $x_{p} > = x_{k}$ 的最优解。即 $x_{p}$ 的最优解 $a_{g}$ 一定 $g > = j$

如果对于当前的 $x_{k}$ 来说， $(x_{k} - a_{i})^{4} + b_{i} < = (x_{k} - a_{j})^{4} + b_{j}$ ，那么对于所有的 $x_{p} < = x_{k}$ ，上式均成立（两个四次函数开口向上，大小相同，只有对称轴和底端点不同）。
即如果 $a_{j}$ 不是 $x_{k}$ 的最优解，那么 $a_{j}$ 不是 $x_{p} < = x_{k}$ 的最优解。即 $x_{p}$ 的最优解 $a_{g}$ 一定 $g < = i$

当 $a_{i} > = x$ 时 ， $a_{i} < = a_{j}$
如果对于当前的 $x_{k}$ 来说， $(x_{k} - a_{i})^{4} + b_{i} < = (x_{k} - a_{j})^{4} + b_{j}$ ，那么对于所有的 $x_{p} < = x_{k}$ ，上式均成立（两个四次函数开口向上，大小相同，只有对称轴和底端点不同）。
即如果 $a_{j}$ 不是 $x_{k}$ 的最优解，那么 $a_{j}$ 不是 $x_{p} < = x_{k}$ 的最优解。即 $x_{p}$ 的最优解 $a_{g}$ 一定 $g < = i$

我们将函数按照 $a$ 从小到大排序，将询问按照 $x$ 从小到大排序，则最优决策具有单调性，可以分治求解。分别求解 $a_{i} \leq x$ 和 $x \leq a_{i}$ 即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=1100;

struct func
{
    ll a,b;
    int l,r;
}f[maxn<<1];

bool cmp1(const func &a,const func &b)
{
    return a.a<b.a;
}

struct node
{
    ll x;
    int id;
}q[maxn];

bool cmp2(const node &a,const node &b)
{
    return a.x<b.x;
}

struct tree
{
    int l,r;
    vector<int>idf,idq;
}t[maxn<<2];

int idf[maxn<<1],idq[maxn];
ll ans[maxn];

void build(int l,int r,int cnt)
{
    t[cnt].l=l,t[cnt].r=r;
    t[cnt].idf.clear();
    t[cnt].idq.clear();
    if(l==r) return ;
    build(l,tmid,lc);
    build(tmid+1,r,rc);
}


void change(int l,int r,int cnt,int k,bool flag)
{
    if(l>r) return ;
    if(!flag) t[cnt].idq.pb(k);
    if(l<=t[cnt].l&&t[cnt].r<=r)
    {
        if(flag) t[cnt].idf.pb(k);
        return ;
    }
    if(l<=t[lc].r) change(l,r,lc,k,flag);
    if(r>=t[rc].l) change(l,r,rc,k,flag);
}

ll fi(ll x)
{
    return x*x*x*x;
}

//ai<=x
void so1(int ql,int qr,int fl,int fr)
{
    if(ql>qr||fl>fr) return ;
    int mid=(ql+qr)>>1,pos=fl;
    ll minn=lnf;
    for(int i=fl;i<=fr;i++)
    {
        if(f[idf[i]].a>q[idq[mid]].x) continue;
        if(fi(q[idq[mid]].x-f[idf[i]].a)+f[idf[i]].b<minn)
            minn=fi(q[idq[mid]].x-f[idf[i]].a)+f[idf[i]].b,pos=i;
    }
    ans[q[idq[mid]].id]=min(ans[q[idq[mid]].id],minn);
    so1(ql,mid-1,fl,pos);
    so1(mid+1,qr,pos,fr);
}

//ai>=x
void so2(int ql,int qr,int fl,int fr)
{
    if(ql>qr||fl>fr) return ;
    int mid=(ql+qr)>>1,pos=fr;
    ll minn=lnf;
    for(int i=fl;i<=fr;i++)
    {
        if(f[idf[i]].a<q[idq[mid]].x) continue;
        if(fi(q[idq[mid]].x-f[idf[i]].a)+f[idf[i]].b<minn)
            minn=fi(q[idq[mid]].x-f[idf[i]].a)+f[idf[i]].b,pos=i;
    }
    ans[q[idq[mid]].id]=min(ans[q[idq[mid]].id],minn);
    so2(ql,mid-1,fl,pos);
    so2(mid+1,qr,pos,fr);
}

void dfs(int cnt)
{
    if(t[cnt].idf.size()>0&&t[cnt].idq.size()>0)
    {
        for(int i=0;i<t[cnt].idf.size();i++)
            idf[i+1]=t[cnt].idf[i];
        for(int i=0;i<t[cnt].idq.size();i++)
            idq[i+1]=t[cnt].idq[i];
        so1(1,t[cnt].idq.size(),1,t[cnt].idf.size());
        so2(1,t[cnt].idq.size(),1,t[cnt].idf.size());
    }
    if(t[cnt].l==t[cnt].r)
    {
        if(t[cnt].idq.size()!=0)
            printf("%lld\n",ans[q[t[cnt].idq[0]].id]==lnf?-1:ans[q[t[cnt].idq[0]].id]);
        return ;
    }
    dfs(lc);
    dfs(rc);
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        int n,m,op,t;
        scanf("%d%d",&n,&m);
        build(1,m,1);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&f[i].a,&f[i].b);
            f[i].l=1,f[i].r=m;
        }
        int cntf=n,cntq=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&op);
            ans[i]=lnf;
            if(op==1)
            {
                ++cntf;
                scanf("%lld%lld",&f[cntf].a,&f[cntf].b);
                f[cntf].l=i,f[cntf].r=m;
            }
            else if(op==2)
            {
                scanf("%d",&t);
                f[t].r=i-1;
            }
            else if(op==3)
            {
                ++cntq;
                scanf("%lld",&q[cntq].x);
                q[cntq].id=i;
            }
        }

        sort(f+1,f+cntf+1,cmp1);
        sort(q+1,q+cntq+1,cmp2);
        for(int i=1;i<=cntf;i++)
            change(f[i].l,f[i].r,1,i,true);
        for(int i=1;i<=cntq;i++)
            change(q[i].id,q[i].id,1,i,false);
        dfs(1);
    }
    return 0;
}