题解：CF2230E Minimum Influence

NegetiveEdgeWeight · 2026-06-05 18:44:34 · 题解

我太菜了不会题解区大神们的思路怎么办？？？

数据结构神力。

可以把每个新闻当成平面上的点 (p_i,c_i)，把一个查询 tp_j,tc_j 当成两条直线 x=tp_j 和 y=tc_j。

那么一个查询就会把区域划分成四个部分：

离线处理，按照 tp_j 的值进行升序排序然后做扫描线状物。以文化强度为值域维护两颗值域线段树，分别包含扫描过的点和没扫描到的点。

第一颗值域线段树维护文化强度最小值，第二颗值域线段树维护文化强度、政治强度、两者之和的最小值。

然后就按上面的分讨就做完了。

代码中进行了一定的精细实现。具体参见注释。 :::success[Code] 很难看 qaq

#include<bits/stdc++.h>
#define For(a,b,c) for(int a=(int)b;a<=(int)(c);a++)
#define Fro(a,b,c) for(int a=(int)b;a>=(int)(c);a--)
#define ms(a) memset(a,0,sizeof (a))
#define msinf(a) memset(a,0x3f,sizeof (a))
#define mkp make_pair
#define pb push_back
using namespace std;

// N为最大点数/查询数，C为值域范围（文化强度c的最大值）
constexpr int N=4e5+5,C=1e6+5,MOD=998244353,inf=0x3f3f3f3f;

// trL: 扫描线左侧(p < tp，政治未超标)的线段树，仅维护区间最小的文化强度c
int trL[C<<2];

// trR: 扫描线右侧(p >= tp，政治已超标)的线段树
struct NodeR{
    int mp,my,msum; // mp: 最小的p, my: 最小的c, msum: 最小的(p+c)
}trR[C<<2];

// head, nxt: 用于维护同一种文化强度c下，所有点的静态链表，方便O(1)弹出最小的p
int head[C],nxt[N],cntL[C];

// 新闻点结构体: p为政治强度, c为文化强度
struct Pt{
    int p,c;
}pts[N];

// 查询结构体: tx对应tp(政治容忍度), ty对应tc(文化容忍度), d为缓冲区间
struct Qry{
    int tx,ty,d,id;
}qs[N];
int ansArr[N];

// === 左侧线段树操作 ===
void bldL(int id,int l,int r){
    trL[id]=inf;
    if(l==r)return;
    int mid=(l+r)>>1;
    bldL(id<<1,l,mid);
    bldL(id<<1|1,mid+1,r);
}
void updL(int id,int l,int r,int pos,int val){
    if(l==r){trL[id]=val;return;}
    int mid=(l+r)>>1;
    if(pos<=mid)updL(id<<1,l,mid,pos,val);
    else updL(id<<1|1,mid+1,r,pos,val);
    trL[id]=min(trL[id<<1],trL[id<<1|1]);
}
int qryL(int id,int l,int r,int ql,int qr){
    if(ql>qr)return inf;
    if(ql<=l&&r<=qr)return trL[id];
    int mid=(l+r)>>1,res=inf;
    if(ql<=mid)res=min(res,qryL(id<<1,l,mid,ql,qr));
    if(qr>mid)res=min(res,qryL(id<<1|1,mid+1,r,ql,qr));
    return res;
}

// === 右侧线段树操作 ===
void bldR(int id,int l,int r){
    if(l==r){
        // 若当前c值域没有点，赋为inf；否则取静态链表头部（即该c下p最小的点）的信息
        if(!head[l])trR[id]={inf,inf,inf};
        else{int p=pts[head[l]].p;trR[id]={p,l,p+l};}
        return;
    }
    int mid=(l+r)>>1;
    bldR(id<<1,l,mid);
    bldR(id<<1|1,mid+1,r);
    trR[id].mp=min(trR[id<<1].mp,trR[id<<1|1].mp);
    trR[id].my=min(trR[id<<1].my,trR[id<<1|1].my);
    trR[id].msum=min(trR[id<<1].msum,trR[id<<1|1].msum);
}
void updR(int id,int l,int r,int pos){
    if(l==r){
        if(!head[l])trR[id]={inf,inf,inf};
        else{int p=pts[head[l]].p;trR[id]={p,l,p+l};}
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)updR(id<<1,l,mid,pos);
    else updR(id<<1|1,mid+1,r,pos);
    trR[id].mp=min(trR[id<<1].mp,trR[id<<1|1].mp);
    trR[id].my=min(trR[id<<1].my,trR[id<<1|1].my);
    trR[id].msum=min(trR[id<<1].msum,trR[id<<1|1].msum);
}
NodeR qryR(int id,int l,int r,int ql,int qr){
    if(ql>qr)return {inf,inf,inf};
    if(ql<=l&&r<=qr)return trR[id];
    int mid=(l+r)>>1;
    NodeR res={inf,inf,inf};
    if(ql<=mid){
        NodeR left=qryR(id<<1,l,mid,ql,qr);
        res.mp=min(res.mp,left.mp);
        res.my=min(res.my,left.my);
        res.msum=min(res.msum,left.msum);
    }
    if(qr>mid){
        NodeR right=qryR(id<<1|1,mid+1,r,ql,qr);
        res.mp=min(res.mp,right.mp);
        res.my=min(res.my,right.my);
        res.msum=min(res.msum,right.msum);
    }
    return res;
}

int main(){
    int n,m;
    cin>>n;
    For(i,1,n) cin>>pts[i].p;
    For(i,1,n) cin>>pts[i].c;
    cin>>m;
    For(i,1,m){
        cin>>qs[i].tx;
        qs[i].id=i;
    }
    For(i,1,m) cin>>qs[i].ty;
    For(i,1,m) cin>>qs[i].d;

    // 离线核心：新闻点按p升序，查询点按tx(即tp)升序，构建一维扫描线
    sort(pts+1,pts+1+n,[](const Pt&a,const Pt&b){return a.p<b.p;});
    sort(qs+1,qs+1+m,[](const Qry&a,const Qry&b){return a.tx<b.tx;});

    // 倒序构建静态链表：保证head[c]始终指向当前c对应的新闻集合中，p最小的那一个点
    Fro(i,n,1){
        nxt[i]=head[pts[i].c];
        head[pts[i].c]=i;
    }

    bldL(1,0,C-5);
    bldR(1,0,C-5);
    int ptr=1;

    For(i,1,m){
        // 扫描线推进：当新闻点的p小于当前查询的tp时，它进入了“政治未超标”的左半场
        while(ptr<=n&&pts[ptr].p<qs[i].tx){
            auto [p,c]=pts[ptr];
            // O(1)在右侧树中弹出当前p最小的点，暴露出第二小的点
            head[c]=nxt[head[c]];
            updR(1,0,C-5,c);
            // 记录该c值在左半场出现的次数，首次出现则更新到左侧树中
            if(++cntL[c]==1)
                updL(1,0,C-5,c,c);
            ptr++;
        }

        int tx=qs[i].tx,ty=qs[i].ty,d=qs[i].d,res=inf;

        // 象限1 (左下: p < tp, c < tc)：两项均未超标，若存在点则最小影响力必为0
        if(qryL(1,0,C-5,0,ty-1)!=inf)res=0;

        if(res>0){
            // 象限2 (左上: p < tp, c >= tc)：仅文化超标，总影响力退化为 min(c, tc+d)
            int mc=qryL(1,0,C-5,ty,C-5);
            if(mc!=inf)
                res=min(res,min(mc,ty+d));

            // 象限3 (右下: p >= tp, c < tc)：仅政治超标，总影响力退化为 min(p, tp+d)
            NodeR r3=qryR(1,0,C-5,0,ty-1);
            if(r3.mp!=inf)
                res=min(res,min(r3.mp,tx+d));

            // 象限4 (右上: p >= tp, c >= tc)：双超标，总影响力利用分配律拆开四项分别求 min
            NodeR r4=qryR(1,0,C-5,ty,C-5);
            if(r4.mp!=inf)
                res=min(res,min(r4.msum,min(r4.mp+ty+d,min(r4.my+tx+d,tx+ty+2*d))));
        }
        // 根据离线打乱前的原始id储存答案
        ansArr[qs[i].id]=res;
    }
    For(i,1,m)
        cout<<ansArr[i]<<'\n';
    return 0;
}

::: :::info[AI 使用说明] 使用 Gemini 3.1 Pro 为代码添加注释。保证代码经过人工审查。 :::