用途：

解决 “带时间轴的更改和查询” 问题。

算法流程：

首先我们要知道，这个算法是离线的，还是利用递归进行求解的。

把读入的n个操作都按照时间轴排列好。
把时间轴劈开，分为[l,mid]和[mid+1,r]两部分。
开始当前层cdq(l,r)的求解前先进行cdq(l,mid)与cdq(mid+1,r)的求解。
拎出区间[l,mid]内的所有修改操作和区间[mid+1,r]内的所有查询操作[mid+1,r]。
统计区间[l,mid]内的所有修改操作对区间[mid+1,r]内的所有查询操作的影响，并将影响加入ans数组中。

关于算法的正确性：

为什么这么做会是对的呢？我们不妨举个例子来看看。

加入一共有7个时刻（或者说是个7操作），对于位于3时刻的修改操作，在cdq(1,7)中，统计了它对于区间[5,7]中查询的影响，又在cdq(3,4)中统计了区间[4,4]中查询的影响。

可以看到，对于位于3时刻的查询操作，在我们的cdq过程中，统计了它对于[4,7]的时刻中，所有查询操作的影响。

例题以及题解：

例题：

BOI 2007 【Mokia 摩基亚】洛谷里有，P4390。

题目概述：

（至于为什么是概述呢？——题目B话太TM多了！！！

给你一个二维平面直角坐标系，还有一些操作。

操作有两种：

1.格式"(1,x,y,w)"，表示在(x,y)的地方加上权值w。
2.格式"(2,sx,sy,ex,ey)"，表示询问以(sx,sy)为左上角顶点，(ex,ey)为右下角顶点，询问矩形区间内的权值和。

后面的修改操作不会对前面的查询操作产生影响。

数据：操作数<=200000，x,y,sx,sy,ex,ey<=2000000

思路分析：

大家还是先打消要用二维树状数组的念头吧

是二维的，那么我们应该怎么做呢？（先提示下吧，log²的，大家可以先想一想）

滴，滴，滴，滴————————

好，时间到，那就再给大家一个提示吧。

某名Niro**的dalao（他/她真的是dalao）说过：“CDQ分治就是花log n的时间，把所有的修改操作都移到查询操作之前。”

再想想。。。。。。

（假如说还没有想到的话，可以先看一下下文中那些大号加粗的字，看看有没有思路啥的）

（想到了的话，就可以把这篇博客关掉了，再顺手点个推荐啥的）

嗯，现在就到我讲了吧！

二维的，又不能用二维树状数组，再看看博客标题——“CDQ分治”。

en~~~~~

那就肯定是CDQ分治啦！！！

那么当我们把所有的修改都放在查询后面之后，我们应该怎么做呢？

显然要对问题进行“降维打击”。

这个降维打击是个啥呢？——就是把1、2操作（其中把2操作变成起始和结束的两个点）对于x轴进行排序嘛。

排序之后，我们就可以保证在x轴上，前面做过的修改操作，在x轴上是永远包含于后面的查询操作的（如果它的x坐标大于当前查询操作右端点对应的左端点的）。

那么我们只要维护y轴就可以了，这个可以用树状数组来维护。

具体方法的话就是，给树状数组中修改点的y坐标加上它的权值，然后遇到查询操作的右端点时，就统计一下y取值范围内的和就可以了。

那么最后的一个问题就是如果修改点的x坐标小于查询当前查询操作右端点对应的左端点我们应该怎么办呢？

大家先思考一下吧。

......

~~~好了吗？我说喽。——差分嘛！

具体方法就是——遇到左端点时，先把当前树状数组中属于询问范围的y的区间和给减掉嘛。

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
struct point{
    int x,y,id;
};
point a[N],b[N<<1];
int x[N],y[N],sx[N],sy[N],ex[N],ey[N],w[N],ans[N],c[2000005],acnt,bcnt,tot,opt;
bool cmp (point a,point b){
    return a.x<b.x;
}
void update(int x,int val){
    if (x<=2000000) c[x]+=val,update(x+(x&(-x)),val);
}
int query(int x){
    if (x>0) return c[x]+query(x-(x&(-x))); else return 0;
}
void cdq(int l,int r){
    if (l==r) return;
    int mid=l+r>>1; 
    cdq(l,mid); cdq(mid+1,r);
    acnt=0,bcnt=0;
    for (int i=l;i<=mid;i++)
        if (x[i]>0) ++acnt,a[acnt].x=x[i],a[acnt].y=y[i],a[acnt].id=i;
    for (int i=mid+1;i<=r;i++)
        if (sx[i]>0) 
            ++bcnt,b[bcnt].x=sx[i]-1,b[bcnt].y=sy[i],b[bcnt].id=i,
            ++bcnt,b[bcnt].x=ex[i],b[bcnt].y=ey[i],b[bcnt].id=i;
    sort(a+1,a+1+acnt,cmp);
    sort(b+1,b+1+bcnt,cmp);
    int i=1,j=1;
    while (i<=acnt||j<=bcnt)
        if (j>bcnt||i<=acnt&&a[i].x<=b[j].x) 
            update(a[i].y,w[a[i].id]),++i;
        else 
            if (b[j].x==sx[b[j].id]-1&&b[j].y==sy[b[j].id]) 
                ans[b[j].id]-=query(ey[b[j].id])-query(b[j].y-1),j++;
            else 
                ans[b[j].id]+=query(b[j].y)-query(sy[b[j].id]-1),j++;
    for (int i=l;i<=mid;i++) 
        if (x[i]>0) update(y[i],-w[i]);
}
int main(){
    scanf("0 %d",&w[0]);
    scanf("%d",&opt);
    while (opt!=3){
        if (opt==1) ++tot,scanf("%d%d%d",&x[tot],&y[tot],&w[tot]);
        else ++tot,scanf("%d%d%d%d",&sx[tot],&sy[tot],&ex[tot],&ey[tot]);
        scanf("%d",&opt);
    }
    cdq(1,tot);
    for (int i=1;i<=tot;i++)
        if (sx[i]>0) printf("%d
",ans[i]);
    return 0;
}