TLE on #8、#9、#10、#11、#13

有没有路过的神仙帮忙看一下复杂度哪里假了（或帮蒟蒻卡卡常）

#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
int n,m,root,tot,N;
#define maxn 100001
#define inf 0x3f3f3f3f
struct SplayTree{
    int son[2],fa,dat,cnt,siz,id;
    #define ls(x) tree[x].son[0]
    #define rs(x) tree[x].son[1]
    #define siz(x) tree[x].siz
    #define cnt(x) tree[x].cnt
    #define fa(x) tree[x].fa
    #define son(x,k) tree[x].son[k]
    #define dat(x) tree[x].dat
    #define id(x) tree[x].id
}tree[maxn];
void updata(int o){
    siz(o)=siz(ls(o))+siz(rs(o))+cnt(o);
}
void rotate(int o){
    int fath=fa(o),gath=fa(fath);
    bool k=(o==rs(fath));
    son(fath,k)=son(o,k^1);
    fa(son(o,k^1))=fath;
    fa(fath)=o;
    son(o,k^1)=fath;
    fa(o)=gath;
    if(gath)son(gath,(rs(gath)==fath))=o;
    updata(fath),updata(o);
}
void splay(int o){
    int fath=fa(o),gath=fa(fath);
    while(fath){
        if(!gath)rotate(o);
        else{
            bool flag=(rs(gath)==fath)^(rs(fath)==o);
            if(flag)rotate(o),rotate(o);
            else rotate(fath),rotate(o);
        }
        fath=fa(o),gath=fa(fath);
    }
    root=o;
    updata(root);
}
void ins(int x,int id){
    int o=root,fath;
    while(1){
        if(dat(o)==x){
            siz(o)++;
            cnt(o)++;
            break;
        }
        bool k=(x>dat(o));
        if(son(o,k))o=son(o,k),fath=o;
        else{
            fath=o;
            o=++tot;
            dat(tot)=x;
            siz(tot)=cnt(tot)=1;
            fa(tot)=fath;
            id(tot)=id;
            son(fath,k)=tot;
            break;
        }
    }
    splay(o);
}
int nex(int x){
    int o=root,ans=1;
    while(o){
        if(dat(o)==x){
            if(rs(o)){
                o=rs(o);
                while(ls(o))o=ls(o);
                ans=o;
            }
            break;
        }
        if(dat(o)>x&&dat(o)<dat(ans))ans=o;
        bool k=(dat(o)<x);
        o=son(o,k);
    }
    return dat(ans);
}
int pre(int x){
    int o=root,ans=2;
    while(o){
        if(dat(o)==x){
            if(ls(o)){
                o=ls(o);
                while(rs(o))o=rs(o);
                ans=o;
            }
            break;
        }
        bool k=(dat(o)<x);
        if(dat(o)<x&&dat(o)>dat(ans))ans=o;
        o=son(o,k);
    }
    return dat(ans);
}
void find(int x){
    int o=root;
    while(o){
        if(dat(o)==x)break;
        int k=(dat(o)<x);
        o=son(o,k);
    }
    splay(o);
}
void del(int x){
    find(x);
    if(cnt(root)>1)cnt(root)--,updata(root);
    else{
        if(!ls(root))root=rs(root),tot--;
        else if(!rs(root))root=ls(root),tot--;
        else{
            find(pre(x));
            rs(root)=rs(rs(root));
            fa(rs(root))=root;
            updata(root);
        }
    }
}
int nex_city[2][maxn],h[maxn];
struct node{
    int dat,id,h;
}d[4];
bool cmp(node a,node b){
    if(a.dat!=b.dat)return a.dat<b.dat;
    else return a.h<b.h;
}
#define ll long long
int f[21][maxn][2];
ll g[21][maxn][2][2];
ll ask(int x,ll s,bool k,bool op){
    ll tmp=0,len=0,now=x;
    for(int i=N;i>=0;i--){
    	if(now==-1)break;
		while(len+g[i][now][k][0]+g[i][now][k][1]<=s){
        	len+=g[i][now][k][0]+g[i][now][k][1];
        	tmp+=g[i][now][k][op];
        	now=f[i][now][k];
        	if(!i)k^=1;
    	}
	}
    return tmp;
}
ll x0;
ll read(){
    char c=getchar();
    int ff=1;
    ll x=0;
    while(c<'0'||c>'9'){if(c=='-')ff=-1;c=getchar();}
    while(c>='0'&&c<='9'){x*=10;x+=c-'0';c=getchar();}
    return x*ff;
}
int main(){
    //freopen("8.in","r",stdin);
    //freopen("0.out","w",stdout);
    n=read();
    ins(inf,0);
    ins(-inf,n+1);
    for(int i=1;i<=n;i++)h[i]=read(),ins(h[i],i);
    for(int i=1;i<=n;i++){
        int cnt=0;
        find(pre(h[i]));
        if(dat(root)!=-inf){
            d[cnt].h=dat(root),d[cnt].dat=h[i]-dat(root),d[cnt++].id=id(root),find(pre(dat(root)));
            if(dat(root)!=-inf)d[cnt].h=dat(root),d[cnt].dat=h[i]-dat(root),d[cnt++].id=id(root);
        }
        find(nex(h[i]));
        if(dat(root)!=inf){
            d[cnt].h=dat(root),d[cnt].dat=dat(root)-h[i],d[cnt++].id=id(root),find(nex(dat(root)));
            if(dat(root)!=inf)d[cnt].h=dat(root),d[cnt].dat=dat(root)-h[i],d[cnt++].id=id(root);
        }
        sort(d,d+cnt,cmp);
        if(cnt<1)nex_city[0][i]=nex_city[1][i]=-1;
        else if(cnt<2)nex_city[1][i]=d[0].id,nex_city[0][i]=-1;
        else nex_city[1][i]=d[0].id,nex_city[0][i]=d[1].id;
        del(h[i]);
    }
    while((1<<N)<=n)N++;
    N--;
    memset(f,-1,sizeof f);
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++){
        int to0=nex_city[0][i],to1=nex_city[1][i];
        f[0][i][0]=to0;
        f[0][i][1]=to1;
        if(~to0)g[0][i][0][0]=abs(h[i]-h[to0]),g[0][i][0][1]=0;
        if(~to1)g[0][i][1][1]=abs(h[i]-h[to1]),g[0][i][1][0]=0;
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=n;j++){
            int pre0=f[i-1][j][0],pre1=f[i-1][j][1];
            if(i==1){
                if(~pre0)f[i][j][0]=f[i-1][pre0][1];
                if(~pre1)f[i][j][1]=f[i-1][pre1][0];
            }
            else{
                if(~pre0)f[i][j][0]=f[i-1][pre0][0];
                if(~pre1)f[i][j][1]=f[i-1][pre1][0];
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=n;j++){
            int pre0=f[i-1][j][0],pre1=f[i-1][j][1];
            if(i==1){
                if(~pre0)g[i][j][0][0]=g[i-1][j][0][0]+g[i-1][pre0][1][0],g[i][j][0][1]=g[i-1][j][0][1]+g[i-1][pre0][1][1];
                if(~pre1)g[i][j][1][0]=g[i-1][j][1][0]+g[i-1][pre1][0][0],g[i][j][1][1]=g[i-1][j][1][1]+g[i-1][pre1][0][1];
            }
        }
    }
    x0=read();
    double frac=inf;
    int ans;
    for(int i=1;i<=n;i++){
    	ll tmp0=ask(i,x0,0,0),tmp1=ask(i,x0,0,1);
    	if(!tmp1)continue;
    	double tmp=(double)tmp0/(double)tmp1;
    	if(tmp<frac)ans=i,frac=tmp;
	}
	printf("%d\n",ans);
    m=read();
	for(int i=1;i<=m;i++){
		ll s,x;
        s=read(),x=read();
		printf("%lld %lld\n",ask(s,x,0,0),ask(s,x,0,1));
	}
    return 0;
}