首页 > 代码库 > hdu 5975---Aninteresting game（树状数组）

hdu 5975---Aninteresting game（树状数组）

2024-10-02 00:24:01   217人阅读

题目链接

 

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= 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.
 
题意：每次查询有两种操作
           op1：求加入L~R的数时所消耗的单元
           op2：求将x加入集合或移动到其它集合所消耗的单元（即由x引起消耗的单元）
 
思路：op1：每次加入一个数i 那么会移动[i-lowbit(i)+1 , i-1] ，总的消耗是i-(i-lowbit(i)+1) +1=lowbit(i) 所以每次加入一个数对应的消耗是2的幂次，那么求L~R即可以枚举幂次，即： ans+=(n/(1<<i)-n/(1<<(i+1)))*(1<<i)
                 解释一下，n/(1<<i)-n/(1<<(i+1))表示长为2^i的消耗的数的个数，例如：n=10 ， 包含长为2的数是2，6，10 为什么4，8不是，因为它们虽然是2的倍数，但更是4的倍数，包含更长的区间了，所以这部分要减去。
        op2：由树状数组可知 [i-lowbit(i)+1 , i-1] 是以i为根节点对应的区间，如果假如的数能够移动i ，那么这个数对应的孩子区间一定包含i ，所以从x向上一直找父节点即可。
 
代码如下：
#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;typedef long long LL;LL lowbit(LL x){    return x&(-x);}LL query(LL x,LL n){    LL ans=0;    while(x<=n)    {        ans++;        x+=lowbit(x);    }    return ans;}LL cal(LL x){    LL ans=0;    LL tmp=1;    for(LL i=0; tmp<=x; i++)        ans+=(x/(tmp)-x/(tmp<<1))*tmp,tmp<<=1;    return ans;}int main(){    LL n,q;    while(scanf("%lld%lld",&n,&q)!=EOF)    {        while(q--)        {            int op;            scanf("%d",&op);            if(op==1)            {                LL x,y;                scanf("%lld%lld",&x,&y);                LL ans=cal(y)-cal(x-1);                printf("%lld\n",ans);            }            else            {                LL x;                scanf("%lld",&x);                LL ans=query(x,n);                printf("%lld\n",ans);            }        }    }    return 0;}

 

 
 
 
 

hdu 5975---Aninteresting game（树状数组）


联系
我们