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

：

$j$ 对 $i$ 的贡献：永远是 $m$ 。
$i$ 对 $j$ 的贡献：设 $x_m$ 为满足下式的最大 $x$ （特别地，如果没有，则设为 $0$ ）。
$<d_x\times t_i,idx_i> \ \le \ <d_{tot}\times t_j,idx_j>\\$
那么贡献就是 $\sum_{i=1}^{x_m} c_i$ 。

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

首先可以对每个点

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

：

我们考虑满足 $pos_j<pos_i\land j<i$ 的 $j$ 对 $i$ 的贡献：

遍历 $x(1\le x\le tot)$ ，那么这一段的贡献部分就是 $c_i\sum_{j} [pos_j\le pre_{i,x}]$ 。

那么可以用数据结构实现 $O(n)$ 次修改和 $O(n\sqrt{s_m})$ 次查询。考虑使用 $O(\sqrt{n})$ 修改、 $O(1)$ 查询的分块来平衡复杂度。
我们考虑 $i$ 对满足 $pos_j>pos_i\land j<i$ 的 $j$ 的贡献：

遍历 $x(1\le x\le tot)$ ，那么这一段的贡献部分就是 $c_i\sum_{j} [pos_i\le pre_{j,x}]$ 。

那么可以用数据结构实现 $O(n\sqrt{s_m})$ 次修改和 $O(n)$ 次查询。考虑使用 $O(1)$ 修改、 $O(\sqrt{n})$ 查询的分块来平衡复杂度。

那么最后前缀累加，记为

res_i

，由于有记重复对于自己的贡献，所以真正的答案

ans_i

应该等于

res_i-im

。

代码

CPP

#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;
}

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

文章操作

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

知识点

分析

代码

相关推荐

评论

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