BZOJ2989 数列（二进制分组）

这题其实可以cdq分治做，但是如果强制在线的话，这里有个牛逼方法叫二进制分组。

它的基本思想是把修改操作按二进制分组，遇到修改就在尾部加一个，并与之前的合并，比如之前有23（16+4+2+1）个，加了一个后就变成了24（16+8）个，遇到查询就在每个组内查询，再加起来就好了。

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

#define M ((l+r)>>1)

#define mk(a,b) make_pair(a,b)

typedef pair<int,int> pr;

const int N=,A=N+;

char op[];

int n,q,x,y,tt,tp,a[N],rt[][],rb[],vs[];

vector<pr> v[];

struct nd {int l,r,s;}t[];

void ins2(int &x,int ls,int l,int r,int v) {

    t[x=rb[tt--]].s=t[ls].s+,vs[x]=;

    if(l==r) return;

    if(v<=M) t[x].r=t[ls].r,ins2(t[x].l,t[ls].l,l,M,v);

    else t[x].l=t[ls].l,ins2(t[x].r,t[ls].r,M+,r,v);

}

int qr2(int x,int y,int l,int r,int L,int R) {

    if(L<=l&&R>=r) return t[x].s-t[y].s;

    if(R<=M) return qr2(t[x].l,t[y].l,l,M,L,R);

    if(L>M) return qr2(t[x].r,t[y].r,M+,r,L,R);

    return qr2(t[x].l,t[y].l,l,M,L,R)+qr2(t[x].r,t[y].r,M+,r,L,R);

}

void dl(int x,int l,int r) {

    if(vs[x]) return;

    rb[++tt]=x,vs[x]=,dl(t[x].l,l,M),dl(t[x].r,M+,r),t[x].s=t[x].l=t[x].r=;

}

void ins(int x,int y) {

    v[++tp].push_back(mk(x,y)),ins2(rt[tp][],rt[tp][],,A,y);

    while(tp>&&v[tp-].size()==v[tp].size()) {

        int t1=,t2=; vector<pr> t;

        for(int i=;i<=v[tp-].size();i++) dl(rt[tp-][i],,A);

        for(int i=;i<=v[tp].size();i++) dl(rt[tp][i],,A);

        while(t1<v[tp-].size()||t2<v[tp].size()) {

            if(t1<v[tp-].size()&&(t2==v[tp].size()||v[tp-][t1]<v[tp][t2]))

                t.push_back(v[tp-][t1++]),ins2(rt[tp-][t1+t2],rt[tp-][t1+t2-],,A,v[tp-][t1-].second);

            else t.push_back(v[tp][t2++]),ins2(rt[tp-][t1+t2],rt[tp-][t1+t2-],,A,v[tp][t2-].second);

        }

        v[tp-]=t,v[tp].clear(),tp--;

    }

}

int qr(int x,int y,int k3) {

    int r=;

    for(int i=;i<=tp;i++) {

        int k=lower_bound(v[i].begin(),v[i].end(),mk(x+k3,0x3f3f3f3f))-v[i].begin();

        int k2=lower_bound(v[i].begin(),v[i].end(),mk(x-k3,))-v[i].begin();

        r+=qr2(rt[i][k],rt[i][k2],,A,max(,y-k3),min(y+k3,A));

    }

    return r;

}

int main() {

    scanf("%d%d",&n,&q),vs[]=;

    for(int i=;i<;i++) rb[++tt]=i,vs[i]=;

    for(int i=;i<=n;i++) scanf("%d",&a[i]),ins(a[i]+i,a[i]-i+N);

    while(q--) {

        scanf("%s%d%d",op,&x,&y);

        if(op[]=='Q') printf("%d\n",qr(a[x]+x,a[x]-x+N,y));

        else a[x]=y,ins(y+x,y-x+N);

    }

    return ;

}