BOJ 17731 | Historical Research

일본어는 할 줄 모르지만 구글 번역기의 힘을 빌려 읽어냈다.

#23238 문제와 비슷하지만 여기서는 최빈값이 아닌 $x×cnt[x]$가 최대여야 한다.

큰 틀은 #23238과 동일하게 풀었다.

이 문제는 시간제한이 4초라 넉넉하기 때문에 마치 제곱근 분할이 정해인 것처럼 느껴진다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define lint long long
#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) cout
#define endl '\n'

struct Query{
	int l, r;
	int idx;
};

int n, m;
vector<lint> oarr;
vector<lint> arr;
vector<lint> zip;
vector<Query> q;
lint maxvaule = -1;

const int SZ = 100; // size of bucket
const int SQ = 111111 / SZ + 15; // bucket quantity

lint bucketmax[SQ][SQ];
lint bucketmaxcnt;
lint bmax;
lint bucket_cnt[100001];
lint ans[100001];

vector<vector<int>> studentidx;

void arrayclear(lint (&a)[100001]){
	for (lint &i : a){
		i = 0;
	}
}

void preprocessing(){	
	for (int k = 0; k * SZ < n; k++){
		bucketmaxcnt = 0;
		bmax = 0;
		arrayclear(bucket_cnt);
		for (int i = k*SZ; i <= n; i++){
			if (i == 0) continue;
			
			lint t = arr[i];
			bucket_cnt[t]++;
			if (zip[t] * bucket_cnt[t] > zip[bmax] * bucketmaxcnt){ // important
				bmax = t;
				bucketmaxcnt = bucket_cnt[t];
			}
			
			if (i % SZ == SZ-1 || i == n){ // Succession
				bucketmax[k][i/SZ+1] = bmax;
			}
		}
	}
}

bool _cmp(Query a, Query b){
	int al = a.l / SZ;
	int bl = b.l / SZ;
	
	if (al != bl) return al < bl;
	return a.r < b.r;
}

int findzip(int x){
	return lower_bound(zip.begin(), zip.end(), x) - zip.begin();
}


int main(){
	FASTIO;
	oarr.resize(100001);
	arr.resize(100001);
	studentidx.resize(100001);
	
	#ifdef LOCAL
	ifstream cin("02-02.txt");
	ofstream cout("result.ans");
	#endif
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		int t; cin >> t;
		oarr[i] = t;
		zip.push_back(t);
	}
	
	sort(zip.begin(), zip.end());
	zip.erase(unique(zip.begin(), zip.end()), zip.end());
	
	for (int i = 1; i <= n; i++){
		arr[i] = findzip(oarr[i]);
		studentidx[arr[i]].push_back(i);
	} // compression
	
	preprocessing();
	
	for (int i = 0; i < m; i++){
		int l, r; cin >> l >> r;
		q.push_back({l, r, i});
	}
	
	//sort(q.begin(), q.end(), _cmp);
	
	for (int i = 0; i < m; i++){
		int l = q[i].l, r = q[i].r;
		int idx = q[i].idx;
		lint ret = 0;
		
		if (l / SZ == r / SZ) { // same bucket
			for (int i = l; i <= r; i++){
				int t = upper_bound(studentidx[arr[i]].begin(), studentidx[arr[i]].end(), r) - lower_bound(studentidx[arr[i]].begin(), studentidx[arr[i]].end(), l);
				ret = max(ret, zip[arr[i]] * t);
			}
		}
		else{
			vector<int> doubt;
			int lp = (l/SZ) + 1;
			if (l % SZ == 0) lp--;
			
			for (int i = l; i < (lp)*SZ; i++){
				doubt.push_back(arr[i]);
			}
			doubt.push_back( bucketmax[lp][r/SZ] );
			
			for (int i = r; i >= (r/SZ)*SZ; i--){
				doubt.push_back(arr[i]);
			}
			
			
			for (auto &i : doubt){
				int t = upper_bound(studentidx[i].begin(), studentidx[i].end(), r) - lower_bound(studentidx[i].begin(), studentidx[i].end(), l);
				ret = max(ret, zip[i] * t);
			}
			
		}
		
		ans[idx] = ret;
	}
	
	for (int i = 0; i < m; i++){
        cout << ans[i] << endl;
    }
	
}