#P12473. [2025年福建省队集训]未来的我

    ID: 11636 传统题 3000ms 888MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-Splay维护顺序统计量区间翻转标记复合等比数列求和模逆元快速幂添加哨兵参数化连续段压缩

[2025年福建省队集训]未来的我

题目描述

阿绫有 22 个数组 a,ba,b,一开始 22 个数组为空数组。

阿绫会进行 mm 次操作,设当前数组长度为 nn,操作有以下类型:

  1. 给定 x,c,p,q,u,vx,c,p,q,u,v,分别在数组 a,ba,b 的第 xx 个数和第 x+1x+1 个数之间插入 cc 个数 (0≤x≤n)(0\le x\le n),对于 1≤i≤c1\le i\le c,在 aa 中插入的第 ii 个数为 pqi−1pq^{i-1},在 bb 中插入的第 ii 个数为 u+v(i−1)u+v(i-1)。
  2. 给定 l,rl,r,删除数组 a,ba,b 的区间 [l,r][l,r] (1≤l≤r≤n)(1\le l\le r\le n)。
  3. 给定 l,rl,r,翻转数组 a,ba,b 的区间 [l,r][l,r] (1≤l≤r≤n)(1\le l\le r\le n)。
  4. 给定 l,rl,r,询问 ∑i=lraibi\sum_{i=l}^r a_ib_i,答案对 P=109+7P=10^9+7 取模 (1≤l≤r≤n)(1\le l\le r\le n)。
  5. 给定 l,r,u,vl,r,u,v,对数组 bb 的区间 [l,r][l,r] 进行修改 (1≤l≤r≤n)(1\le l\le r\le n),对于 l≤i≤rl\le i\le r,将 bib_i 修改为 bi+u+v(i−l)b_i+u+v(i-l)。

输入格式

从标准输入读入。

第一行 22个整数 tid,mtid,m,其中 tidtid 表示测试点编号,样例中 tid=0tid=0。

接下来 mm 行,每行若干个整数表示一次操作。

对于第一种操作,输入 1 x c p q u v。
对于第二种操作,输入 2 l r。
对于第三种操作,输入 3 l r。
对于第四种操作,输入 4 l r。
对于第五种操作,输入 5 l r u v。

输出格式

输出到标准输出。

对于每次询问操作,输出一行一个整数,表达答案对 P=109+7P=10^9+7 取模的结果。

样例

样例输入1

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

样例输出1

370

样例解释1

第 11 次操作后,序列 a,ba,b 分别为 {1,2,4,8,16},{3,7,11,15,19}\{1,2,4,8,16\},\{3,7,11,15,19\}。
第 22 次操作后,序列 a,ba,b 分别为 {1,2,16},{3,7,19}\{1,2,16\},\{3,7,19\}。
第 33 次操作后,序列 a,ba,b 分别为 {2,1,16},{7,3,19}\{2,1,16\},\{7,3,19\}。
第 44 次操作后,序列 a,ba,b 分别为 {2,1,16},{7,4,22}\{2,1,16\},\{7,4,22\}。
第 55 次询问,答案为 2×7+1×4+16×22=3702\times 7 + 1\times 4 + 16\times 22=370。

样例 2

见选手目录下的 future/future2.in 与 future/future2.ans。

这个样例满足测试点 1∼21\sim 2 的约束条件。

样例 3

见选手目录下的 future/future3.in 与 future/future3.ans。

这个样例满足测试点 5∼65\sim 6 的约束条件。

样例 4

见选手目录下的 future/future4.in 与 future/future4.ans。

这个样例满足测试点 7∼87\sim 8 的约束条件。

样例 5

见选手目录下的 future/future5.in 与 future/future5.ans。

这个样例满足测试点 11∼1211\sim 12 的约束条件。

样例 6

见选手目录下的 future/future6.in 与 future/future6.ans。

这个样例满足测试点 15∼1615\sim 16 的约束条件。

样例 7

见选手目录下的 future/future7.in 与 future/future7.ans。

这个样例满足测试点 21∼2221\sim 22 的约束条件。

样例 8

见选手目录下的 future/future8.in 与 future/future8.ans。

这个样例满足测试点 23∼2523\sim 25 的约束条件。

数据范围

数据范围中变量含义与题目描述一致,nn 的范围表示任意时刻数组长度的范围。

对于 100%100\% 的数据,1≤m≤3×1051\le m\le 3\times 10^5,0≤x≤n≤1090\le x\le n\le 10^9,1≤c≤1091\le c\le 10^9,1≤l≤r≤n1\le l\le r\le n,1≤p,q<P1\le p,q\lt P,0≤u,v<P0\le u,v\lt P。

测试点编号 mm 特殊限制
1∼21\sim 2 ≤5000\le 5000 n≤5000n\le 5000
3∼43\sim 4 ≤3×105\le 3\times 10^5 ABEABE
5∼65\sim 6 BEBE
7∼87\sim 8 ADEADE
9∼109\sim 10 AEAE
11∼1211\sim 12 EE
13∼1413\sim 14 ≤8×104\le 8\times 10^4 ABAB
15∼1615\sim 16 CC
17∼1817\sim 18 ADAD
19∼2019\sim 20 ≤3×105\le 3\times 10^5 BB
21∼2221\sim 22 AA
23∼2523\sim 25 无

特殊限制 AA: 不存在操作 33。
特殊限制 BB: 不存在操作 55。
特殊限制 CC: 保证 q=1q=1。
特殊限制 DD: 保证 v=0v=0。
特殊限制 EE: 保证 ∑c≤m\sum c\le m。