题解 P9491 ZHY 的集合

Lynkcat · 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();
    }
}