ZOJ 3279 Ants 二分树状数组

----------

const int maxn=110000;
const int maxm=10000;
int n,m;
struct BIT{
    int n;
    int tree[maxn];
    void init(int n){
        this->n=n;
        memset(tree,0,sizeof(tree));
    }
    int lowbit(int x){
        return x&(-x);
    }
    void add(int x,int val){
        for (int i=x;i<=n;i+=lowbit(i)) tree[i]+=val;
    }
    int query(int x){
        int ret=0;
        for (int i=x;i>0;i-=lowbit(i)) ret+=tree[i];
        return ret;
    }
    //离散 p=lower_bound(b+1,b+n+1,a[i])-b;
    //逆序数 x=(i-1)-query(p);add(p,1);
}bt;
int a[maxn];
int main(){
    while (~scanf("%d",&n)){
        bt.init(n);
        for (int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            bt.add(i,a[i]);
        }
        scanf("%d",&m);
        char s[2];
        while (m--){
            scanf("%s",s);
            if (s[0]=='p'){
                int x,y;
                scanf("%d%d",&x,&y);
                bt.add(x,-a[x]);
                bt.add(x,y);
                a[x]=y;
            }
            else if (s[0]=='q'){
                int x,l=1,r=n,ans=0;
                scanf("%d",&x);
                while (l<=r){
                    int mid=(l+r)/2;
                    if (bt.query(mid)<x){
                        ans=mid;
                        l=mid+1;
                    }
                    else r=mid-1;
                }
                printf("%d
",ans+1);
            }
        }
    }
	return 0;
}

----------