本文主要是介绍qduoj 帅气的HYC的珍珠 （树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://qduoj.com/problem/37/点击打开链接
帅气的HYC的珍珠
发布时间: 2015年11月1日 17:02 最后更新: 2015年11月2日 19:52 时间限制: 1000ms 内存限制: 128M
帅气的HYC经常早晨去锻炼(多么好的习惯～。有一天，他看到一路上的露珠，心里便产生了一个问题：一路上假如有N棵草，每颗草上可能会有露珠，或者没有露珠。连续的露珠会和为一体(>=2)，并变为珍珠。
比如第1棵草上有露珠，第2棵草也有露珠。那么就会形成一个珍珠。第1棵草上有露珠，第2棵草有露珠，第3棵也有露珠，那么也会形成一个珍珠。相反，如果第1颗草有露珠，第2棵草没有露珠，就不会形成珍珠。
现在给你HYC今天早晨一路上的看到的N棵草，以及上面的露珠情况，给你Q次询问，每次询问［L,R],你能快速的告诉HYC，这个区间能形成多少个珍珠吗？ACCEPTIT!
第1行一个整数T，表示有T组测试数据。(T<=15)
第2行一个整数N， 表示有N棵草。(1<=N<=1000)
第3行有N个整数0或者1，中间用空格隔开， 1代表第i课草有露珠，0代表第i棵草没有露珠。
第4行是一个整数Q， 代表查询的次数。(1<=Q<=100000)
下面第（4+Q）行每行两个整数L， R。 代表查询的区间［L， R］；（1<=L<=R<=N）
对于每组查询输出一行。
1 4 1 1 0 1 3 1 2 2 3 1 4
1 0 1
看了学长的代码才会 因为区间查询时考虑的情况很多 树状数组会比线段树方便很多
#include <iostream>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <limits>
#include <string>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
using namespace std;
#define maxn 500005
int aa[maxn];
int a[maxn];
int lowbits(int x)
{return x&(-x);
}
int getsum(int pos)
{int ans=0;while(pos>0){ans+=aa[pos];pos-=lowbits(pos);}return ans;
}
void update(int pos,int val)
{while(pos<=maxn){aa[pos]+=val;pos+=lowbits(pos);}
}
int main(void)
{int t;int n,m;scanf("%d",&t);while(t--){scanf("%d",&n);memset(a,0,sizeof(a));for(int i=1;i<=n;i++)scanf("%d",&a[i]);memset(aa,0,sizeof(aa));for(int i=3;i<=n;i++)if(a[i-2]&&a[i-1]&&!a[i])update(i-1,1);if(a[n] && a[n-1]) update(n, 1);int m,l,r;scanf("%d",&m);while(m--){scanf("%d%d",&l,&r);if(l==r){printf("0\n");continue;}int ans=getsum(r)-getsum(l-1);if(a[r]&&a[r-1]&&a[r+1]) ans++;if(a[l-1]&&a[l]&&!a[l+1]) ans--;printf("%d\n",ans);}}return 0;
}
这篇关于qduoj 帅气的HYC的珍珠 （树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
