LeetCode Weekly Contest 149 : 1157. Online Majority Element In Subarray

9ptでびっくりしていたけどどうにかなった。
https://leetcode.com/contest/weekly-contest-149/problems/online-majority-element-in-subarray/

問題

N要素の整数列が与えられる。
以下のクエリ計Q個に順次答えよ。

• 整数列の区間が指定される。その中に現れる数値で、T回以上の頻度の物があればそれを答えよ。
• なお、Tは区間長の半分超なので、該当する数値は高々1個である。

解法

平方分割でいいのかな。
登場頻度が多いものと低いものに分けて考える。
まず、元の数列で登場頻度が多い(√N程度)値を先に列挙しておく。

これらについて、前処理として区間内の登場頻度を高速に計算できるよう累積和を取っておこう。
ここまででO(N√N)である。

以後、各クエリに対し以下を行う。

• Tが√N未満なら、区間の長さも2T未満で大したことないので、愚直に区間内の要素の頻度をカウントする。
• Tが√N以上なら、先ほど列挙した登場頻度が高い値について、前処理で求めた累積和を使い区間内の登場回数を求める。

全体でO((N+Q)√N)で解ける。

int N;
int A[20202];
vector<int> B;
int C[20202];
int S[20202][202];

class MajorityChecker {
public:
    MajorityChecker(vector<int>& arr) {
		int i,x;
		ZERO(C);
		ZERO(S);
		N=arr.size();
		FOR(i,N) {
			A[i]=arr[i];
			C[A[i]]++;
		}
		B.clear();
		FOR(i,20002) if(C[i]>100) B.push_back(i);
		ZERO(C);
		
		FOR(i,B.size()) {
			FOR(x,N) {
				S[x+1][i]=S[x][i];
				if(A[x]==B[i]) S[x+1][i]++;
			}
		}
		
		
        
    }
    
    int query(int left, int right, int threshold) {
		int ret=-1;
        if(threshold>100) {
			int i;
			FOR(i,B.size()) {
				if(S[right+1][i]-S[left][i]>=threshold) ret=B[i];
			}
		}
		else {
			int i;
			for(i=left;i<=right;i++) {
				C[A[i]]++;
				if(C[A[i]]>=threshold) ret=A[i];
			}
			for(i=left;i<=right;i++) C[A[i]]--;
		}
        return ret;
    }
};

まとめ

ポイントをぼちぼちTシャツに交換しようかな。