本文共 1187 字,大约阅读时间需要 3 分钟。
31 12 23 331 11 21 30
1 1 13 2 1
树状数组在改变一个数据时整个数组的值都会改变 在这道题目中 需要求某一个气球涂过的次数 假如结果(a,b) 那么需要进行add(a,1);然后进行add(b+1,-1)来抵消对b以后的气球的影响
#include#include #include using namespace std;long long sum;int tree[100010];long long lowbit(long long n){ return n&-n;}void add(long long n,long long m){ while(n<=sum) { tree[n]+=m; n+=lowbit(n); }}long long getsum(long long n){ long long h=0; while(n>0) { h+=tree[n]; n-=lowbit(n); } return h;}int main(){ long long n,m,i,a[100010]; while(cin>>sum&&sum) { memset(a,0,sizeof(a)); memset(tree,0,sizeof(tree)); for(i=1;i<=sum;i++) { cin>>n>>m; add(n,1); add(m+1,-1); } for(i=1;i<=sum;i++) { if(i==1)cout<
转载地址:http://ktfci.baihongyu.com/