2025_4_28 T3

Evan_Leo_Azir · 2025-04-28 20:53:58 · 题解

属于合格的NOIP T3 ,有下位紫难度 CF 2500左右吧（但也不至于多棘手）

题目中两集合为 A , B

首先观察等式

注意到，\max函数中的两项分别由A与B的集合元素构成，如果要直接维护\max函数的值，状态数显然十分大——为两集合元素数之积，故考虑把式子拆开

思考一下，当\max函数中，我们取出的值为a_x+a_y时，需要满足什么条件？

条件如下

同理，当取出了b_x+b_y时

考虑移项，使等式一边的值来自同一集合，即

此时，为了方便表示，我们设

最终发现，我们可以用h_x比大小，来确定\max最终可以取哪一项

因为题目有多组询问，所以我们要设法维护ans，此时有两种思路，第一是通过上一个ans递推目前的ans，第二种即为采用某些数据结构，直接回答

前者在只有加数自然方便，但遇到删除操作时便束手无策了，故我们采用后者的思路——使用数据结构

很直觉的，我们对于h_x开一颗权值线段数，离线下所有操作后，将h_x离散化，以其作为下标

那对于线段树的每个节点，我们要存什么？

线段树最重要的是合并，即具有结合律——hyh

我们维护当前节点本身可以找出的答案，假设左右儿子为ls,rs，目前pushup的节点为rt,显然有

同样，为了合并，我们还要维护当前节点内最小的a_x,b_x(x\in A),a_y,b_y(y\in B)

所以，这启发我们，对于底层的节点（即 tree_l=tree_r)维护一个set

因为是以h_x作下标的权值线段树，故rs的h_x大于ls的h_x，所以

此时，对于加入或删点，先O(\log q)操作底层的set，再一步步传上来即可

时间复杂度O(q\log q)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+10,inf=1e17+10;
int q,len;
int lisan[maxn];
struct QUE{
    int opt,d,a,b,id,deta;
}que[maxn];
struct SEGMENT_TREE{//0,1指A集合 2,3指B集合,0 2指a,1 3指b 
    int minans; 
    int mi[4];
}tree[maxn<<2];
multiset<int>s[maxn][4];
int read()
{
    int ret=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*w;
}
void pushup(int ret)
{
    for(int i=0;i<4;i++) tree[ret].mi[i]=min(tree[ret<<1].mi[i],tree[ret<<1|1].mi[i]);
    tree[ret].minans=min(tree[ret<<1].minans,tree[ret<<1|1].minans);
    tree[ret].minans=min(tree[ret].minans,min(tree[ret<<1].mi[2]+tree[ret<<1|1].mi[0],
    tree[ret<<1].mi[1]+tree[ret<<1|1].mi[3]));
}
void build(int ret,int l,int r)
{
    tree[ret].minans=inf;
    for(int i=0;i<4;i++) tree[ret].mi[i]=inf;
    if(l==r) {for(int i=0;i<4;i++) s[l][i].insert(inf);}
    else
    {
        int mid=(l+r)>>1;
        build(ret<<1,l,mid);build(ret<<1|1,mid+1,r);
    }
}
void change(int ret,int l,int r,int id)
{
    if(l==r)
    {
        int x=que[id].d?2:0;
        if(que[id].opt)
        {
            s[l][x].insert(que[id].a);
            s[l][x+1].insert(que[id].b);
        }else
        {
            s[l][x].erase(s[l][x].find(que[id].a));
            s[l][x+1].erase(s[l][x+1].find(que[id].b));
        }
        for(int i=0;i<4;i++) tree[ret].mi[i]=*s[l][i].begin();
        tree[ret].minans=min(tree[ret].mi[0]+tree[ret].mi[2],tree[ret].mi[1]+tree[ret].mi[3]);
    }else
    {
        int mid=(l+r)>>1;
        if(que[id].id<=mid) change(ret<<1,l,mid,id);
        else change(ret<<1|1,mid+1,r,id);
        pushup(ret);
    }
}
void inpu()
{
    q=read();
    for(int i=1;i<=q;i++)
    {
        que[i].opt=read(),que[i].d=read(),que[i].a=read(),que[i].b=read();
        que[i].deta=lisan[i]=que[i].d?que[i].b-que[i].a:que[i].a-que[i].b;
    }//操作离线
}
void pre()
{
    sort(lisan+1,lisan+q+1);
    len=unique(lisan+1,lisan+q+1)-lisan-1;
    build(1,1,q);
}//离散化与建树
void deal()
{
    for(int i=1;i<=q;i++)
    {
        que[i].id=lower_bound(lisan+1,lisan+len+1,que[i].deta)-lisan;
        change(1,1,q,i);
        printf("%lld\n",tree[1].minans>(int)4e9?-1:tree[1].minans);
    }
}
void solve()
{
    inpu();
    pre();
    deal();
}
signed main()
{
    int t=1;
    while(t--) solve();
    return 0;
}