qduoj 帅气的HYC的珍珠（树状数组）

本文主要是介绍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 复制

样例输出1

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的珍珠（树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！