#P15594. [2025年山东第一轮集训] 修改

    ID: 14806 传统题 6000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>数据结构分块堆算法基础模拟数学CF2500

[2025年山东第一轮集训] 修改

题目描述

X 有一个长为 nn 的正整数数列

a1,a2,…,an.a_1,a_2,\ldots,a_n.

X 会对这个数列做出 qq 次修改。第 ii 次修改有两个参数 li,ril_i,r_i,X 会按顺序枚举

j=li,li+1,…,ri−1,j=l_i,l_i+1,\ldots,r_i-1,

如果

aj>aj+1,a_j>a_{j+1},

则 X 会交换 aja_j 和 aj+1a_{j+1} 的值。

Y 想知道在第 i=1,2,…,qi=1,2,\ldots,q 次修改后,

si=∑j=liriajs_i=\sum_{j=l_i}^{r_i}a_j

的值分别是多少。但是 X 并不想做奇奇怪怪的计算,因此 Y 只好求助于你。

对于一部分测试点,Y 并不想实时地知道 sis_i,你只需要在所有修改后输出 aa 数组即可。对于这样的测试点有 t=1t=1;对于那些需要计算 sis_i 的测试点有 t=2t=2。

输入格式

第一行,三个正整数 n,q,tn,q,t。

第二行,nn 个正整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

接下来 qq 行,每行两个正整数 li,ril_i,r_i。

输出格式

若 t=1t=1:一行,nn 个正整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示所有修改后的 aa 数组。

若 t=2t=2:一行,qq 个正整数 s1,s2,…,sqs_1,s_2,\ldots,s_q。

样例 1 输入

5 6 2
9 9 8 2 4
1 4
2 4
2 5
1 2
3 4
1 5

样例 1 输出

28 19 23 11 12 32

数据范围与子任务

对于所有数据:

1≤n≤106,1\le n\le 10^6, 1≤q≤104,1\le q\le 10^4, t∈{1,2},t\in\{1,2\}, 1≤ai≤109,1\le a_i\le 10^9, 1≤li≤ri≤n.1\le l_i\le r_i\le n.
子任务 n≤n\le q≤q\le t=t= 特殊性质 分值
1 10410^4 22 无 12
2 9×1059\times 10^5 90009000 11 li=1, ri=nl_i=1,\ r_i=n 20
3 22 16
4 11 无
5 22 ai≤2a_i\le 2 8
6 无 16
7 10610^6 10410^4 11 或 22 12