#P14861. [OOI2025 资格赛]Distinctive Features独特特征

    ID: 14077 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-扫描线查询排序树状数组局部离散化

[OOI2025 资格赛]Distinctive Features独特特征

题目描述

你正在开发一个系统,用来辅助智能手机商店中的顾问。

商店中所有智能手机排成一行,按摆放顺序从 11 到 nn 编号。每台智能手机都具有若干“独特特征”,例如耐用性、大电池等。一共有 mm 种不同的独特特征,编号为 11 到 mm。

顾问最常被问到的问题是:这台手机与旁边的手机有什么不同?我们将这个问题形式化如下:

给定一段编号从 lil_i 到 rir_i 的手机区间,以及其中某台手机的编号 pip_i(li≤pi≤ril_i\le p_i\le r_i),请确定有多少种独特特征存在于手机 pip_i 中,但不存在于区间 [li,ri][l_i,r_i] 内的其他任何手机中。

为了减轻顾问的工作,你需要开发一个能够高效回答这些询问的系统。

输入格式

第一行包含三个整数 n,m,gn,m,g(1≤n,m≤5000001\le n,m\le 500000,0≤g≤90\le g\le 9),分别表示手机数量、不同独特特征的数量,以及当前测试点所属分组编号。

接下来 nn 行描述每台手机的独特特征。每行格式如下:

先给出一个整数 kik_i(0≤ki≤m0\le k_i\le m),表示第 ii 台手机具有的独特特征数量;随后在同一行给出 kik_i 个整数

1≤ai,1<ai,2<⋯<ai,ki≤m,1\le a_{i,1}<a_{i,2}<\cdots<a_{i,k_i}\le m,

表示第 ii 台手机具有的特征编号,按递增顺序给出。

下一行包含一个整数 qq(1≤q≤5000001\le q\le 500000),表示询问数量。

接下来 qq 行描述询问。第 ii 行包含三个整数 li,ri,pil_i,r_i,p_i(1≤li≤pi≤ri≤n1\le l_i\le p_i\le r_i\le n)。

设

s=∑i=1nkis=\sum_{i=1}^{n} k_i

为所有手机特征数量之和。保证 n,m≤s≤500000n,m\le s\le 500000。

输出格式

输出 qq 个整数,分别表示每个询问的答案。每个答案占一行。

样例

6 4 0
2 1 3
0
2 1 4
3 2 3 4
2 1 2
2 2 3
5
1 3 2
4 4 4
3 5 4
1 3 1
4 6 5
0
3
1
1
1

样例解释

在第一个询问中,第 22 台手机没有任何独特特征,因此答案为 00。

在第二个询问中,区间只包含一个元素,因此第 44 台手机的全部独特特征都满足要求。

在第三个询问中,第 33 台手机的特征为 [1,4][1,4],第 44 台手机的特征为 [2,3,4][2,3,4],第 55 台手机的特征为 [1,2][1,2]。在第 44 台手机的特征中,只有特征 33 在该区间内是唯一的,因此答案为 11。

组别 分数 附加限制 依赖分组 说明
0 - 样例
1 10 n,m,q≤500n,m,q\le 500 0 -
2 7 q≤5000, s≤10000q\le 5000,\ s\le 10000
3 13 q,s≤100000, m≤500q,s\le 100000,\ m\le 500
4 19 - pi=lip_i=l_i
5 7 li=1l_i=1
6 10 li≤li+1, ri≤ri+1l_i\le l_{i+1},\ r_i\le r_{i+1}
7 12 q,s≤100000q,s\le 100000 0,2,3 -
8 7 q,s≤200000q,s\le 200000 0,2,3,7
9 15 - 0–8 Offline-testing