自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 22:48:51，当前版本为作者最后更新于2023-07-30 23:52:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑算一下贡献。

当集合 $S_i$ 与 $S_j$ 进行归并的时候，当且仅当 $S_{i,k}< S_{j,m-k+1}$ 时 $S_{i,k}$ 会算进答案里。

于是枚举 $k$，用 BIT 维护 $S_{j,m-k+1}$ 来动态算 $S_{i,k}$ 的贡献与 $S_{j,m-k+1}$ 的贡献，所以总时间复杂度 $O(qm\log n)$。

下面提供了 $O(qm\log nm)$ 的代码，不难通过精细实现做到 $O(qm\log n)$。

// Problem: T350821 ZHY 的集合
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T350821?contestId=117064
// Memory Limit: 256 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
#define N 2000005
using namespace std;
int n,m,q,lst[20005],a[20005][105];
int id[20005];
int tmp[N],ans[N];
namespace BIT
{
	int tr[N],tr1[N];
	inline void upd(int x,int y,int z){while (x<N){tr[x]+=y;tr1[x]+=z;x+=x&-x;}}
	inline int qry(int x){int res=0;while(x){res+=tr[x];x-=x&-x;}return res;}
	inline int qry1(int x){int res=0;while(x){res+=tr1[x];x-=x&-x;}return res;}
}
void BellaKira()
{
	cin>>n>>m>>q;
	poly g;
	for (int i=1;i<=n;i++)
	{
		lst[i]=0;
		for (int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			g.push_back(a[i][j]);
		}
		sort(a[i]+1,a[i]+m+1);
		id[i]=i;
	}
	for (int i=n+1;i<=n+q;i++)
	{
		cin>>lst[i];
		int x=lst[i];
		lst[i]=id[lst[i]];
		for (int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			g.push_back(a[i][j]);
		}
		sort(a[i]+1,a[i]+m+1);
		id[x]=i;
	}
	sort(g.begin(),g.end());
	g.erase(unique(g.begin(),g.end()),g.end());
	for (int i=1;i<=n+q;i++)
		for (int j=1;j<=m;j++) a[i][j]=lower_bound(g.begin(),g.end(),a[i][j])-g.begin()+1;
	for (int t=1;t<=m;t++)
	{
		// cout<<"!!"<<t<<endl;
		for (int i=1;i<=n;i++)
		{
			tmp[i]=tmp[i-1];
			// cout<<"?"<<a[i][t]<<endl;
			tmp[i]+=BIT::qry1(a[i][t]-1);
			tmp[i]+=(BIT::qry(N-1)-BIT::qry(a[i][t]-1))*g[a[i][t]-1];
			// cout<<"?"<<i<<" "<<BIT::qry(a[i][t])<<endl;
			BIT::upd(a[i][m-t+1],1,g[a[i][m-t+1]-1]);
		}
		// cout<<"??"<<tmp[n]<<endl;
		// cout<<"!!"<<t<<endl;
		for (int i=n+1;i<=n+q;i++)
		{
			tmp[i]=tmp[i-1];
			BIT::upd(a[lst[i]][m-t+1],-1,-g[a[lst[i]][m-t+1]-1]);
			tmp[i]-=BIT::qry1(a[lst[i]][t]-1);
			tmp[i]-=(BIT::qry(N-1)-BIT::qry(a[lst[i]][t]-1))*g[a[lst[i]][t]-1];


			tmp[i]+=BIT::qry1(a[i][t]-1);
			tmp[i]+=(BIT::qry(N-1)-BIT::qry(a[i][t]-1))*g[a[i][t]-1];
			BIT::upd(a[i][m-t+1],1,g[a[i][m-t+1]-1]);
		}
		for (int i=1;i<=n+q;i++) ans[i]+=tmp[i];
		
		for (int i=1;i<=n;i++)
			BIT::upd(a[i][m-t+1],-1,-g[a[i][m-t+1]-1]);
		for (int i=n+1;i<=n+q;i++)
		{
			BIT::upd(a[lst[i]][m-t+1],1,g[a[lst[i]][m-t+1]-1]);
			BIT::upd(a[i][m-t+1],-1,-g[a[i][m-t+1]-1]);
		}
	}
	for (int i=n;i<=n+q;i++) cout<<ans[i]<<'\n';
			
			
	
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}