E.小A的任务

题解

本题的 版本做法与 CCPC 2023 网络赛 L 题 基本一致。

对于固定的询问 ，在完成前 个 A 类任务的情况下显然应选择 到 中前 小的数。 对应的结果可以将 离散化后用可持久化线段树 查询。

同时，对于固定的 和 ，当 逐渐增加时，由于 对应的 集合严格包含 对应的 集合，因此 对应的第 大也不大于 对应的第 大。即对任意 , ，有 ，即每个 对应的最优 存在决策单调性。

因此可以用决策单调性分治求解。时间复杂度 。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 100000
int i,j,k,n,m,t,mpb[N+50],nb;
int rt[N+50];
ll res[N+50],a[N+50],b[N+50];

struct ST{
	#define md ((l+r)>>1)
	int ls[N*30+50],rs[N*30+50],num[N*30+50],it;
	ll su[N*30+50];
	void add(int &id,int l,int r,int lst,int w){
		id=++it;
		su[id]=su[lst]; num[id]=num[lst];
		ls[id]=ls[lst]; rs[id]=rs[lst];
		if(l==r){
			su[id]+=mpb[w]; num[id]++; 
			return;
		}
		if(w<=md)add(ls[id],l,md,ls[lst],w);
		else add(rs[id],md+1,r,rs[lst],w);
		su[id]=su[ls[id]]+su[rs[id]];
		num[id]=num[ls[id]]+num[rs[id]];
	}
	ll get(int id,int l,int r,int x){
		if(num[id]<x)return 1e18;
		if(num[id]==x)return su[id];
		if(l==r){
			return x*mpb[l];
		}
		if(num[ls[id]]>=x)return get(ls[id],l,md,x);
		return su[ls[id]]+get(rs[id],md+1,r,x-num[ls[id]]);
	}
}st;

void solve(int l,int r,int l1,int r1){
	if(l>r)return;
	int pos=0,i,j,k; ll ans=1e18,t1;
	for(i=l1;i<=r1;i++){
		t1=st.get(rt[i],1,nb,md)+a[i];
		if(t1<=ans){
			ans=t1; pos=i;
		}
	}
	res[md]=ans;
	solve(l,md-1,l1,pos); solve(md+1,r,pos,r1);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>t;
	for(i=1;i<=n;i++){cin>>a[i]; a[i]+=a[i-1];}
	for(i=1;i<=n;i++){cin>>b[i]; mpb[i]=b[i];}
	sort(mpb+1,mpb+n+1); nb=unique(mpb+1,mpb+n+1)-mpb-1;
	for(i=1;i<=n;i++){
		b[i]=lower_bound(mpb+1,mpb+nb+1,b[i])-mpb;
		st.add(rt[i],1,nb,rt[i-1],b[i]);
	}
	solve(1,n,1,n);
	while(t--){
		cin>>k;
		cout<<res[k]<<'\n';
	}
}