【luogu P3709 大爷的字符串题】题解

题目链接：https://www.luogu.org/problemnew/show/P3709

离散化+区间众数..？

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn = 500000+10;

inline int read()

{

    int k=0;

    char c;

    c=getchar();

    while(!isdigit(c))c=getchar();

    while(isdigit(c)){k=(k<<3)+(k<<1)+c-'0';c=getchar();}

    return k;

}

int n, m, a[maxn], ans[maxn], cnt[maxn], bl, curL = 1, curR = 0, answer = 0, b[maxn], tot, sum[maxn];

struct query{

	int l, r, p;

}e[maxn];

bool cmp(query a, query b)

{

	return (a.l/bl) == (b.l/bl) ? a.r < b.r : a.l < b.l;

}

void add(int pos)

{

	sum[cnt[a[pos]]]--;

	cnt[a[pos]]++;

	sum[cnt[a[pos]]]++;

	answer = max(answer, cnt[a[pos]]);

}

void remove(int pos)

{

	sum[cnt[a[pos]]]--;

	cnt[a[pos]]--;

	sum[cnt[a[pos]]]++;

	while(!sum[answer]) answer--;

}

int main()

{

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

	bl = sqrt(n);

	for(int i = 1; i <= n; i++)

	a[i] = b[++tot] = read();

	sort(b+1, b+1+tot);

	tot = unique(b+1, b+1+tot)-b-1;

	for(int i = 1; i <= n; i++)

	a[i] = lower_bound(b+1,b+1+tot,a[i])-b;//离散化 

	for(int i = 1; i <= m; i++)

	{

		e[i].l = read(); e[i].r = read(); e[i].p = i;

	}

	sort(e+1, e+1+m, cmp);

	for(int i = 1; i <= m; i++)

	{

		int L = e[i].l, R = e[i].r;

		while(curL < L) remove(curL++);

		while(curL > L) add(--curL);

		while(curR < R) add(++curR);

		while(curR > R) remove(curR--);

		ans[e[i].p] = answer;

	}

	for(int i = 1; i <= m; i++)

	printf("%d\n",0-ans[i]);

	return 0;

}

/*

7 5

52 1 52 52 1000000000 1000000000 1000000000

1 3

1 2

1 6

2 5

2 2

*/

巴特西

【luogu P3709 大爷的字符串题】题解

最新文章

热门文章

巴特西

【luogu P3709 大爷的字符串题】 题解

最新文章

热门文章

【luogu P3709 大爷的字符串题】题解