[Usaco2015 dec]Breed Counting

原题链接https://www.lydsy.com/JudgeOnline/problem.php?id=4397

用线段树维护区间和即可。时间复杂度\(O((N+Q)logN)\)。

#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,0,0};

        if(l<=mid)

            getsum(d<<1,l,r,sum[1],sum[2],sum[3]),ans1=sum[1],ans2=sum[2],ans3=sum[3];

        if(r>mid)

            getsum(d<<1|1,l,r,sum[1],sum[2],sum[3]),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,l,r,ans1,ans2,ans3);

        printf("%d %d %d\n",ans1,ans2,ans3);

    }

    return 0;

}

巴特西

[Usaco2015 dec]Breed Counting

原题链接https://www.lydsy.com/JudgeOnline/problem.php?id=4397

用线段树维护区间和即可。时间复杂度\(O((N+Q)logN)\)。

最新文章

热门文章