题解：P11118 [ROI 2024] 无人机比赛 (Day 2)

· · 题解

P11118 [ROI 2024] 无人机比赛 (Day 2)

博客园链接：P11118 [ROI 2024] 无人机比赛 (Day 2) - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

分块。

分析

首先有一个显而易见的贪心：如果一个无人机飞了一段路，而下一段路的长度小于等于这段路，那么它肯定会继续飞。证明也显然。

但是并不那么显而易见的是它的作用：注意到 s_m 的范围只有 1.5\times 10^5，那么如果我们根据上述贪心将一定能够连着飞的段缩起来，那么剩余段数最多只有 O(\sqrt{s_m})（更准确地，是 \sqrt{2\times 1.5\times 10^5} \le 548）。证明可以考虑构造极端情况。

根据上述贪心，我们按 s_i - s_{i-1} 的大小将 s 缩段，设缩完段后总共有 tot 段，第 i 大段开头一小段长度为 d_i，第 i 大段中总共有 c_i 小段。

那么接下来就简单了，我们先按 <t_i,i> 关键字对所有点（无人机，后文统称为点）进行排序，设 idx_i 表示排序后的点 i 在原序列中的位置，pos_i 表示原序列中 i 在排序后序列中的位置。然后考虑它们对彼此的贡献（定义 i 对 j 的贡献为：有几个 i 移动的回合中 j 被传送回去）。假设现在将全部点都加入。

在排序后的序列中，如果 i<j：

现在考虑加入题目的限制，维护一个一个插入的总贡献。

首先可以对每个点 u，求出 x 固定时，满足 <d_x\times t_i,idx_i> \ \le \ <d_{tot}\times t_{pos_u},u>\\ 的最大 i，记为 pre_{u,x}。

然后按原序列顺序遍历 1\sim n，假设现在遍历到 i：

那么最后前缀累加，记为 res_i，由于有记重复对于自己的贡献，所以真正的答案 ans_i 应该等于 res_i-im。

代码

#define Plus_Cat ""
#include<bits/stdc++.h>
#define ll long long
#define Pli pair<ll,int>
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(1.5e5+10),M(547+10);

namespace IOcat {
#define LIM (1<<22)
    char buf[LIM],*ip;

    void In(int &x) {
        x=0;
        static char ch(0);
        while(ch=*ip++,ch<48);
        do x=(x<<1)+(x<<3)+(ch^48);
        while(ch=*ip++,ch>47);
    }

    char pbuf[LIM],*pp;

    void Out(ll x) {
        static int top(0);
        static char st[50];
        do st[++top]=x%10^48,x/=10;
        while(x);
        while(top)*pp++=st[top--];
        *pp++='\n';
    }
} using namespace IOcat;

int n,m,tot;
int t[N],s[M],c[M],idx[N],pos[N];
int pre[N][M];
ll ans;

namespace Divide_Block {
    constexpr int BL(388+10),BN(N/(BL-10)+10);
    int Bl,Bn;
    int st[BN],en[BN],bel[N];
    /*1.Change:O(B),Query:Q(1)*/
    int v1[N],s1[BN];

    void Plus1(int x) {
        FOR(i,x,en[bel[x]])++v1[i];
        FOR(i,bel[x],Bn)++s1[i];
    }

    int Sum1(int x) { return v1[x]+s1[bel[x]-1]; }
    /*2.Change:O(1),Query:Q(B)*/
    ll v2[N],s2[BN];

    void Plus2(int x,ll d) { v2[x]+=d,s2[bel[x]]+=d; }

    ll Sum2(int x) {
        ll ans(0);
        FOR(i,x,en[bel[x]])ans+=v2[i];
        FOR(i,bel[x]+1,Bn)ans+=s2[i];
        return ans;
    }
    /*Build*/
    void Build(const int n) {
        Bl=ceil(sqrt(n)),Bn=(n-1)/Bl+1;
        FOR(i,1,Bn) {
            st[i]=en[i-1]+1,en[i]=min(en[i-1]+Bl,n);
            FOR(j,st[i],en[i])bel[j]=i;
        }
    }
} using namespace Divide_Block;

signed main() {
    /*DE("Input");*/
    fread(buf,1,LIM,stdin),ip=buf,pp=pbuf;
    //n,m
    In(n),In(m);
    //t
    FOR(i,1,n)In(t[i]),idx[i]=i;
    sort(idx+1,idx+n+1,[&](const int &a,const int &b) { return t[a]^t[b]?t[a]<t[b]:a<b; });
    FOR(i,1,n)pos[idx[i]]=i;
    //s
    int lst(0);
    FOR(i,1,m) {
        int cur;
        In(cur);
        if(!tot||cur-lst>s[tot])s[++tot]=cur-lst;
        ++c[tot],lst=cur;
    }
    /*DE("Init");*/
    Build(n);
    FOR(i,1,tot) {
        int it(0);
        FOR(j,1,n) {
            const int &u(idx[j]);
            while(it<n&&Pli((ll)t[idx[it+1]]*s[i],idx[it+1])<=Pli((ll)t[u]*s[tot],u))++it;
            pre[u][i]=it;
        }
    }
    /*DE("Solve & Output");*/
    FOR(i,1,n) {
        //small ones to it
        FOR(j,1,tot)ans+=(ll)Sum1(pre[i][j])*c[j];
        Plus1(pos[i]);
        //it to big ones
        FOR(j,1,tot)Plus2(pre[i][j],c[j]);
        ans+=Sum2(pos[i]);
        //output
        Out(ans-=m);
    }
    fwrite(pbuf,1,pp-pbuf,stdout);
    return 0;
}