看到全是线段树或者树状数组写法，就来提供一发全网唯一cdq分治三维偏序解法吧

容易发现，这个题的查询就是对于每个区间l,r，查询有多少个修改区间l_i,r_i与l,r有交集

转化为数学语言，就是查询满足l_i<=r且r_i>=l的修改个数

一个二维偏序问题，但是我们发现，这是个动态插入的二维偏序问题

_(:з」∠)_一时不知所措

再想一想，不妨把时间另开一个维度作为第三维，然后就是这样了

对于每个查询，我们要求出它之前有多少个修改区间与其相交

数学语言：

查询满足l_i<=r且r_i>=l且[l_i,r_i].time<[l,r].time的修改个数

思路清晰明了，而且敲好想，但是实现细节还是比较麻烦的（一部分是因为我的奇葩cdq写法），在代码注释里解释一下（模板这种的就不解释了）

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn=1e5+10;struct node{    int a,b,c,q,w;//a,b,c表示三个维度，q记录这个操作是修改还是查询//w表示这个是否有效（和q差不多，查询是不需要统计的，w=0；修改的w=1）}v[maxn];int n,m,cnt,tot,c[maxn],ans[maxn];bool vis[maxn];bool cmpx(const node &a,const node &b){    return a.a==b.a?(a.b==b.b?a.c
         
          
           
            >1; cdq(l,mid),cdq(mid+1,r); sort(v+l,v+mid+1,cmpy),sort(v+mid+1,v+r+1,cmpy); int i=l,j=mid+1; for(;j<=r;j++) { while(v[i].b<=v[j].b&&i<=mid) add(v[i].c,v[i].w),i++; if(v[j].q==2) ans[v[j].a]+=sum(n)-sum(v[j].c-1); //统计贡献到ans数组中 } for(j=l;j