线段树 TLE 求助

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10; 
struct re{
	int l,r;
	int val;
}tr[N*4];
int n;
int a[N];
struct ree{
	int p;
	int next;
}e[N];
unordered_map<int,int> h;
unordered_map<int,int> last;
int ll(int x){
	return x<<1;
}
int rr(int x){
	return x<<1|1;
}
void init(int p,int l,int r){
	tr[p].l=l;tr[p].r=r;
	if(l==r){
		tr[p].val=abs(a[l]);
		return ;
	}
	int mid=l+r>>1;
	init(ll(p),l,mid);
	init(rr(p),mid+1,r);
	tr[p].val=max(tr[ll(p)].val,tr[rr(p)].val);
}
int ask(int p,int x,int y){
	if(x<=tr[p].l&&y>=tr[p].r){
		return tr[p].val;
	}
	int ans=-1e18;
	int mid=tr[p].l+tr[p].r>>1;
	if(x<=mid) ans=max(ask(ll(p),x,y),ans);
	if(y>mid) ans=max(ask(rr(p),x,y),ans);
	return ans;
}
signed main(){
	scanf("%d",&n);
	bool pd=true;
	int r=1e9+1;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(r==1e9+1) r=abs(a[i]);
		else if(r!=abs(a[i])) pd=false;
		if(last[abs(a[i])]==0){
			if(a[i]>0) a[i]=-a[i];
			last[abs(a[i])]=1;
		}else{
			if(a[i]<0) a[i]=-a[i];
			last[abs(a[i])]=0;
		}
		e[i].p=i;
		e[i].next=h[a[i]];
		h[a[i]]=i;
	}
	if(pd){
		long long x=n/2;
		long long y=(n+1)/2;
		printf("%lld",x*(x-1)/2+y*(y-1)/2);
		return 0;
	}
	init(1,1,n);
	int sum=0; 
	for(int i=1;i<=n;i++){
		for(int j=h[a[i]];j!=0;j=e[j].next){
			if(e[j].p<=i) break;;
			if(ask(1,i,e[j].p)==abs(a[i])) sum++;
		}
	}
	printf("%lld",sum);
	return 0;
}