P14668 [ICPC 2025 Seoul R] Badge Relay 题解

Iris_Aurora · 2026-01-27 21:27:39 · 题解

过桥问题：

每次过桥都需要提灯，灯只有一盏，每次最多只能两个人一起走，过桥时间为两人分别过桥所需时间的最大值。

求所有人过桥的最短时间。

给定长度为 n 的序列 a，表示每个人过桥的时间，

$1\le n,m\le 2\times 10^5,1\le a_i\le 10^9,1\le l,r\le n$。

断断续续写了两天，不断因为各部分数组重名而修改...最后是捋了两遍才捋顺了。

显然每次向右走一定是 2 个人一起走，向左走一定是 1 个人单独回来，且回来的人一定是当前处在右边的所有人中最快的。

首先第一种策略是快者来回，让所有人中最快的来回接送，每次把一个人送到右边，自己再回来。设共有 k 个人，每个人的耗时是 t_1\le t_2\le...\le t_k，那么此时的总耗时是 (k-2)t_1+\sum_{i=2}^k t_i。

我们可以发现这个策略不总是最优的。如果有两个很慢的人，此时让 1 号来回接送就太慢了，我们可以考虑慢者结伴，加入 2 号来优化这个过程。

具体来说，我们让 1 和 2 先过去，1 回来，再让两个慢的一起过去，最后让 2 把灯送回来。

假设慢的两个人分别为 i,j(i<j)，那么这样的耗时从 t_i+t_j+2t_1 变为 t_j+2t_2+t_1。

移项得到当 t_i>2t_2-t_1 时第二种策略更优。

显然不使用 t_1,t_2 转而使用 t_3 是不优的，即我们一定能由两种策略得到最终的最优答案。

我们令 q=\max\set{i|t_i\le 2t_2-t_1},p=\lfloor\frac{k-q}{2}\rfloor，那么总耗时减少为：

发现任意选择 k 个等价于选择区间中最小的 k 个，我们可以通过可持久化线段树求出 t_1,t_2 和 p，然后显然 (k-p-2)t_1,(2p+1)t_2 和 \sum_{i=3}^{k-2p} t_i 都容易计算（查询单点值、区间 \le 某个数的数量，区间和），我们假设 n,m 同阶，那么可以在 \mathcal{O}(n\log n) 的时间内解决。

然后对于 \sum_{i=0}^{p-1}t_{k-2i}，实际上是求将一段区间内的数排序后，值域上某个区间的奇数位/偶数位的数的和。我们可以很容易用线段树维护，然后对询问做莫队，插入/删除一个数都是 \mathcal{O}(\log n) 的，于是复杂度 \mathcal{O}(n\sqrt{n}\log n)。

发现这样貌似无法优化了，我们发现我们现在是以原区间 [l,r] 为视角在做莫队，找出值域属于 [x,y] 的所有数，于是考虑转换视角。

我们记所有人的时间排过序之后的数组为 t，以值域 [x,y] 为区间，找出所有原始下标属于 [l,r] 的元素，并按照其在 t 中的相对顺序，计算奇数位/偶数位之和。

因为 t 数组是静态且有序的，我们考虑对 t 进行分块，块长为 B。

对于一个询问：

• 对于散块我们暴力计算，遍历 t 中的元素，并将原始下标在 [l,r] 中的加入计算。
• 对于中间的整块，显然我们需要 \mathcal{O}(1) 知道原始下标在 [l,r] 区间内的元素的奇数位/偶数位和。

发现对于整块我们可以预处理，可以用分治做到 \mathcal{O}(B^2)（这个复杂度可以用主定理证，T(n)=2T(\frac{n}{2})+n^2，则 T(n)=n^2(1+\frac12+\frac14+\cdots)\approx 2n^2，所以是 \mathcal{O}(B^2)）。

具体地，solve(dep,l,r) 表示处理的是 t 数组的 [l,r] 区间，显然 t_l\sim t_{mid} 是其中较小的一部分元素，t_{mid+1}\sim t_r 是其中较大的一部分元素，且无论怎么选，左区间里的数都 \le 右区间里的数。

然后我们把区间按照原始下标重新排序，然后记录 pL_{dep,i},pR_{dep,i}（dep 是为了压缩空间）表示按照原始下标的顺序，当前区间的前 i 个元素中，属于左区间/右区间的个数。

那么对于查询区间 (x,y]，它在左区间对应的区间为 (pL_{dep,x},pL_{dep,y}]，右区间对应的区间为 (pR_{dep,x},pR_{dep,y}]，我们令 g_{dep,i,j} 表示 dep 层 (i,j] 区间的答案。

然后合并左右区间即可（我们判断区间长度奇偶来累加奇数位/偶数位和）。

对于询问的 [l,r]，我们对每个块处理 Cnt_{i} 表示这个块中原始下标 \le i 的数的个数，那么 [l,r]（等价于 (l-1,r]） 对应的连续段就是 (Cnt_{l-1},Cnt_r]。

附上代码：

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e5 + 10;
const int MR = 5e2 + 10;

int n,m;
int a[MAXN],ID[MAXN],pos[MAXN],v[MAXN];

struct Qry{
    int l,r,x,y,k;
}q[MAXN],Iter[MAXN];

struct Dat{
    bool op;
    ll Odd,Eve;
}g[11][MR][MR],f[MR][MR],Ans[MAXN];

int B,num;
int id[MAXN],Le[MR],Ri[MR];
int pL[11][MR],pR[11][MR];
int Cnt[MAXN],Ps[MAXN],tot=0; 
ll ans[MAXN];
vector<Qry>E;

Dat operator+(Dat A,Dat B){
    Dat res;
    res.op=A.op^B.op;
    res.Odd=A.Odd+(A.op?B.Eve:B.Odd);
    res.Eve=A.Eve+(A.op?B.Odd:B.Eve);
    return res;
}

int rt[MAXN]; 

struct Segment_Tree{
    int tot=0;
    int Ls[MAXN*40],Rs[MAXN*40];
    struct node{
        int cnt;
        ll sum;
    }t[MAXN*40];
    void update(int &x,int y,int l,int r,int p){
        x=++tot;
        t[x]=t[y],Ls[x]=Ls[y],Rs[x]=Rs[y];
        t[x].cnt++,t[x].sum+=v[p];
        if(l==r) return ;
        int mid=(l+r)>>1;
        if(p<=mid) update(Ls[x],Ls[y],l,mid,p);
        else update(Rs[x],Rs[y],mid+1,r,p);
    } 
    int query_cnt(int x,int l,int r,int L,int R){
        if(!x) return 0;
        if(L<=l&&r<=R) return t[x].cnt;
        int mid=(l+r)>>1;
        if(R<=mid) return query_cnt(Ls[x],l,mid,L,R);
        else if(L>mid) return query_cnt(Rs[x],mid+1,r,L,R);
        else return query_cnt(Ls[x],l,mid,L,R)+query_cnt(Rs[x],mid+1,r,L,R);
    }
    ll query_sum(int x,int l,int r,int L,int R){
        if(!x) return 0;
        if(L<=l&&r<=R) return t[x].sum;
        int mid=(l+r)>>1;
        if(R<=mid) return query_sum(Ls[x],l,mid,L,R);
        else if(L>mid) return query_sum(Rs[x],mid+1,r,L,R);
        else return query_sum(Ls[x],l,mid,L,R)+query_sum(Rs[x],mid+1,r,L,R);
    }
    int find(int x,int y,int l,int r,int k){
        if(l==r) return l;
        int mid=(l+r)>>1,cnt=t[Ls[y]].cnt-t[Ls[x]].cnt;
        if(k<=cnt) return find(Ls[x],Ls[y],l,mid,k);
        else return find(Rs[x],Rs[y],mid+1,r,k-cnt);
    }
}T;

bool cmp(int p,int q){
    return a[p]<a[q];
}

void solve(int dep,int l,int r){
    if(l==r){
        g[dep][0][1]={1,v[l],0};
        return ;
    }
    int mid=(l+r)>>1,len=r-l+1;
    vector<PII>tmp;
    FL(i,l,r) tmp.push_back({ID[i],i});
    sort(tmp.begin(),tmp.end());
    int CntL=0,CntR=0;
    pL[dep][0]=pR[dep][0]=0;
    FL(i,1,len){
        if(tmp[i-1].second<=mid) CntL++;
        else CntR++; 
        pL[dep][i]=CntL,pR[dep][i]=CntR;
    }
    solve(dep+1,l,mid);
    FL(x,0,len) FL(y,x,len) g[dep][x][y]=g[dep+1][pL[dep][x]][pL[dep][y]];
    solve(dep+1,mid+1,r);
    FL(x,0,len) FL(y,x,len) g[dep][x][y]=g[dep][x][y]+g[dep+1][pR[dep][x]][pR[dep][y]];
}

int main(){
    freopen("bridge.in","r",stdin);
    freopen("bridge.out","w",stdout);
    scanf("%d%d",&n,&m);
    FL(i,1,n) scanf("%d",&a[i]),ID[i]=i;
    sort(ID+1,ID+n+1,cmp);
    FL(i,1,n) pos[ID[i]]=i,v[i]=a[ID[i]];
    FL(i,1,n) T.update(rt[i],rt[i-1],1,n,pos[i]);
    FL(i,1,m){
        scanf("%d%d%d%d%d",&q[i].l,&q[i].r,&q[i].x,&q[i].y,&q[i].k);
        int l=lower_bound(v+1,v+n+1,q[i].x)-v;
        int r=upper_bound(v+1,v+n+1,q[i].y)-v-1;
        int L=q[i].l,R=q[i].r,k=q[i].k;
        if(l>r){ans[i]=0;continue;}
        int cnt=T.query_cnt(rt[R],1,n,l,r)-T.query_cnt(rt[L-1],1,n,l,r);
        int prv=(l>1?(T.query_cnt(rt[R],1,n,1,l-1)-T.query_cnt(rt[L-1],1,n,1,l-1)):0);
        k=min(k,cnt),r=T.find(rt[L-1],rt[R],1,n,prv+k);
        if(!k){ans[i]=0;continue;}
        int t1=T.find(rt[L-1],rt[R],1,n,prv+1);
        if(k==1){ans[i]=v[t1];continue;}
        int t2=T.find(rt[L-1],rt[R],1,n,prv+2);
        if(k==2){ans[i]=v[t2];continue;}
        int ps=upper_bound(v+1,v+n+1,2*v[t2]-v[t1])-v-1;
        ps=min(ps,r);
        int p=(ps<r?((T.query_cnt(rt[R],1,n,ps+1,r)-T.query_cnt(rt[L-1],1,n,ps+1,r))/2):0);
        ans[i]=1ll*(k-p-2)*v[t1]+1ll*(2*p+1)*v[t2];
        ps=T.find(rt[L-1],rt[R],1,n,k-2*p+prv);
        if(t2<ps) ans[i]+=(T.query_sum(rt[R],1,n,t2+1,ps)-T.query_sum(rt[L-1],1,n,t2+1,ps));
        if(p) E.push_back({L,R,T.find(rt[L-1],rt[R],1,n,k-2*p+prv+2),r,i});
    }
    B=sqrt(n),num=(n-1)/B+1;
    FL(i,1,n) id[i]=(i-1)/B+1;
    FL(i,1,num) Le[i]=(i-1)*B+1,Ri[i]=i*B;
    Ri[num]=n,tot=0;
    for(int i=0;i<(int)E.size();i++){
        int l=E[i].l,r=E[i].r,x=E[i].x,y=E[i].y;
        if(id[x]+1<=id[y]-1)
            Iter[++tot]={id[x]+1,id[y]-1,l,r,0},Ans[tot]={0,0,0},Ps[i]=tot;
    }
    FL(i,1,num){
        int l=Le[i],r=Ri[i],len=r-l+1;
        FL(j,1,n) Cnt[j]=0;
        FL(j,l,r) Cnt[ID[j]]++;
        FL(j,1,n) Cnt[j]+=Cnt[j-1];
        solve(1,l,r);
        FL(j,0,len) FL(k,j,len) f[j][k]=g[1][j][k];
        FL(j,1,tot)
            if(Iter[j].l<=i&&i<=Iter[j].r)
                Ans[j]=Ans[j]+f[Cnt[Iter[j].x-1]][Cnt[Iter[j].y]]; 
    }
    for(int i=0;i<(int)E.size();i++){
        int l=E[i].l,r=E[i].r,x=E[i].x,y=E[i].y,Id=E[i].k,op=1;
        if(id[x]==id[y]){
            FL(j,x,y)
                if(l<=ID[j]&&ID[j]<=r)
                    ans[Id]+=op*v[j],op^=1;
            continue;
        }
        FL(j,x,Ri[id[x]])
            if(l<=ID[j]&&ID[j]<=r)
                ans[Id]+=op*v[j],op^=1;
        if(Ps[i]){
            if(op) ans[Id]+=Ans[Ps[i]].Odd;
            else ans[Id]+=Ans[Ps[i]].Eve;
            op^=Ans[Ps[i]].op;
        }
        FL(j,Le[id[y]],y)
            if(l<=ID[j]&&ID[j]<=r)
                ans[Id]+=op*v[j],op^=1;
    }
    FL(i,1,m) printf("%lld\n",ans[i]);
}