剪贴板链接

自己想到的一个命题，如果有现成的题或者有借鉴价值的题可以告诉我，或者有想法也行

由于自己想到的，数据范围不定，能做到越大越好

$O(n \sum a_i)$ 的暴力是肯定可以的，但是问题是能优化到多少

命题描述：

有 $n$ 个人和 $k$ 种兴趣爱好，其中这 $k$ 种兴趣爱好分别为 $1,2,\dots,k$

第 $i$ 个人有 $a_i(1 \le a_i \le k)$ 种兴趣爱好，分别为 $x_{i,1},x_{i,2},\dots,x_{i,a_i}(\{x_{i,1},x_{i,2},\dots,x_{i,a_i}\} \in [1,k] \cap \mathbb{Z^+},x_{i,1} \lt x_{i,2} \lt \dots \lt x_{i,a_i})$

定义 $f(i,j)= \begin{cases}0,&第i个人和第j个人没有共同的兴趣爱好\\w,&第i个人和第j个人有共同的兴趣爱好，且他们共同的兴趣爱好中最小的为w\end{cases}$

求 $\sum \limits_{i=1}^n \sum \limits_{j=1}^n f(i,j)$

如果可以解决的话，还有几个问题：

1. 每次给定询问参数 $r$，求 $\sum \limits_{i=1}^r \sum \limits_{j=1}^r f(i,j)$

2. 每次给定询问参数 $l$，求 $\sum \limits_{i=l}^n \sum \limits_{j=l}^n f(i,j)$

3. 每次给定询问参数 $l,r$，求 $\sum \limits_{i=l}^r \sum \limits_{j=l}^r f(i,j)$

4. 每次给定询问参数 $a,b,c,d$，求 $\sum \limits_{i=a}^b \sum \limits_{j=c}^d f(i,j)$