백준 소스코드 [C++] 6515 Frequent values

www.acmicpc.net/problem/6515

6515번: Frequent values

백준 소스코드 [C++] 6515 Frequent values

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
typedef long long ll;
using namespace std;
int n, m,sqrtn;
int arr[100001];
int cnt[200001];
int table[200001];
int maxcount=0;
void add(int a) {
	if (table[cnt[a]] != 0) table[cnt[a]]--;
	cnt[a]++;
	table[cnt[a]]++;
	maxcount = max(maxcount, cnt[a]);
}

void sub(int a) {
	table[cnt[a]]--;
	if (maxcount == cnt[a] && table[cnt[a]] == 0) maxcount--;
	cnt[a]--;
	table[cnt[a]]++;
}

struct query {
	int idx, i, j;
};
bool compare(query& x,query& y) {
	if (x.i / sqrtn != y.i / sqrtn) return x.i / sqrtn < y.i / sqrtn;
	return x.j < y.j;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	while (true) {
		maxcount = 0;
		cin >> m;
		sqrtn = (int)sqrt(n);
		memset(arr, 0, sizeof(arr));
		memset(cnt, 0, sizeof(cnt));
		memset(table, 0, sizeof(table));
		int val;
		for (int i = 0;i < n;i++) {
			cin >> val;
			arr[i] = val + 100000;
		}
		vector<query> q(m);
		vector<int>res(m);
		int x, y;
		for (int a = 0;a < m;a++) {
			cin >> x >> y;
			q[a] = { a,x - 1,y - 1 };
		}

		sort(q.begin(), q.end(), compare);

		int s = q[0].i, e = q[0].j;
		for (int a = s;a <= e;a++) add(arr[a]);
		res[q[0].idx] = maxcount;

		for (int a = 1;a < m;a++) {
			while (q[a].i < s)add(arr[--s]);
			while (q[a].j > e)add(arr[++e]);
			while (q[a].i > s)sub(arr[s++]);
			while (q[a].j < e)sub(arr[e--]);
			res[q[a].idx] = maxcount;
		}
		for (int i = 0;i < m;i++)  cout << res[i] << '\n';
		cin >> n;
		
		if (n == 0) break;
	}
	return 0;
}