火烧树状数组
Description
【题意】小火龙捡到了一个长度为n的a序列
她根据a数组做出了一个支持 单点修改，区间求和 的 树状数组 c数组
她发现c数组里有一些负数
她很不爽，想烧掉一些负数的格子
小火龙只想烧a数组里面的数字
相应的，c数组会有变化
小火龙每次烧一个格子都会把这个格子里的数字烧成0
现在你要求出最少要烧掉多少个a数组里的格子才能满足小火龙的愿望（烧的是a数组而目标是c数组）
n保证是一个2的k次方
为了选手的良好体验，我们给出c数组的构造代码（其实就是最常见的树状数组）
良心出题人顺手把快读板子也给你们了
#include<cstdio> using namespace std; typedef long long ll;inline int read() { register int s=0;register char c=getchar();bool f=1; while(c<48){if(c=='-')f=0;c=getchar();} while(c>47)s=(s<<1)+(s<<3)+(c^48),c=getchar(); return f?s:-s; }
const int N=1<<24|5; int n;ll a[N],c[N]; int lowbit(int x){return x&-x;} void add(int x,ll k) { while(x<=n) { c[x]+=k; x+=lowbit(x); } } ll get(int x) { ll ans=0; while(x) { ans+=c[x]; x-=lowbit(x); } return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); for(int i=1;i<=n;i++)add(i,a[i]); for(int i=1;i<=n;i++)printf("%lld ",c[i]); return 0; }
【输入格式】
第一行一个正整数n，表示序列长度
第二行n个正整数表示a序列
【输出格式】
输出一个数表示答案
【输入样例】
8
1 -1 2 0 -3 -2 -3 -1
【输出样例】
3
【提示】
时限1000ms
1<=n<=2^24
-10000000<=a[i]<=10000000
数据不爆long long
请使用快读
【数据范围】
对于30%的数据，n<=32768
对于100%的数据，n<=2^24
</p>