问题出在第一个二分的边界和第一个二分套的二分的边界上：

a 数组是原数组，b 数组是排序后第 j 块的数字。

代码:

#define int long long

const int ma=1e5+5;

int a[ma],b[ma],bel[ma],Left[ma],Right[ma];

int n,m;

inline void updata(int x,int k)
{
	int pos=lower_bound(b+Left[bel[x]],b+Right[bel[x]]+1,a[x])-b;

	a[x]=k,b[pos]=k;

	sort(b+Left[bel[x]],b+Right[bel[x]]+1);
}

inline int binary(int p,int k)
{
	int l=Left[p],r=Right[p];

	while(l<=r)
	{
		int mid=(l+r)>>1;

		if(b[mid]>k)
		{
			r=mid;
		}

		else
		{
			l=mid+1;
		}
	}

	return l;
}

inline int cnt(int l,int r,int num)//num 在区间 [l,r] 内是否是第 k 小
{
	int tmp=0;

	if(bel[l]==bel[r])
	{
		for(register int i=l;i<=r;i++)
		{
			if(num>a[i])
			{
				tmp++;
			}
		}
	}

	else
	{
		for(register int i=l;i<=Right[bel[l]];i++)
		{
			if(num>a[i])
			{
				tmp++;
			}
		}

		for(register int i=Left[bel[r]];i<=r;i++)
		{
			if(num>a[i])
			{
				tmp++;
			}
		}

		for(register int i=bel[l]+1;i<bel[r];i++)
		{
			int now=binary(i,num);

			while(now>Left[i] && b[now-1]==b[now])//找到最前面的
			{
				now--;
			}

			tmp+=now-Left[i];
		}
	}

	return tmp;
}

inline int query(int le,int ri,int k)
{
	int l=1,r=1e9;

	while(l+1<r)//二分第 k 小的数 mid
	{
		int mid=(l+r)>>1;

		if(cnt(le,ri,mid)>=k)
		{
			l=mid;
		}

		else
		{
			r=mid;
		}
	}

	return l;
}

#undef int

int main(void)
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif

	#define int long long

	n=read(),m=read();

	for(register int i=1;i<=n;i++)
	{
		a[i]=b[i]=read();
	}

	int len=sqrt(n),num=ceil((double)(n)/(double)(len));

	for(register int i=1;i<=num;i++)
	{
		Left[i]=(i-1)*len+1;

		Right[i]=i*len;
	}

	Right[num]=n;

	for(register int i=1;i<=num;i++)
	{
		for(register int j=Left[i];j<=Right[i];j++)
		{
			bel[j]=i;
		}
	}

	for(register int i=1;i<=num;i++)
	{
		sort(b+Left[i],b+Right[i]+1);
	}

	for(register int i=1;i<=num;i++)
	{
		printf("i = %lld,Left = %lld,Right = %lld\n",i,Left[i],Right[i]);
	}

	for(register int i=1;i<=m;i++)
	{
		char opt[3];

		scanf("%s",opt);

		if(opt[0]=='Q')
		{
			int l=read(),r=read(),k=read();

			printf("%lld\n",query(l,r,k));
		}

		else
		{
			int x=read(),k=read();

			updata(x,k);
		}
	}

	return 0;
}

---

第一个二分

正确的：

//区间 [le,ri] 找第 k 小
inline int query(int le,int ri,int k)
{
	int l=1,r=1e9;

	while(l+1<r)//二分第 k 小的数 mid
	{
		int mid=(l+r)>>1;

		if(cnt(le,ri,mid)>=k)//统计区间 [le,ri] 比 mid 小的数的个数。
		{
			l=mid;
		}

		else
		{
			r=mid;
		}
	}

	return l;
}

错误的：

//区间 [le,ri] 找第 k 小
inline int query(int le,int ri,int k)
{
	int l=1,r=1e9;

	while(l+1<r)//二分第 k 小的数 mid
	{
		int mid=(l+r)>>1;

		if(cnt(le,ri,mid)>=k)//统计区间 [le,ri] 比 mid 小的数的个数。
		{
			r=mid;
		}

		else
		{
			l=mid;
		}
	}

	return l;
}

inline int query(int le,int ri,int k) { int l=1,r=1e9;

while(l<r)//二分第 k 小的数 mid
{
	int mid=(l+r)>>1;

	if(cnt(le,ri,mid)>=k)
	{
		r=mid;
	}

	else
	{
		l=mid+1;
	}
}

return l;

}

第二个二分：

正确的：
```cpp
inline int binary(int p,int num)
{
	int l=Left[p],r=Right[p];

	while(l<=r)
	{
		int mid=(l+r)>>1;

		if(b[mid]>num)
		{
			r=mid-1;
		}

		else if(b[mid]<num)
		{
			l=mid+1;
		}

		else
		{
			l=mid;

			break;
		}
	}

	return l;
}

错误的：

//求 b 数组中区间 [Left[p],Right[p]] 中 k 的位置
inline int binary(int p,int k)
{
	int l=Left[p],r=Right[p];

	while(l<r)
	{
		int mid=(l+r)>>1;

		if(b[mid]>=k)
		{
			r=mid;
		}

		else
		{
			l=mid;
		}
	}

	return l;
}

---

问题：

欲将二分边界变为 while(l<r) 该如何写？