Rhythm of Codes

BZOJ 3211 花神游历各国 线段树题解

BZOJ 3211 花神游历各国 线段树题解

 

3211: 花神游历各国

Time Limit: 5 Sec Memory Limit: 128 MB

Submit: 2551 Solved: 946

[Submit][Status][Discuss]

Description

Input

Output

每次x=1时,每行一个整数,表示这次旅行的开心度

 

 

Sample Input

4

 

1 100 5 5

 

5

 

1 1 2

 

2 1 2

 

1 1 2

 

2 2 3

 

1 1 4

 

Sample Output

101

 

11

 

11

 

HINT

 

对于100%的数据, n ≤ 100000,m≤200000 ,data[i]非负且小于10^9

 

 

 

 

Source

SPOJ2713 gss4 数据已加强

 

线段树区间修改区间查询,但是因为开方的特殊性,必须要更新到每个单点上。本题每个点最大为109 ,开方五次就已经变成一了,所以开方标记超过五次往下就不用开了。

 

Leave a Reply

Your email address will not be published. Required fields are marked *