#P18903. [2026多校联测]小Z爱考试

[2026多校联测]小Z爱考试

题目背景

长假过后,如何应付开学考试是一个困难的问题,对此,小 Z 在班级中组织了“联络对象”……

题目描述

小 Z 所在的班级中有 nn 个同学,第 ii 个同学正常完成考试的得分为 aia_i。

每个同学 ii 都有一个联络对象 bib_i,并在考试中会恰好进行一次联络。在联络时,如果 ai<abia_i<a_{b_i},那么他的得分 aia_i 会神秘地增加 wiw_i,保证 wiw_i 为正整数。

但是小 Z 也考虑到某位同学同时是很多人的联络对象时会引发一些混乱,因此小 Z 限制了每个人至多是三名同学的联络对象。

由于考试过程中不能交谈,所有同学进行联络的顺序是不确定的。现在小 Z 想要知道,如果所有 n!n! 种联络顺序等概率出现,每位同学在考试完成后的得分期望是多少。

当然,同学们的联络策略会发生改变,自身实力也会发生改变,于是小 Z 希望你能完成 qq 次如下操作(三种之一):

  • 1 i c:修改 aia_i 的值为 cc。
  • 2 i c:修改 wiw_i 的值为 cc。
  • 3 k:按上述方式进行考试,求第 kk 位同学在考试完成后的得分期望。请输出答案对 109+710^9+7 取模后的结果。可以证明答案一定能写成有理数 pq\frac{p}{q} 的形式,其中 q≢0(mod109+7)q\not\equiv0\pmod{10^9+7}。

注意,所有询问之间互不影响,也就是 aia_i 在一次询问中的变化不会影响到下一次询问。

输入格式

本题包含多组测试数据。

第一行包含一个正整数 TT,表示数据组数。接下来 TT 组数据:

第一行包含两个正整数 n,qn,q,含义如上。

接下来 nn 行,每行包含三个正整数 ai,bi,wia_i,b_i,w_i,含义如上。

接下来 qq 行,每行描述一个操作。

输出格式

对每个询问,输出一行一个整数表示答案。

样例 1

2
3 3
3 2 3
2 1 3
4 1 1
3 1
3 2
3 3
6 8
1 3 2
1 1 1
4 6 3
5 3 5
1 1 4
4 4 2
3 2
3 4
3 6
1 2 3
3 2
1 1 5
3 2
3 1
500000008
5
166666672
500000005
833333345
6
3
4
333333341

样例 2

1
10 10
10 3 5
17 6 9
19 2 16
14 1 5
11 9 13
13 1 8
16 4 11
11 5 3
11 1 4
23 3 16
3 6
3 5
3 10
2 5 6
3 3
3 10
3 5
1 4 10
3 4
3 1
17
166666681
933333363
666666691
933333363
12
500000016
15

数据范围

对所有数据,1≤T≤1001\le T\le100,1≤n,q,∑n,∑q≤2×1051\le n,q,\sum n,\sum q\le2\times10^5,1≤ai,bi,wi,c≤1091\le a_i,b_i,w_i,c\le10^9,1≤k≤n1\le k\le n。

保证 wiw_i 为正整数,并且 bb 中一种数出现不超过三次。注意,不保证 bi≠ib_i\ne i。

测试点编号 n,∑n≤n,\sum n\le q,∑q≤q,\sum q\le 特殊性质
1-3 1010 无
4-7 30003000 没有操作 1、2
8-10 2×1052\times10^5
11-12 30003000 无
13-20 2×1052\times10^5