#P17265. [2025年南开中学集训]混沌纪元

    ID: 16991 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-普通线段树消除被支配候选倍增性质断点压缩同向双指针前后缀分解

[2025年南开中学集训]混沌纪元

题目描述

在混沌初生的年代,王国的长老们正在研究一条古老的法则:

“只有当力量之间保持和谐,世界才能不被撕裂。”

给定长度为 nn 的数能序列 aa,称区间 [l,r][l,r] 为「好区间」,当且仅当不存在 l≤i<j≤rl\le i<j\le r 使得:

$\dfrac{a_i\times a_j}{a_i+a_j}>\sum\limits_{\substack{k=l\\k\ne i,k\ne j}}^r a_k$。

即:任意两种能量的“协同效应”不会超过其他能量的总和。

你需要处理 qq 次操作 (op,x,y)(op,x,y):

  • 若 op=1op=1:先知改变了能量流,将 axa_x 赋值为 yy。
  • 若 op=2op=2:长老询问在区间 [x,y][x,y] 中的最长好区间长度。

输入格式

第一行包含两个整数 nn 和 qq,依次表示序列长度和操作次数。

第二行包含 nn 个整数,其中第 ii 个整数表示 aia_i。

接下来 qq 行,每行包含三个整数 op,x,yop,x,y,表示一次操作。

输出格式

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

输入输出样例 #1

输入 #1

5 5
1 3 8 4 60
2 2 5
2 1 3
1 5 10
2 1 5
2 3 5

输出 #1

3
1
5
1

输入输出样例 #2

输入 #2

12 10
3 11 7 50 6 6 68 154 12 10 11 13
2 1 12
2 2 2
1 5 8
2 7 11
2 5 12
2 1 11
1 7 6
2 6 10
2 4 9
2 1 10

输出 #2

12
1
4
8
11
5
5
10

说明 / 提示

数据范围

对于所有数据,保证:

  • 1≤n,q≤2×1051\le n,q\le 2\times 10^5;
  • 1≤ai≤10121\le a_i\le 10^{12};
  • op=1op=1 时,1≤x≤n1\le x\le n,1≤y≤10121\le y\le 10^{12};
  • op=2op=2 时,1≤x≤y≤n1\le x\le y\le n。
子任务编号 分值 限制
1 20 n,q≤300n,q\le 300
2 15 n,q≤5000n,q\le 5000
3 20 n,q≤5×104n,q\le 5\times 10^4,op=2op=2
4 n,q≤5×104n,q\le 5\times 10^4
5 25 无

样例解释 #1

对于第一个查询,最长好区间是 [2,4][2,4]。

对于第二个查询,任意长度为 11 的区间都是最长好区间。

然后将 a5a_5 修改为 1010,原序列变成 1,3,8,4,101,3,8,4,10。

对于第三个查询,最长好区间是 [1,5][1,5]。

对于第四个查询,任意长度为 11 的区间都是最长好区间。