Aninteresting game

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

 

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 2 1 8 9 2 6

 

 

Sample Output

9 2

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= 210 When 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

wange2014   |   We have carefully selected several similar problems for you:  6447 6446 6445 6444 6443 

 

 

Statistic | Submit | Discuss | Note

因为插入i的贡献是[i-lowbit(i)+1,i-1] 的长度，所以i的贡献就是（i-1）-（i-lowbit(i)+1）,就是lowbit(i)

所以这个题目化简成了：

①：求【L，R】的lowbit（i）的和

②：数字x在几个集合里面

思想：

第二种比较好算，要找到x在几个集合中，可用x=x+lowbit（x）找出有多少满足条件的x，就能得到集合的个数。

第一种需要推一下公式

可以发现lowbit的值肯定是1，2，4，8，16.。。。2的n次方。所以利用容斥原理，假如我想知道2的个数，那么就用n/2算出有几个可以整除2，减掉可以整除2*2的个数。嗯。

我们可以发现，每k个 k ∈{1,2,4,8……}会出现1个k的倍数，所以我们能够知道[1,i]中有多少个不同的k以及每个k的个数p（类似于容斥原理）。所以能够求得[1,i]的长度和是多少，进而求得[a,b]的长度和。

参考：https://blog.****.net/haut_ykc/article/details/78376923

代码：

#include<stdio.h>
typedef long long ll;
ll tmp[65],n,m;
ll findans(ll x)
{
	ll ans=0;
	for(ll i=0;tmp[i]<=x;i++)
		ans+=(x/tmp[i]-x/tmp[i+1])*tmp[i];
	return ans;
}
int main(void)
{
	int i;
	tmp[0]=1;
	for(i=1;i<=63;i++)
		tmp[i]=tmp[i-1]*2;
	while(scanf("%lld%lld",&n,&m)!=EOF)
	{
		ll x,y,t;
		while(m--)
		{
			scanf("%lld",&t);
			if(t==1)
			{
				scanf("%lld%lld",&x,&y);
				printf("%lld\n",findans(y)-findans(x-1));
			}
			else
			{
				ll ans=0;
				scanf("%lld",&x);
				while(x<=n)
				{
					ans++;
					x+=x&(-x);
				}
				printf("%lld\n",ans);
			}
		}
	}
	return 0;
}