http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=832

Problem Description

In the world line 1.048596%

双叶理央是梓川咲太为数不多的朋友。

栖息于理科实验室，一直在做着梓川咲太永远也想不明白的实验。偶尔用半升的烧杯煮咖啡，度过悠闲的校园时光。

梓川咲太无聊的时候也经常拜访理科实验室。黄金周的最后一天，上午，双叶理央也在辛勤的做着实验，不过这次有点不同，并没有常识中的实验仪器，双叶理央面对电脑陷入深思。

“你来的正好，听我说。”，双叶理央罕见的没有先让梓川咲太出去，“我最近在用Binary Indexed Tree去解决一个有关数据结构的问题，里面有一个语句是x&(-x)，这是对方程lowbit(x)的模拟操作。”

梓川咲太想吐槽些什么，可是立刻被双叶理央递过来的咖啡堵住了嘴。

“听我说完，lowbit(x)的含义为x的二进制表达式中，最低位1所对应的值，比如说6的二进制为110，所以lowbit（6）=2。”

感觉说的不够详细的理央整理了一下思绪，继续说道。

“更一般的，设 a[m],a[m-1].....a[1]是数x的二进制表示，而a[m]是x二进制的最低位，k是最小的满足a[k]=1的下标。则此时，lowbit(x)的值就等于 2^(k-1)。”

"恩恩，是这样吗，我懂了。"

梓川咲太什么都听不懂。

“现在有这么一个操作，就称为f(x)吧。当输入一个非负整数x，如果x等于0，则返回0；否则他有二分之一的概率会返回x-lowbit(x)，也有二分之一的概率的记录返回x+lowbit(x)。”

双叶理央开始在黑板上写下数学公式。

“现在有一个长度为n的数组A，我会对它进行m次操作。

操作有两种，第一种是1 L R，对于每一个下标i属于[L,R]，将Ai变为f（Ai）。

第二种是 2 L R，询问在区间[L,R]，Ai的值的期望值的总和。”

“当然，这些操作对于每一个f(Ai)操作都是独立的，不会影响其他的部分的结果......”

双叶理央说完以后开始陷入深思，没过多久就展现出茅塞顿开的表情。

“......大概就是这样，也不是什么难题......笨蛋梓川果然是当小黄鸭的最好人选。行了，你快滚出去吧。”

梓川咲太很自觉的离开了理科实验室。

之后，梓川咲太骑车去湘南台站附近的图书馆，给妹妹梓川枫借还书的时候，『那个』进入了视线。

野兔先辈屹立在书架的彼岸。


这一天，梓川咲太与野兔先辈邂逅了。

 

 

Input

第一行一个整数T，表示有T组样例

对于每组样例

第一行两个整数n，m（1<=n，m<=1e5），表示数组的长度n与操作的次数m

第二行n个整数Ai（1<=Ai<=1e4），表示数组每个的数字

之后的m行，每一行有三个整数 t，L，R(t==1 或 t==2，1<=L<=R<=n ).

输入保证n和m的和不超过1e6。

 

 

Output

对于每一组询问操作，输出对应区间的Ai的值的期望得分的值。

 

 

Sample Input


 

1 3 2 1 2 3 1 3 3 2 1 2

 

 

Sample Output


 

3

Hint

Scanf Recommed

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG

using namespace std;
typedef long long ll;
const int N=100000+10;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m;
int tree[N<<2];
void PushUp(int rt){
     tree[rt] = tree[rt*2] + tree[rt*2+1];
 }
void Build(int l, int r, int rt){
    if(l == r){
    scanf("%d",&tree[rt]);
        return ;
    }
    int m = (l+r) / 2;
    Build(l,m,rt*2);
    Build(m+1,r,rt*2+1);
    PushUp(rt);
}
int Query(int l, int r, int rt, int L, int R){
    if(L <= l && r <= R){
        return tree[rt];
    }
    int m = (l+r) / 2;
    int ret = 0;
    if(L <= m) ret += Query(l, m, rt*2, L, R);
    if(m < R) ret += Query(m+1, r, rt*2+1, L, R);
    return ret;
}

int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d",&t);

    while(t--){
        scanf("%d%d",&n,&m);
        Build(1,n,1);
        int T,l,r;
        while(m--){
            scanf("%d%d%d",&T,&l,&r);
            if(T==1){
            }else{
                printf("%d\n", Query(1,n,1,l,r));
            }
        }
    }
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

https://www.cnblogs.com/MingSD/p/10050324.html

#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod =  (int)1e9+7;
const int N = 1e5 + 100;
int a[N];
int main(){
    int n, m, T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]), a[i] += a[i-1];
        int op, l, r;
        while(m--){
            scanf("%d%d%d", &op, &l, &r);
            if(op == 2){
                printf("%d\n", a[r] - a[l-1]);
            }
        }
    }
    return 0;
}