线段树每个节点维护d[4][4]表示四个顶点之间的最短路，合并时用Floyed合并，查询时分三段然后合并。

 

#include
     
      #define N 100010struct P{int d[4][4];}T[N<<2],tmp;int n,m,op,x,y,u,v,i,j,k,a[N],b[N],c[N],f[8][8],g[8][8],inf=~0U>>2,flag,ans,d1,d2;inline void up(int&x,int y){if(x>y)x=y;}inline void floyed(int n){for(k=0;k
      
       
        
         1?i+2:i][j>1?j+2:j];}void build(int x,int a,int b){  if(a+1==b){cal(T[x],a);return;}  int mid=(a+b)>>1;  build(x<<1,a,mid),build(x<<1|1,mid,b),up(T[x],T[x<<1],T[x<<1|1]);}void change(int x,int a,int b,int c){  if(a+1==b){cal(T[x],a);return;}  int mid=(a+b)>>1;  if(c
         
          <<1,a,mid,c);else change(x<<1|1,mid,b,c);  up(T[x],T[x<<1],T[x<<1|1]);}void ask(int x,int a,int b,int c,int d){  if(c<=a&&b<=d){    if(!flag)flag=1,tmp=T[x];else up(tmp,tmp,T[x]);    return;  }  int mid=(a+b)>>1;  if(c
          
           <<1,a,mid,c,d); if(d>mid)ask(x<<1|1,mid,b,c,d);}int main(){ scanf("%d",&n); for(i=1;i
           
            1)change(1,1,n,y-1); }else{ if(x==y){puts("0");continue;} if(x>y)i=x,x=y,y=i; u=(x+1)/2,v=(y+1)/2,d1=x&1^1,d2=y&1^1; if(u==v){ ans=b[u]; if(u>1)flag=0,ask(1,1,n,1,u),up(ans,tmp.d[2][3]); if(u
            
             1)for(flag=0,ask(1,1,n,1,u),i=0;i<4;i++)for(j=0;j<4;j++)up(g[i][j],tmp.d[i][j]); if(v
             
              <4;i++)for(j=0;j<4;j++)up(g[i+4][j+4],tmp.d[i][j]); for(i=0;i<8;i++)for(j=0;j<8;j++)f[i][j]=g[i][j]; floyed(8); ans=f[2+d1][4+d2]; } printf("%d\n",ans); } } return 0;}