求分析代码时间复杂度

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N=1e6+5;
int n,k,q,a[N],t[N],min_l[N],cnt[N],ans[N];
vector<int> tree[4*N];
pair<int,int> temp[N],b[N];
inline int lc(int x){return x<<1;}
inline int rc(int x){return x<<1|1;} 
inline void build(int now,int l,int r){
	if(l==r){
		tree[now].push_back(t[l]);
		return;
	}
	int mid=l+r>>1;
	build(lc(now),l,mid);
	build(rc(now),mid+1,r);
	tree[now].resize(r-l+1);
	merge(tree[lc(now)].begin(),tree[lc(now)].end(),tree[rc(now)].begin(),tree[rc(now)].end(),tree[now].begin());
}
inline int query(int now,int l,int r,int ql,int qr,int x){
	if(l>qr||r<ql) return 0;
	if(ql<=l&&r<=qr) return upper_bound(tree[now].begin(),tree[now].end(),x)-tree[now].begin();
	int mid=l+r>>1;
	return query(lc(now),l,mid,ql,qr,x)+query(rc(now),mid+1,r,ql,qr,x);
}
int lowbit(int x){return x&-x;}
void update(int x){
	while(x<=n){
		cnt[x]++;
		x+=lowbit(x);
	}
}
int get_sum(int x){
	int res=0;
	while(x){
		res+=cnt[x];
		x-=lowbit(x);
	}
	return res;
}
int Q(int l,int r){return get_sum(r)-get_sum(l-1);}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k>>q;
	for(int i = 1;i<=n;i++) cin>>a[i],t[a[i]]=i;
	build(1,1,n);
	for(int i = 1;i<=n;i++){
        if(i<=k){
            min_l[i]=0;
            continue;
        }
		int R=a[i]-1;
		if(R<1){
			min_l[i]=0;
			continue;
		}
		int val=query(1,1,n,1,R,i);
		if(val<k) min_l[i]=0;
		else{
			int l=1,r=i,res=i;
			while(l<=r){
				int mid=l+r>>1;
				if(query(1,1,n,1,R,mid)>=val-k+1) res=mid,r=mid-1;
				else l=mid+1;
			}
			min_l[i]=res;
		}
	}
	vector<tuple<int,int,int>> qry;
	for(int i = 1;i<=q;i++) cin>>temp[i].x>>temp[i].y,qry.push_back({temp[i].x,temp[i].y,i});
	sort(qry.begin(),qry.end());
	for(int i = 1;i<=n;i++) b[i]={min_l[i],i};
	sort(b+1,b+1+q);
	int j=1;
	for(auto &[l,r,id]:qry){
        while(j<=n&&b[j].x<l) update(b[j].y),j++;
		ans[id]=Q(l,r);
	}
	for(int i = 1;i<=q;i++) cout<<ans[i]<<'\n';
}