一道套数据结构的题
题意是说，蚂蚁有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, 0, sizeof(a));
memset(c, 0, sizeof(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);
}
}
}
}