首页 > 代码库 > hdu 5975 Aninteresting game

hdu 5975 Aninteresting game

Aninteresting game

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 209    Accepted Submission(s): 82


Problem Description
Let’s play a game.We add numbers 1,2...n in increasing order from 1 and put them into some sets.
When we add i,we must create a new set, and put iinto it.And meanwhile we have to bring [i-lowbit(i)+1,i-1] from their original sets, and put them into the new set,too.When we put one integer into a set,it costs us one unit physical strength. But bringing integer from old set does not cost any physical strength.
After we add 1,2...n,we have q queries now.There are two different kinds of query:
1 L R:query the cost of strength after we add all of [L,R](1≤L≤R≤n)
2 x:query the units of strength we cost for putting x(1≤x≤n) into some sets.
 

 

Input
There are several cases,process till end of the input.
For each case,the first line contains two integers n and q.Then q lines follow.Each line contains one query.The form of query has been shown above.
n≤10^18,q≤10^5
 

 

Output
For each query, please output one line containing your answer for this query
 

 

Sample Input
10 21 8 92 6
 

 

Sample Output
92
Hint
lowbit(i) =i&(-i).It means the size of the lowest nonzero bits in binary of i. For example, 610=1102, lowbit(6) =102= 210When we add 8,we should bring [1,7] and 8 into new set.When we add 9,we should bring [9,8] (empty) and 9 into new set.So the first answer is 8+1=9.When we add 6 and 8,we should put 6 into new sets.So the second answer is 2.
 

 

Source
2016ACM/ICPC亚洲区大连站-重现赛(感谢大连海事大学)
 

 

Recommend
 
 
 

hdu 5975 Aninteresting game