【2025广东省队集训day2】火力全开 做题记录

转化题意：

给定 $n,m,k$，一个长 $n$ 的序列 $a$ 和一个长 $m$ 的二元组序列 $(X_i,Y_i)$，对于每个 $1\le x\le n$，定义 $f(x)$ 为 $\sum\limits_{i>x} a_i$ 加上 $\{Y_i|X_i\ge x\}$ 的前 $k$ 小值的和，求 $f$ 的最小值。

有 $q$ 次修改，每次修改完都要输出 $f$ 的最小值，修改有两种类型：

• 修改某一个 $a_i$；
• 修改某一个二元组；

$1\le n,m,k,q\le 2.5\times 10^5$，$1\le qk\le 5\times 10^5$，输入的所有数是 $[1,10^9]$ 内的正整数。

考虑线段树，每个节点维护区间内 $a$ 的和 $sm_u$，$X_i$ 在区间内的前 $k$ 小的 $Y_i$ $mn_{u,[1,k]}$，$mn_u$ 的前缀和 $pre_{u,[0,k]}$（$pre_{u,0}=0$），区间内 $k=0,1,2,3,\dots ,k$ 的子问题的答案 $f_{u,[0,k]}$。那么 update 的时候有 $f_{ls,i}+pre_{rs,j}+sm_{rs}\to f_{u,i+j}$，最终答案为 $f_{1,k}$。

注意到 $pre_{rs}$ 是凸的，故对于任意 $i,j,k,t$，若 $f_{ls,i}+pre_{rs,j}\le f_{ls,i}+pre_{rs,k}$，则 $f_{ls,i}+pre_{rs,j+t}\le f_{ls,i}+pre_{rs,k+t}$。故 $f_{i+j}$ 的决策点 $i$ 是单调递增的，那么根据决策单调性使用分治优化卷积即可。

时间复杂度 $O(qk\log n\log k)$，代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;

const int S=250005;
const ll inf=1e17;

struct node
{
	int op,x,y,z;
};

int n,m,q,k;
int a[S],b[S],c[S],d[S];
node que[S];
int tot,tmp[S*3];
ll sm[S*3<<2];
vector<int> mn[S*3<<2];
vector<ll> pre[S*3<<2],f[S*3<<2];
ll val[S*3];
multiset<int> st[S*3];

void doit(vector<ll> &h,vector<ll> &f,vector<ll> &g,int l,int r,int kl,int kr)
{
	if(l>r) return;
	int mid=l+r>>1;
	int n=g.size()-1;
	int kx=-1;
	for(int i=max(kl,mid-n);i<=kr&&i<=mid;i++)
	{
		ll pre=f[i]+g[mid-i];
		if(pre<h[mid]) h[mid]=pre,kx=i;
	}
	doit(h,f,g,l,mid-1,kl,kx),doit(h,f,g,mid+1,r,kx,kr);
}

inline void upda(int u)
{
	int ls=u<<1,rs=u<<1|1;
	sm[u]=sm[ls]+sm[rs];
	{// mn & pre
		mn[u].clear();
		int lsz=mn[ls].size(),rsz=mn[rs].size();
		int i=0,j=0;
		while(mn[u].size()<k&&(i<lsz||j<rsz))
		{
			if(i<lsz&&(j==rsz||mn[ls][i]<mn[rs][j]))
				mn[u].push_back(mn[ls][i++]);
			else
				mn[u].push_back(mn[rs][j++]);
		}
		int sz=mn[u].size();
		pre[u].resize(sz+1);
		pre[u][0]=0;
		for(int i=1;i<=sz;i++)
			pre[u][i]=pre[u][i-1]+mn[u][i-1];
	}
	int sz=mn[u].size();
	f[u].resize(sz+1);
	for(int i=0;i<=sz;i++) f[u][i]=inf;
	doit(f[u],f[ls],pre[rs],0,sz,0,f[ls].size()-1);
	for(int i=0;i<=sz;i++) f[u][i]+=sm[rs];
	for(int i=0;i<f[rs].size();i++) f[u][i]=min(f[u][i],f[rs][i]);
}

inline void init(int u,int p)
{
	sm[u]=val[p];
	int sz=min(k,(int)st[p].size());
	mn[u].clear();
	for(int x:st[p])
	{
		mn[u].push_back(x);
		if(mn[u].size()==sz) break;
	}
	pre[u].resize(sz+1);
	pre[u][0]=0;
	for(int i=1;i<=sz;i++)
		pre[u][i]=pre[u][i-1]+mn[u][i-1];
	f[u].resize(sz+1);
	for(int i=0;i<=sz;i++) f[u][i]=pre[u][i];
}

void build(int u,int l,int r)
{
	if(l==r) return init(u,l),void();
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	upda(u);
}

void updp(int u,int l,int r,int p)
{
	if(l==r) return init(u,l),void();
	int mid=l+r>>1;
	if(p<=mid) updp(u<<1,l,mid,p);
	else updp(u<<1|1,mid+1,r,p);
	upda(u);
}

inline ll getans()
{
	ll res=sm[1];
	if(f[1].size()==k+1) res=min(res,f[1][k]);
	return res;
}

int main()
{
	freopen("fire.in","r",stdin);
	freopen("fire.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q>>k;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	for(int i=1;i<=m;i++) cin>>c[i]>>d[i];
	for(int i=1;i<=q;i++) cin>>que[i].op>>que[i].x>>que[i].y>>que[i].z;
	for(int i=1;i<=n;i++) tmp[++tot]=b[i];
	for(int i=1;i<=m;i++) tmp[++tot]=d[i];
	for(int i=1;i<=q;i++) tmp[++tot]=que[i].z;
	sort(tmp+1,tmp+tot+1);
	tot=unique(tmp+1,tmp+tot+1)-tmp-1; 
	for(int i=1;i<=n;i++) b[i]=lower_bound(tmp+1,tmp+tot+1,b[i])-tmp;
	for(int i=1;i<=m;i++) d[i]=lower_bound(tmp+1,tmp+tot+1,d[i])-tmp;
	for(int i=1;i<=q;i++) que[i].z=lower_bound(tmp+1,tmp+tot+1,que[i].z)-tmp;
	for(int i=1;i<=n;i++) val[b[i]]+=a[i];
	for(int i=1;i<=m;i++) st[d[i]].insert(c[i]);
	build(1,1,tot);
	for(int i=1;i<=q;i++)
	{
		int op=que[i].op,x=que[i].x,y=que[i].y,z=que[i].z;
		if(op==1)
		{
			val[b[x]]-=a[x];
			updp(1,1,tot,b[x]);
			a[x]=y,b[x]=z;
			val[b[x]]+=a[x];
			updp(1,1,tot,b[x]);
		}
		else
		{
			st[d[x]].erase(st[d[x]].find(c[x]));
			updp(1,1,tot,d[x]);
			c[x]=y,d[x]=z;
			st[d[x]].insert(c[x]);
			updp(1,1,tot,d[x]);
		}
		// print(1,1,tot);
		cout<<getans()<<'\n';
	}
	return 0;
}