题意的转化挺巧妙的

可以联想到曼哈顿距离！

并且，所谓的修改还要查询历史版本，并且修改之间不动只算一次，不就是给平面上加一个点吗？

看成(x,a[x])的点

就是一个菱形区域

转切比雪夫距离，变成矩形区域

所以

平面单点加，矩形查询和

1.cdq分治

2.树套树（离散化都不用）

3.二进制分组+主席树

这里，大炮打蚊子，用二进制分组来写

加入的点按操作二进制分组，每个组用主席树维护这个平面，查询在logn上查询，合并暴力重构，256MB又没有删除，所以重构完了把原来的树垃圾回收

注意：

主席树垃圾回收，从最后一个根开始，一个点不能删除两次，所以共用点打die标记，之后搜到返回即可。

代码：

写得很丑

其实不用vector，可以开数组，记录每个组的范围。每次sort，然后建树。

#include
     
      #define reg register int#define il inline#define numb (ch^'0')#define mid ((l+r)>>1)#define fi first#define se second#define mp(a,b) make_pair(a,b)using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=160000+5;const int U=160000;int n,q;pair
      
       a[N];int b[N];char ch[233];struct node{    int ls,rs;    int sum;    void clear(){        ls=rs=sum=0;    }}t[40000*200];int tot;int sta[N],top;int del[40000*200],dc;bool die[40000*200];int nc(){    int r=dc?del[dc--]:++tot;    die[r]=0;    t[r].clear();//    cout<<" r "<
       
        <<" "<
        
         <<" "<
         
          <<" "<
          
           <
           
             >mem[N];vector
            
             rt[N],pos[N];bool cmp(pair
             
              a,pair
              
                b){ //a
               
                 >tmp; int l=0,r=0; for(reg k=1;k<=(int)mem[i].size()+(int)mem[j].size();++k){ if(l>=(int)mem[i].size()){ tmp.push_back(mem[j][r++]); }else if(r>=(int)mem[j].size()){ tmp.push_back(mem[i][l++]); }else if(cmp(mem[i][l],mem[j][r])){ tmp.push_back(mem[i][l++]); }else{ tmp.push_back(mem[j][r++]); } } mem[i]=tmp;}void upda(int &x,int y,int l,int r,int p){ if(!x) x=nc(); t[x].sum=t[y].sum+1; if(l==r){ return;} if(p<=mid){ t[x].rs=t[y].rs;upda(t[x].ls,t[y].ls,l,mid,p); }else{ t[x].ls=t[y].ls;upda(t[x].rs,t[y].rs,mid+1,r,p); }}void remove(int x){ if(!x||die[x]) return; remove(t[x].ls);remove(t[x].rs); t[x].clear(); die[x]=1; del[++dc]=x;}int query(int x,int y,int l,int r,int L,int R){ //cout<<" query "<
                
                 <<" "<
                 
                  <<" "<
                  
                   <<" "<
                   
                    <<" goal "<
                    
                     <<" "<
                     
                      <
                      
                       =0;--i) remove(rt[A][i]); for(reg i=rt[B].size()-1;i>=0;--i) remove(rt[B][i]);// cout<<" guibing "<
                       
                        1&&mem[sta[top]].size()==mem[sta[top-1]].size()){ bing(sta[top-1],sta[top]); --top; } }// cout<
                        
                         <<" "<
                         
                          <
                          
                           1&&mem[sta[top]].size()==mem[sta[top-1]].size()){ bing(sta[top-1],sta[top]); --top; } b[x]=k; /// cout<<" seventy-five "<
                           
                            <