神秘树状数组优化AC，求问时间复杂度

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define int long long
#define PII pair<int,int>
#define fir first
#define sec second
using namespace std;
//v>V 瓒呴€?
namespace Main{
	const int N=1e5+7;
	int T,ret;
	int n,m,L,V;
	struct Car{
		int d,v,a;
	}s[N];
	int p[N];
	int tr[N];
	bool st[N];
	inline int lowbit(int x){
		return x&-x;
	}
	inline void add(int a,int b){
		for(int i=a;i<=n;i+=lowbit(i)){
			tr[i]+=b;
		}
		return ;
	}
	inline int query(int x,int res){
		for(int i=x;i;i-=lowbit(i)){
			res+=tr[i];
		}
		return res;
	}
	inline void main(){
		scanf("%lld",&T);
		while(T--){
			vector<PII> res={};
			scanf("%lld%lld%lld%lld",&n,&m,&L,&V);
			for(int i=1;i<=n;i++){
				auto &d=s[i].d,&v=s[i].v,&a=s[i].a;
				scanf("%lld%lld%lld",&d,&v,&a);
			}
			for(int i=1;i<=m;i++){
				scanf("%lld",&p[i]);
			}
			sort(p+1,p+m+1);
			for(int i=1;i<=n;i++){
				auto &t=s[i];
				int d=t.d,v=t.v,a=t.a;
				if(!a){
					if(v>V){
						int u=lower_bound(p+1,p+m+1,d)-p;
						if(u<=m){
							res.push_back({u,m});
							add(u,1),add(m+1,-1);
						}
					}
				}
				else{
					int u=lower_bound(p+1,p+m+1,d)-p;
					bool flag=false,isadd=false;
					int st;
					for(int i=u;i<=m;i++){
						int dist=p[i]-d;
						int speed=v*v+2*a*dist;
						if(speed>V*V){
							if(!flag){
								st=i;
								flag=true;
							}
							if(a>0){
								isadd=true;
								res.push_back({i,m});
								add(i,1),add(m+1,-1);
								break;
							}
						}
						else{
							if(flag){
								isadd=true;
								res.push_back({st,i-1});
								add(st,1),add(i,-1);
								break;
							}
						}
					}
					if((!isadd)&&flag){
						res.push_back({st,m});
						add(st,1),add(m+1,-1);
					}
				}
			}
			if(!res.size()){
				printf("0 %lld\n",m);
				continue;
			}
			sort(res.begin(),res.end(),[&](PII a,PII b){
				return b.sec<a.sec?1:(b.sec==a.sec?a.fir>b.fir:0);
			});
			for(int i=res.size()-1;i>=0;i--){
				if(st[i]){
					continue;
				}
				auto u=res[i];
				int cnt=0,ans;
				for(int j=u.sec;j>=u.fir;j--){
					int k=query(j,0);
					if(k>=cnt){
						cnt=k;
						ans=j;
					}
				}
				++ret;
				for(int j=i;j>=0;j--){
					if(st[j]){
						continue;
					}
					if(res[j].fir<=ans&&res[j].sec>=ans){
						add(res[j].fir,-1),add(res[j].sec+1,1);
						st[j]=1;
					}
					else{
						break;
					}
				}
			}
			printf("%lld %lld\n",(long long)res.size(),m-ret);
			ret=0;
			memset(st,0,sizeof st);
		}
		return ;
	}
}
signed main(){
	Main::main();
	return 0;
}