学姐是野兔先辈β

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与操作的次数。
第二行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

题解:看起来很复杂,但仔细一看算数学期望时无论操作多少次,x-lowbit(x)和x+lowbit(x)都是会消掉的。因此题目转化为 给出一段区间[L,R],求[L,R]内元素的和

PS:求和时如果直接每次累加会造成TLE,正确做法应该是读入时就累加好,每次给出下标直接输出。


#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ling long
#define INF 0×3f3f3f3f  //0×7ffffff
#define EPS 1e-6
#define maxn 100000+10
#define PI acos(-1.0)
using namespace std;
int a[maxn];
int main()
{
    int t,n,m,pop,l,r;
    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];}
        while(m--)
        {
            scanf("%d%d%d",&pop,&l,&r);
            if(pop==2)
                printf("%d\n",a[r]-a[l-1]);
        }
    }
    return 0;
}

 

发表评论,支持MarkDown语法