forestkeeper

C++博客 首页 新随笔 联系 聚合 管理
  3 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks
一道套数据结构的题

题意是说,蚂蚁有n个等级(level),每个等级初始都有一定量的蚂蚁,随后有一系列操作,p a b操作表示把level  a的蚂蚁个数转换成b,q  x  表示询问在所有蚂蚁里排名第x的蚂蚁在哪个等级。

首先一共有的蚂蚁数为所有level蚂蚁数量总和,不能为每个蚂蚁都开一个int数组去存它的level(如果数据量很小则这种方法可以是o(n)的)。对存着每个层的蚂蚁可以用求和与x比较来确定它处于哪个level。由于n的数量级,故希望能采用log n级的方法来处理,恰好由线段树实现的子段和,其无论是更新(update)还是查询(query)都是log n级的,同时在查询时可再加一二分,即sort(0,n)开始,于是查询的复杂度为logn*logn,最终280ms AC。附代码,代码中未用线段树,而是使用了树状数组同样是logn的查找及更新复杂度,空间复杂度及编程复杂度比线段树低。

#include <cstring> 
#include
<cstdio>
const int MAXN = 100000
 
inline 
int lowbit(int x) 
    
return (x & (x ^ (x - 1))); 
}
 
 
template
<class elemType> 
class Sum
public
    elemType a[MAXN], c[MAXN], ret; 
    
int n; 
 
    
void init(int i) 
        memset(a, 
0sizeof(a)); 
        memset(c, 
0sizeof(c)); 
        n 
= i; 
    }
 
 
    
void update(int i, elemType v) 
        v 
-= a[i]; 
        a[i] 
+= v; 
        
for (i++; i <= n; i += lowbit(i)) 
            c[i 
- 1+= v; 
        }
 
    }
 
     elemType query(
int i) 
        
for (ret = 0; i; i ^= lowbit(i)) 
            ret 
+= c[i-1]; 
        }
 
        
return ret; 
    }
 
}
;
Sum
<int>sum; 

int Sort(int l,int r,int x)
{
    
if(l>=r-1)
       
return l;
    
int pos = (l+r)/2;
    
if (pos==1)
      
return pos;
    
int p1 = sum.query(pos);
    
int p2 = sum.query(pos-1);
    
if(x>p1&&x<=p2)
      
return pos;
    
int ans;
    
if(x>p2)
      ans 
= Sort(pos,r,x);
    
else ans = Sort(l,pos,x);
     
return ans;
}

int main()
{
    
int n;
    
while(scanf("%d",&n)!=EOF)
    
{
    sum.init(n);
    
for (int i =0; i<n; i++)
    
{
        
int a;
        scanf(
"%d",&a);
        sum.update(i,a);
    }

    
int m;
    scanf(
"%d",&m);
    
for (int i =0; i<m; i++)
    
{
        
char c[20];
        scanf(
"%s",c);
        
if (c[0]=='p')
        
{
            
int a,b;
            scanf(
"%d%d",&a,&b);
            sum.update(a
-1,b);
        }

        
else
        
{
            
int x;
            scanf(
"%d",&x);
            
int ans = Sort(1,n+1,x);
            printf(
"%d\n",ans);
        }

    }

    }

}
posted on 2010-01-03 11:07 forestkeeper 阅读(1196) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理