自动搬运

查看原文

来自洛谷，原作者为

	钰瑾_恋涵 菜死了

搬运于2025-08-24 22:30:57，当前版本为作者最后更新于2022-02-11 10:59:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：普通莫队

前言：

熟悉的区间询问，熟悉的数据范围。嗯？好！上莫队！

由于本人做这道题时是初学莫队，根本不知道还有值域分块这种东西，好像所有的莫队都可值域分块，其他大佬的题解里要么用了主席树和整体二分 ( 蒟蒻太弱啦，根本不会！) ，要么都是值域分块莫队，所以这里给出一种普通莫队的做法。

想要 $\Theta (1)$ 转移当前答案看起来不太可做，但我们考虑答案在什么情况才会改变。

• k 表当前答案，sum 表后缀和。

1. 当 sum[k+1] > k ：k + 1 。

2. 当 sum[k] < k : k - 1 。

根据这两个性质，我们可以开一个桶维护每个数的出现次数，再用一个数维护大于等于 k 的数有多少个。在每次增 / 删数时检查是否需要更改答案就行了。在每次询问结束后更新答案也行。

然后就做到 $\Theta(1)$ 转移和查询答案啦！

最后附上代码:

#include <bits/stdc++.h>
using namespace std;
int read() {
	int x=0; char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x;
}
void put(int x) {
	if(x>=10) put(x/10);
	putchar(x%10^48);
}
const int Maxn=2e5+10;
int n,q,unit,a[Maxn],cnt[Maxn],ans[Maxn];
struct node {
	int l,r,id;
	bool operator<(const node &b) const {
		if(l/unit!=b.l/unit) return l<b.l;
		return l/unit&1?r<b.r:r>b.r;
	}
} ask[Maxn];
signed main() {
	n=read(),q=read(),unit=sqrt(n);
	for(register int i=1; i<=n; ++i) a[i]=read();
	for(register int i=1; i<=q; ++i) ask[i].l=read(),ask[i].r=read(),ask[i].id=i;
	sort(ask+1,ask+q+1);
	register int l=ask[1].l,r=ask[1].l-1,k=0,t=0;
	for(register int i=1; i<=q; ++i) {
		while(l>ask[i].l) ++cnt[a[--l]],t+=(a[l]>=k);
		while(r<ask[i].r) ++cnt[a[++r]],t+=(a[r]>=k);
		while(l<ask[i].l) t-=(a[l]>=k),--cnt[a[l++]];
		while(r>ask[i].r) t-=(a[r]>=k),--cnt[a[r--]];
		while(t-cnt[k]>k) t-=cnt[k++];
		while(t<k) t+=cnt[--k]; 
		ans[ask[i].id]=k;
	}
	for(register int i=1;i<=q;++i) put(ans[i]),putchar('\n');
	return 0;
}