CDQ分治

\(code :\)

void cdq(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);
    sort(q+l,q+mid+1,cmp2);
    sort(q+mid+1,q+r+1,cmp2);
    int pos=l;
    for(int i=mid+1;i<=r;++i)
    {
        while(q[i].b>=q[pos].b&&pos<=mid)
        {
            update(q[pos].c,q[pos].val);
            pos++;
        }
        q[i].ans+=query(q[i].c);
    }
    for(int i=l;i<pos;++i) update(q[i].c,-q[i].val);
}

原文：https://www.cnblogs.com/lhm-/p/12229595.html