学姐是野兔先辈β

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/131072 K (Java/Others)
Total Submission(s): 1264    Accepted Submission(s): 230
 

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

分析：

因为这些操作对于每一个f(Ai)操作都是独立的，不会影响其他的部分的结果，所以当输入的t==1时不必理会，直接输出区间[l,r]之间的元素和，，ff[i]表示[1,i]之间的元素和，则ff[l,r]=ff[1,r]-ff[1,l-1];

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 1e5+1;
int f[maxn],ff[maxn];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        memset(ff,0,sizeof(ff));
        for(int i=1;i<=n;i++){
            scanf("%d",&f[i]);
            ff[i]=f[i]+ff[i-1];
        }
        int t1,l,r;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&t1,&l,&r);
            if(t1==2){
            	cout<<ff[r]-ff[l-1]<<"\n";
			}
        }
    }
    return 0;
}