hdu-1556 Color the ball && nyoj -123 士兵杀敌（四）----------》树状数组-白红宇

hdu-1556 Color the ball && nyoj -123 士兵杀敌（四）----------》树状数组

阅读量：4286 次

发布时间：2019-05-27

本文共 1717 字，大约阅读时间需要 5 分钟。

hdu-1556

#include
    
     #include
     
      int n,a[100005];int lowbit(int x){    return x&(-x);}int Getsum(int pos){    int res = 0;    while(pos > 0)    {        res += a[pos];        pos -= lowbit(pos);    }    return res;}void add(int pos,int num){    while(pos <= n)    {        a[pos] += num;        pos += lowbit(pos);    }}int main(){    int t,x,y;    char s[20];    while(scanf("%d",&n),n)    {        memset(a,0,sizeof(a));        for(int i = 1;i <= n;i++)        {            scanf("%d%d",&x,&y);            add(x,1);            add(y+1,-1);        }        printf("%d",Getsum(1));        for(int i = 2;i <= n;i++)        {            printf(" %d",Getsum(i));        }        printf("\n");    }}

&& 1556（简单巧妙的方法）

#include
    
     #include
     
      int main(){    int n,a,b,s[100005];    while(scanf("%d",&n),n)    {        memset(s,0,sizeof(s));        for(int i=1;i<=n;i++)        {            scanf("%d%d",&a,&b);            s[a]++;s[b+1]--;        }        int ant=s[1];        for(int i=1;i

nyoj-123

#include
   
    int m[1000001],i,N,n;int lowbit(int x){    return x&(-x);}int GetSum(int pos){    int res=0;    while(pos>0)    {        res+=m[pos];        pos-=lowbit(pos);    }    return res;}void push(int pos,int num){    while(pos<=N)    {        m[pos]+=num;        pos+=lowbit(pos);    }}int main(){    char a[8];    int b,c,d,f;    memset(m,0,sizeof(m));    scanf("%d%d",&n,&N);    getchar();    while(n--)    {        scanf("%s ",a);        if(a[0]=='A')        {            scanf("%d%d%d",&b,&c,&d);            push(b,d);            push(c+1,-d);        }        else        {            scanf("%d",&f);            printf("%d\n",GetSum(f));        }    }    return 0;}

转载地址：http://vysgi.baihongyu.com/

你可能感兴趣的文章