莫队+树状数组/主席树

Just h-index

本题可以二分答案，假设二分的答案为$mid$,区间长度为$len$。

• 如果区间大于$mid$的数个数大于等于$mid$个，那么这个$mid$就是满足的。
• 也可以这样理解：如果该区间第 $len-mid+1$大的数$>=mid$，那么$mid$也是满足的。

对于第一个我们可以用莫队+树状数组解决。第二个就是求解区间第$K$大的模板了，利用主席树。
主席树比莫队快了$1000+ms!$

主席树

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include<cmath>
#include<functional>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
struct tree{
	int lc, rc, cnt;
}T[N<<5];
int n, m,tot,rm;
int a[N],root[N];
void build(int &rt,int l, int r)
{
	rt = ++tot;
	if (l < r)
	{
		int mid = (l + r) >> 1;
		build(T[rt].lc, l, mid);
		build(T[rt].rc, mid + 1, r);
	}
}
void update(int &cur, int pre, int l, int r, int pos)
{
	cur = ++tot;
	T[cur] = T[pre];
	T[cur].cnt++;
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (pos <= mid) update(T[cur].lc, T[pre].lc, l, mid, pos);
	else update(T[cur].rc, T[pre].rc, mid + 1, r, pos);
}
int query(int x, int y, int l, int r, int k)
{
	if (l == r) return l;
	int s = T[T[y].lc].cnt - T[T[x].lc].cnt;
	int mid = (l + r) >> 1;
	if (k <= s)
		return query(T[x].lc, T[y].lc, l, mid, k);
	else
		return query(T[x].rc, T[y].rc, mid + 1, r, k - s);
}
int solve(int l, int r)
{
	int s = r - l + 1;
	int L = 1, R = s;
	while (L < R)
	{
		int mid = (L + R+1) >> 1;
		int k = query(root[l - 1], root[r], 1, rm, s - mid + 1);
		if (k >= mid) L = mid;
		else R = mid - 1;
	}
	return L;
}
int main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		tot = 0;
		rm = -1;
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			rm = max(rm, a[i]);
		}
		//build(root[0], 1, rm);
		for (int i = 1; i <= n; i++)
			update(root[i], root[i - 1], 1, rm, a[i]);
		for (int i = 1; i <= m; i++)
		{
			int l, r;
			scanf("%d%d", &l, &r);
			printf("%d\n",solve(l, r));
		}
	}
	return 0;
}

莫队+树状数组

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long 
using namespace std; 
#define lowbit(x) (x&(-x))
const int N = 1e5+10;
int b[N],Ans[N];
int c[N], a[N];
int g[N];
int n, m,block,tot, ans;
int  k;
int l, r;
struct query{
	int id, l, r;
}q[N];
bool cmp1(query o1, query o2)
{
	if (b[o1.l] == b[o2.l]) 
		return o1.r < o2.r; 
	return o1.l < o2.l;
}
void update(int pos,int val)
{
	for (; pos <= n; pos += lowbit(pos))
		c[pos] += val;
}
int ask(int pos)
{
	int res=0;
	for (; pos; pos -= lowbit(pos))
		res += c[pos];
	return res;
}
int solve()
{
	int cnt = r - l + 1;
	int L = 1, R = cnt;
	while (L < R)
	{
		int mid = (L + R+1) >> 1;
		if (cnt - ask(mid - 1) >= mid) L = mid;
		else R = mid - 1;
	}
	 return L;
}
void Mo()
{
	l = 1, r = 0;
	for (int i = 1; i <= m; i++)
	{
		while (r < q[i].r) update(a[++r],1);
		while (r> q[i].r)  update(a[r--], -1);
		while (l < q[i].l) update(a[l++], -1);
		while (l>q[i].l) update(a[--l], 1);
		Ans[q[i].id] = solve();
	}
	for (int i = 1; i <= m; i++)
		printf("%d\n", Ans[i]);
}
int main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		block = sqrt(n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			b[i] = (i - 1) / block + 1;
			c[i] = 0;
		}
		for (int i = 1; i <= m; i++)
		{
			scanf("%d%d", &q[i].l, &q[i].r);
			q[i].id = i;
		}
		sort(q + 1, q + m + 1, cmp1);
		Mo();
	}
	return 0;
}