一道套數(shù)據(jù)結(jié)構(gòu)的題
題意是說，螞蟻有n個等級（level），每個等級初始都有一定量的螞蟻，隨后有一系列操作，p a b操作表示把level a的螞蟻個數(shù)轉(zhuǎn)換成b，q x 表示詢問在所有螞蟻里排名第x的螞蟻在哪個等級。
首先一共有的螞蟻數(shù)為所有l(wèi)evel螞蟻數(shù)量總和，不能為每個螞蟻都開一個int數(shù)組去存它的level（如果數(shù)據(jù)量很小則這種方法可以是o（n）的）。對存著每個層的螞蟻可以用求和與x比較來確定它處于哪個level。由于n的數(shù)量級，故希望能采用log n級的方法來處理，恰好由線段樹實現(xiàn)的子段和，其無論是更新（update）還是查詢（query）都是log n級的，同時在查詢時可再加一二分，即sort（0，n）開始，于是查詢的復(fù)雜度為logn*logn，最終280ms AC。附代碼，代碼中未用線段樹，而是使用了樹狀數(shù)組同樣是logn的查找及更新復(fù)雜度，空間復(fù)雜度及編程復(fù)雜度比線段樹低。
#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);
}
}
}
}