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

Tabris

CSDN数据结构

发布于：2017年6月3日

次浏览

[原创]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 了一发

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# 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;
}

本页文档最后更新于：2021年5月16日

CSDN

数据结构