这题虽然是个树状数组，但是也可以用cdq分治做啊~~，这个就是一个浅显的二维偏序的应用？

cdq分治和普通的分治有什么区别？

举个栗子：有4个小朋友，你请他们吃饭，假如你分治搞，就会分成很多子问题——1~1号小朋友有多少个来，2~2号小朋友有多少个来，然后程序就会回溯，你就知道1~2号小朋友有多少个来，最后你就知道1~4号小朋友有多少个来了。

而cdq分治呢？同样是4个小朋友，但是要照顾小朋友的心情，第i号小朋友的开心程度是1~i-1号小朋友有多少个来，你想知道小朋友们的心情，有可能心情不好就不来了，那先往左右搜，然后要把心情的影响加上。可能这个栗子不是很贴切，但是我想说的就是cdq分治中，前面的结果会影响后面的，而且，这个算法做题只能离线。

那么，我是拿了这题水题来理解。

俩操作，一个单点修改，一个询问区间和。

那么我们还是照样按前缀和的做法，把询问分成求1~l-1和1~r。

那么离线做，按照输入的顺序放进结构体，这个时候你一定发现了，对于一个询问，对它有影响的修改，就是在它前面操作的，并且修改位置也在它询问位置前面的。那么，实际上这个结构体已经是按照操作的顺序排好了，那么要解决的就是位置的问题。具体的做法，就是按照它的位置，做一次归并排序。

具体怎么做呢，首先先把区间分成l~mid和mid+1~r，当前我们要维护的，就是mid+1~r的全部询问，要先让两边都递归下去，令l~mid的询问解决，以及mid+1~r里的修改施加影响。

那么在归并的过程中，记录一个sum，表示左边已经l~当前归并到的位置的修改值的和，然后当遇到右边的询问，就将影响释放下去，一直这样做下去，当按x排好序了，对于mid+1~r中的询问，l~r的全部影响都已经解决，最后回溯接受更前面的影响，或者去影响后面的其他询问（你这样归排岂不是把一开始操作的顺序打乱了！？不用担心，l~mid的输入顺序每一个都是比mid+1~r大的，l~mid的顺序改变并不会影响后面的修改）

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;int n,m;struct node{ int x,tp;LL v; //tp=1表示这个是修改操作，x表示修改哪个位置，v表示要加上的值 //tp=2,3表示这个是问1~x的前缀和，v表示这个影响第几个答案 }a[210000],t[210000];int len=0;void ins(int x,int tp,int v){ len++; a[len].x=x;a[len].tp=tp;a[len].v=v;}LL ans[210000];int ansl=0;//答案数组bool check(node n1,node n2){ if(n1.x