qwb又偷懒了思路+代码_综合

Problem J: qwb又偷懒了

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 662 Solved: 106
[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

Sample Output

 2 zhizhiwuwu

HINT

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

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

思路：这道题看到就应该大概知道要用树状数组，因为题意要对目标进行修改查询操作，直接用循环会TE。

难点在于区间平均收入=区间总工资/区间总人数，树状数组不好进行操作，所以我用到了两个树状数组分别存取人数与工资收入。因为要考虑收入

为0的情况，所以进行操作时树状数组进行了右移，让0号树状数组不存。

#include<stdio.h>
#include<string.h>
const int max1=1000000+100;
typedef long long ll;
ll p[max1];
ll m[max1];//人，钱
int lowbit(ll x)
{return x&(-x);
}
void update1(ll x,ll add)//钱
{while(x<=max1){m[x]+=add;x+=lowbit(x);}
}
void update2(ll x, ll add)//人
{while(x<=max1){p[x]+=add;x+=lowbit(x);}
}
ll sum(ll n,ll *a)
{ll ans=0;while(n>0){ans+=a[n];n-=lowbit(n);}return ans;
}
int main()
{int k,d;ll x,l,r;while(~scanf("%d",&k)){memset(p,0,sizeof(p));memset(m,0,sizeof(m));while(k--){scanf("%d",&d);if(!d){scanf("%lld",&x);x++;//右移，树状数组0号单元不存数据 update1(x,x-1);update2(x,1);}else{scanf("%lld %lld",&l,&r);l++,r++;//因为整个树状数组都右移了，所以区间应该+1 ll t1,t2;t1=sum(r,p)-sum(l-1,p);//人t2=sum(r,m)-sum(l-1,m);//钱if(!t1)//该区间收入人数为0 printf("zhizhiwuwu\n");elseprintf("%lld\n",t2/t1);}}printf("\n");}return 0;
}

qwb又偷懒了 思路+代码