脚本宝典收集整理的这篇文章主要介绍了[Usaco2015 dec]Breed Counting,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
#include<iostream> #include<cstring> #include<cstdio> #define maxn 100010 using namespace std; inline int read(){ register int x(0),f(1); register char c(getchar()); while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); } while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,q,a[maxn]; struct SegmentTree{ struct node{ int l,r,sum[4]; }t[maxn<<2]; void build(int d,int l,int r){ t[d].l=l,t[d].r=r; if(l==r){ for(register int i=1;i<=3;i++) t[d].sum[i]=0; t[d].sum[a[l]]=1; return; } int mid=(l+r)>>1; build(d<<1,l,mid),build(d<<1|1,mid+1,r); for(register int i=1;i<=3;i++) t[d].sum[i]=t[d<<1].sum[i]+t[d<<1|1].sum[i]; } void getsum(int d,const int &l,const int &r,int &ans1,int &ans2,int &ans3){ if(l<=t[d].l&&t[d].r<=r){ ans1=t[d].sum[1],ans2=t[d].sum[2],ans3=t[d].sum[3]; return; } int mid=(t[d].l+t[d].r)>>1,sum[4]={0,0}; if(l<=mid) getsum(d<<1,sum[1],sum[2],sum[3]),ans1=sum[1],ans2=sum[2],ans3=sum[3]; if(r>mid) getsum(d<<1|1,ans1+=sum[1],ans2+=sum[2],ans3+=sum[3]; } }tree; int main(){ n=read(),q=read(); for(register int i=1;i<=n;i++) a[i]=read(); tree.build(1,1,n); for(register int i=1;i<=q;i++){ int l=read(),r=read(),ans1=0,ans2=0,ans3=0; tree.getsum(1,ans1,ans2,ans3); PRintf("%d %d %d\n",ans3); } return 0; }
以上是脚本宝典为你收集整理的[Usaco2015 dec]Breed Counting全部内容,希望文章能够帮你解决[Usaco2015 dec]Breed Counting所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。