I-小鸡的排列构造的checker

原题：I-小鸡的排列构造的checker

题意：

给定一个长度为 n 的排列以及 m 次询问，每次询问给出 l, r, c，分别表示查询的区间 [l, r]，查询的下标 c，问在区间 [l, r] 内进行从小到大排序，原来下标为 c 的数经过排序后的下标是多少？（下标是对于整个数组来说的，不是对于区间来说；每次查询不会改变原数组的位置）

思路：

树状数组离线查询

• 查询 [l,r,c] 相当于问 [l,r] 区间有多少个小于等于 p[c] 的数
• 因为比 p[c] 小的数将要排在 p[c] 前面，再加上左边界 - 1 就是答案
• 对于样例 [1, 4, 9, 2, 8, 7, 3, 5, 6]，设置树状数组的原数组全为 0
• 再依次将值为 1,2,3,4... 的下标位置 +1，原数组变化过程为：[1,0,0,0,0,0,0,0,0] -> [1,0,0,1,0,0,0,0,0] -> [1,0,0,1,0,0,1,0,0] ...... 这样操作
• 当操作到要询问位置时就计算答案
• 所以询问的位置要根据 p[c] 的大小从小到大排序

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int MOD=1e9+7;

int T,n,m;
int lowbit(int x)
{
	return x & -x;
}

//加数
void add(vector<int>& t, int idx, int val)// [index, n, index += lowbit(index) )这些位置都要加上
{
	while(idx<=n)
	{
		t[idx]+=val;
		idx+=lowbit(idx);
	}
}

//[1, index] 的前缀和
int presum(vector<int>& t, int x)
{				
	int res=0;
	while(x>0)
	{
		res+=t[x];
		x-=lowbit(x);// x = x - lowbit(x) 作为步长
	}
	return res;
}

void solve(){
	cin>>n>>m;
	vector<int> p(n+1,0),t(n+1,0);
	for(int i=1;i<=n;i++)cin>>p[i];
	vector<array<int,4>> v(m);
	for(int i=0,l,r,c;i<m;i++)
	{
		cin>>l>>r>>c;
		v[i]={l,r,c,i};
	}
	sort(v.begin(),v.end(),[&](const array<int,4>& x, const array<int,4>& y){return p[x[2]]<p[y[2]];});//依据 下标对应的值排序
	vector<int> ans(m),rev(n+1);
	for(int i=1;i<=n;i++)rev[p[i]]=i;//反向索引
	for(int i=1,j=0,cur=p[v[0][2]];i<=n && j<m;i++)
	{
		add(t,rev[i],1);//rev[i] 位置加 1
		while(cur==i && j<m)//注意防止越界
		{
			auto [l,r,c,idx]=v[j++];
			int cnt=presum(t,r)-presum(t,l-1);//cnt 表示 [l,r] 区间有多少个小于等于 p[c] 的数
			ans[idx]=l+cnt-1;//用第二个样例模拟一下就得到这个公式了
			if(j<m)//注意防止越界
				cur=p[v[j][2]];
		}
	}
	for(int i:ans)
		cout<<i<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	T=1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}