CF1618G Trader Problem

· · 题解

写出来感觉和csp-j2021 T4差不多。

具体实现方法：将两个数组放在一起排序后求前缀和，维护一个链表，链表除了记录前一块和后一块之外，还要统计当前块的头和尾。用堆维护两个块之间的距离的集合，对问题离线。

设当前块有 c 个原来是 a 数组里的数字，块的值为当前块最大的 c 个数的和。

当前查询的值大于两个块的距离时，统计答案的变量减去当前两个块的值，合并这两个块，再加上这两个块的值。

具体实现见代码注释。 

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,al,q,ans;
int as[400005];
int qzhv[800005],qzhc[800005];
struct dt{
    int val,c;
}d[800005];
struct qst{//存储问题以离线 
    int rk,qv;
}qs[400005];
struct blk{//链表 
    int lst,nxt;
    int frm,to;
}k[800005];
dt make_dt(int v,int f){
    dt xf;
    xf.val=v;xf.c=f;
    return xf;
}
bool cmp(dt a1,dt a2){return a1.val<a2.val;}
bool qcmp(qst a1,qst a2){return a1.qv<a2.qv;}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;//用以统计相邻块的间隙 
#define gtblock(x) (qzhv[k[x].frm]-qzhv[max(0ll,k[x].frm-qzhc[k[x].frm]+qzhc[k[x].to-1])])//求当前块的最大值 
main(){
    scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=1,u;i<=n;i++){
        scanf("%lld",&u);
        d[i]=make_dt(u,1);
    }
    for(int i=1,u;i<=m;i++){
        scanf("%lld",&u);
        d[i+n]=make_dt(u,0);
    }
    al=n+m;
    sort(d+1,d+1+al,cmp);
    for(int i=1;i<=al;i++){//初始每个块只包含一个元素 
        k[i].frm=k[i].to=i;
        qzhc[i]=qzhc[i-1]+d[i].c;
        qzhv[i]=qzhv[i-1]+d[i].val;//有了前缀和以及每个块统计的头和尾后，可以快速求出块里原来a数组的数的个数和最大的一段 
        ans+=d[i].c*d[i].val;
    }
    for(int i=1;i<al;i++){
        pq.push(make_pair(d[i+1].val-d[i].val,i));//把这个间隙丢进堆里 
        k[i].nxt=i%al+1;//连接链表 
        k[i%al+1].lst=i;
    }
    for(int i=1;i<=q;i++) scanf("%lld",&qs[i].qv),qs[i].rk=i;
    sort(qs+1,qs+1+q,qcmp);
    for(int i=1;i<=q;i++){
        while(!pq.empty()&&pq.top().first<=qs[i].qv){
            int x=pq.top().second;
            pq.pop();
            ans-=gtblock(x);
            ans-=gtblock(k[x].nxt);
            k[k[x].lst].nxt=k[x].nxt;
            k[k[x].nxt].lst=k[x].lst;
            k[k[x].nxt].to=k[x].to;
            ans+=gtblock(k[x].nxt);
        }
        as[qs[i].rk]=ans;
    }
    for(int i=1;i<=q;i++) printf("%lld\n",as[i]);
}