首页 > 代码库 > hdu 5239 Doom（线段树）
hdu 5239 Doom（线段树）
Doom
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1401 Accepted Submission(s): 368
Problem Description
THE END IS COMINGGGGGG!
Mike has got stuck on a mystery machine. If he cannot solve this problem, he will go to his doom.
This machine is consist of n cells, and a screen. The i-th cell contains a number ai(1≤i≤n). The screen also contains a number s, which is initially 0.
There is a button on each cell. When the i-th is pushed, Mike observes that, the number on the screen will be changed to s+ai, where s is the original number. and the number on the i-th cell will be changed to a2i.
Mike observes that the number is stored in radix p, where p=9223372034707292160. In other words , the operation is under modulo p.
And now, Mike has got a list of operations. One operation is to push buttons between from l-th to r-th (both included), and record the number on the screen. He is tired of this stupid work, so he asks for your help. Can you tell him, what are the numbers recorded.
Mike has got stuck on a mystery machine. If he cannot solve this problem, he will go to his doom.
This machine is consist of n cells, and a screen. The i-th cell contains a number ai(1≤i≤n). The screen also contains a number s, which is initially 0.
There is a button on each cell. When the i-th is pushed, Mike observes that, the number on the screen will be changed to s+ai, where s is the original number. and the number on the i-th cell will be changed to a2i.
Mike observes that the number is stored in radix p, where p=9223372034707292160. In other words , the operation is under modulo p.
And now, Mike has got a list of operations. One operation is to push buttons between from l-th to r-th (both included), and record the number on the screen. He is tired of this stupid work, so he asks for your help. Can you tell him, what are the numbers recorded.
Input
The first line contains an integer T(T≤5), denoting the number of test cases.
For each test case, the first line contains two integers n,m(1≤n,m≤105).
The next line contains n integers ai(0≤ai<p), which means the initial values of the n cells.
The next m lines describe operations. In each line, there are two integers l,r(1≤l≤r≤n), representing the operation.
For each test case, the first line contains two integers n,m(1≤n,m≤105).
The next line contains n integers ai(0≤ai<p), which means the initial values of the n cells.
The next m lines describe operations. In each line, there are two integers l,r(1≤l≤r≤n), representing the operation.
Output
For each test case, output ‘‘Case #t:‘‘, to represent this is the t-th case. And then output the answer for each query operation, one answer in a line.
For more details you can take a look at the example.
For more details you can take a look at the example.
Sample Input
24 42 3 4 51 22 33 41 41 321 11 11 1
Sample Output
Case #1:51839405Case #2:2622
Source
怎么知道最后会不变的...
hdu 5239 Doom（线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。