[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 J: qwb又偷懒了 [BIT]【数据结构】

2017-06-03 02:44:15 Tabris_ 阅读数：572

博客爬取于2020-06-14 22:40:13
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849792

题目链接：http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=9
——————————————————————————————————————————
Problem J: qwb又偷懒了
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 599 Solved: 93
[Submit][Status][Web Board]
Description
qwb最近在做一个群众收入统计。ta非常懒，以至于忘记了今天领导要来视察。所以急忙催下属去做统计。
在接下来长度为n的时间里,每个单位时间都有事情发生,可能会发下以下两种事件：

1)下属递交了一份调查报告，由于太匆忙，上面只有一个整数x，代表一个居民的收入。
2)领导来视察了，领导会来询问，收入在区间[l,r]内的居民的平均收入，qwb需要给出回答。

qwb非常讨厌小数，所以qwb上报时都会省略小数部分。如果上报时统计的人数为0，qwb就暴露了他偷懒的事情，他就会zhizhiwuwu。
Input
多组测试数据，处理到文件末尾。

每组测试数据的第一行为一个正整数n(0<=100000),确保所有的n的和不超过300000

接下来n行，
当第一个数为0时，代表操作1，后面跟着一个整数x(0<=x<=1000000)，意义如题目所述。
当第一个数为1时，代表操作2，后面跟着两个整数l，r(0<=l<=r<=1000000)，意义如题目描述。

Output
对于每一个领导的询问，给出一个回答，如果统计区间的人数为零，则输出"zhizhiwuwu"。（不带引号）
每个测试例之后输出一个空行。
Sample Input
3
0 1
0 3
1 1 3
2
0 1
1 2 2
Sample Output
2

zhizhiwuwu

HINT

输入输出包含大规模数据,建议使用scanf,printf.

样例1中，收入为1的居民有一个，收入为3的居民有1个，所以收入在1-3范围内的居民有2个，总收入是4，4/2=2
——————————————————————————————————————————

BIT入门级别没啥说的
数据范围小，直接两个BIT就好
其实1个就够了，另一个主要是记录0的个数，，，我也没注意这里wa了一发

附本题代码
——————————————————————————————————————————

# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

# define abs(x) (((x)>0)?(x):-(x))

const int N = 1000000+10;
const int MOD  = 1e9+7;

/******************************************/

LL sum[N][2];
# define lowbit(x) (x&-x)
void update(int i,int v){for(i++;i<N;i+=lowbit(i))sum[i][0]+=v,sum[i][1]+=1;}
LL getSum(int i){LL ans=0;for(i++;i;i-=lowbit(i))ans+=sum[i][0];return ans;}
LL getCnt(int i){LL ans=0;for(i++;i;i-=lowbit(i))ans+=sum[i][1];return ans;}

LL n,op,l,r,x;
int main(){
    while(~scanf("%lld",&n)){
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++){
            scanf("%lld",&op);
            if(op){
                scanf("%lld%lld",&l,&r);
                LL cnt = getCnt(r)-getCnt(l-1);
                LL ans = getSum(r)-getSum(l-1);
//                cout<<ans<<' '<<cnt<<endl;
                if(cnt==0) puts("zhizhiwuwu");
                else       printf("%lld\n",ans/cnt);

            }
            else {
                scanf("%lld",&x);
                update(x,x);
            }
        }
        puts("");
    }
    return 0;
}