#1943. 基础线段树练习题

    ID: 1943 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest2398来源:qoj.ac数据:公开样例线段树树状数组

基础线段树练习题

基础线段树练习题

题目描述

标题: 基础线段树练习题 - Problem - QOJ.ac

#13621. 基础线段树练习题

Statistics

The problem was used in the following contests:

小 y∞ 看到了一道题:


给出一个长度为 n 的序列 A,接下来有 q 次操作,操作有四种:

1.对于所有的 i∈[l,r],将 Ai 变成 Ai+x。

2.对于所有的 i∈[l,r],将 Ai 变成 x。

3.对于所有的 i∈[l,r],将 Ai 变成 ⌊Ai⌋。

4.对于所有的 i∈[l,r],询问 Ai 的和。

保证x>0。


作为一个数竞选手,小 y∞ 一眼就秒了这个题,这大约只要写一棵线段树就好了。

这里给出了他的详细做法,大概和 UOJ#228. 基础数据结构练习题 的做法差不多?

线段树是一种二叉树,它的每个节点都代表着一个区间,大约长这样:

在每个节点上维护该区间的最小值,最大值和区间和。由于这个题(就是你在看的这个题)并不会询问这些值具体是多少,你可以认为它们和当前数列保持一致。反正是可以正确维护的就对了么

每个节点上会有一个标记二元组 (a,b),若 a=0 则为赋值标记,表示这个区间里的所有数都应被赋值为 b,若 a=1 则为区间加标记,表示这个区间里的所有数都应被增加 b(x′=ax+b)。最初,每个非节点上的标记都为 (1,0),叶子节点的标记都为 (0,Ai)。

显然,这里的标记是可加的,标记 (a1,b1) 加上标记 (a2,b2) 的结果为:

{(0,b2)a2=0;(a1,b1+b2)a2=1.

当下传一个节点的标记时,先将该节点的标记分别加到左右孩子的标记上,然后再将该节点的标记赋值为 (1,0)。

要在节点 [L,R] 将区间 [l,r] 增加 k。若 l≤L≤R≤r,那么给这个节点加上一个标记 (1,k)。否则,先下传该节点的标记,再递归与区间 [l,r] 有交的孩子。每当有一个操作 1 时,在节点 [1,n] 将区间 [l,r] 增加 k。

区间赋值是类似的,只不过加上的标记是 (0,k)。每当有一个操作 2 时,在节点 [1,n] 将区间 [l,r] 修改为 k。

要在节点 [L,R] 对区间 [l,r] 开根号。若 l≤L≤R≤r 且 max−min≤1,当 ⌊max⌋−⌊min⌋=0 时给这个节点加上一个标记 (0,⌊min⌋) ,当它等于 1 时给这个节点加上一个标记 (1,⌊min⌋−min)。否则,先下传该节点的标记,再递归与区间 [l,r] 有交的孩子。每当有一个操作 3 时,在节点 [1,n] 给区间 [l,r] 开根号。

显然,这样做的时间复杂度是均摊 O(hlog log A) 的,其中 h 是线段树的树高,A 是权值范围。

小 y∞ 很想知道每个节点的标记是什么。不过,作为一个数竞选手,他并不擅长写竞赛代码。他决定向你寻求帮助:你能回答他的问题吗?


请写一个程序,要求维护一棵用于维护数列 A 的线段树,支持以下 4 种操作:

1.在节点 [1,n] 将区间 [l,r] 增加 k。

2.在节点 [1,n] 将区间 [l,r] 修改为 k。

3.在节点 [1,n] 对区间 [l,r] 开根号。

4.询问节点 [l,r] 上的标记。

输入格式

第一行一个整数 T,表示测试点编号。

第二行两个整数 n,q,分别表示数列 A 的长度与操作个数。

接下来一行 n 个整数,表示数列 A 的初值。

接下来一行包含 n−1 个整数,按照先序遍历给出了该线段树所有非叶子节点的划分位置 mid 。即,节点 [l,r] 的左右孩子分别为 [l,mid] 与 [mid+1,r]。不难发现通过这些信息就能唯一确定一棵 [1,n] 上的线段树。

接下来的 q 行,每行描述了一个操作,第一个数 opt 表示操作类型。

若 opt=1,则表示执行了一个操作 1,接下来三个整数 l,r,k。

若 opt=2,则表示执行了一个操作 2,接下来三个整数 l,r,k。

若 opt=3,则表示执行了一个操作 3,接下来两个整数 l,r。

若 opt=4,则表示执行了一个操作 4,接下来两个整数 l,r。

输出格式

对于每个操作 4,输出一行两个整数 a,b,表示节点 [l,r] 上的标记是 (a,b)。

样例一

input

0
6 7
1 1 1 1 1 1
5 1 3 2 4
2 2 5 2
4 2 5
1 2 4 1
4 2 5
4 2 3
4 4 4
4 5 5

output

0 2
1 0
0 3
0 3
0 2

限制与约定

共 20 个测试点,每个测试点总分为 5 分。

测试点编号操作 1操作 2操作 3操作 4特性 1特性 2 1√√√√划分线段树时有 mid=⌊l+r2⌋ 2√√√√原线段树树高不超过 30 3√√√ 4√√√√ 5√√√√ 6√√√√√ 7√√√√√√ 8√√√ 9√√√ 10√√√√ 11√√√ 12√√√√√ 13√√√ 14√√√ 15√√√√ 16√√√√√ 17√√ 18√√ 19√√√ 20√√

看!每个点都有特殊性质。

特性 1:划分线段树时有 mid=l 或 mid=r−1。

特性 2:操作只会定位到一个节点,即,对于每个操作,其操作范围恰好是线段树的某个节点。

对于所有测试点,有:

n=q=105,Ai≤108

操作 1 保证 k≤103。

操作 2 保证 k≤108。

部分分

显然,某个测试点错在第 23333 行是一件游戏体验极差的事。作为一个有良心的出题人,本题将按照该点的正确率来给分:如果你的程序在某个测试点的正确率是 p,那么你将在此测试点得到5(15p−1)14 分。另外,如果你输出的行数与标准答案行数不同,可能会爆零?没有testlib真自闭

没有输出时正确率当然为 1 啦!

什么,你说这是IOI赛制?我不听我不听,我要做良心出题人!

乱搞碾标算,N方过百万!

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

0
6 7
1 1 1 1 1 1
5 1 3 2 4
2 2 5 2
4 2 5
1 2 4 1
4 2 5
4 2 3
4 4 4
4 5 5
0 2
1 0
0 3
0 3
0 2