题解：P14089 [ICPC 2023 Seoul R] K-Lottery

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define pii pair<int,int>
#define pb push_back 
#define eb emplace_back
#define rep(i,a,b) for (int i=(a);i<=(b);i++) 
#define Rep(i,a,b) for (int i=(a);i>=(b);i--)
using namespace std;
using namespace __gnu_pbds;
namespace fast_IO {
    // fast_IO...
} using namespace fast_IO;
typedef unsigned long long ull;
const int N=1e6+10;
const int p=13331;

int n,m,e[N];
int k,b[N],len;
vector<int> a[N],c[N];
ull fac[N],sum[N];
gp_hash_table<ull,int> mp;
struct node {
	int l,r,cnt,add;
	ull val;
	#define ls u<<1
	#define rs u<<1|1
	#define val(u) (t[u].val)
	#define cnt(u) (t[u].cnt)
	#define add(u) (t[u].add)
}t[N<<2];
void push_up(int u) {
	cnt(u)=cnt(ls)+cnt(rs);
	val(u)=fac[cnt(rs)]*val(ls)+val(rs);
	return ;
}
void push(int u,int x) {
	val(u)+=sum[cnt(u)]*x,add(u)+=x;
	return ;
}
void push_down(int u) {
	if (!add(u)) return ;
	push(ls,add(u)),push(rs,add(u)),add(u)=0;
	return ;
}
void build(int u,int l,int r) {
	t[u].l=l,t[u].r=r;
	if (l==r) return ;
	int mid=l+r>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	return ;
}
void insert(int u,int p,int x) {
	if (t[u].l==t[u].r) {
		val(u)=x,cnt(u)=1;
		return ;
	}
	push_down(u);
	int mid=t[u].l+t[u].r>>1;
	if (p<=mid) insert(ls,p,x);
	else insert(rs,p,x);
	return push_up(u);
}
void del(int u,int p) {
	if (t[u].l==t[u].r) {
		val(u)=cnt(u)=0;
		return ;
	}
	push_down(u);
	int mid=t[u].l+t[u].r>>1;
	if (p<=mid) del(ls,p);
	else del(rs,p);
	return push_up(u);
}
void init() {
	sort(b+1,b+len+1);
	len=unique(b+1,b+len+1)-b-1;
	rep(i,1,m) e[i]=lower_bound(b+1,b+len+1,e[i])-b;
	fac[0]=1;
	rep(i,1,k) fac[i]=fac[i-1]*p;
	rep(i,1,m) sum[i]=sum[i-1]+fac[i-1];
	build(1,1,len);
	return ;
}
void check() {
	if (mp.find(val(1))==mp.end()) return ;
	int idx=mp[val(1)];
	rep(i,1,k) cout<<a[idx][i]<<" ";
	cout<<endl;
	exit(0);
	return ;
}
signed main() {
	cin>>k>>n>>m;
	rep(i,1,n) {
		a[i].resize(k+1);
		c[i].resize(k+1);
		ull tmp=0;
		rep(j,1,k) cin>>a[i][j],c[i][a[i][j]]=j;
		rep(j,1,k) tmp=tmp*p+c[i][j];
		mp[tmp]=i;
	}
	rep(i,1,m) cin>>e[i],b[++len]=e[i];
	init();
	rep(i,1,k) insert(1,e[i],i);
	check();
	rep(i,k+1,m) {
		int lst=i-k;
		del(1,e[lst]);
		push(1,-1);
		insert(1,e[i],k);
		check();
	}
	cout<<0<<endl;
	return (0-0);
}