yukicoder : No.956 Number of Unbalanced

これはなんとか自力で解けた。
https://yukicoder.me/problems/no/956

問題

N要素の整数列が与えられる。
この部分列のうち、ある数値が過半数を占めるようなものは何通りか。

解法

過半数を占める値は1つなので、各値についてそれが過半数を占める部分列を求めよう。

平方分割で解く。
例えば登場頻度がD以下の数値に関しては、それが過半数を占める場合高々長さが(2D-1)である。
よって、長さ(2D-1)以下の部分列は総当たりしよう。
D=√Nにしておけばこの手順はO(N√N)で済む。

次に登場頻度がDより大きなものを考える。
ある1種類が過半数となる部分列は、1個当たり累積和でO(N)またはBITでO(NlogN)でとれる。
(対象の値を1、それ以外を-1と置き、部分和が正になるものを数え上げる。)

そのような値はN/D個以下なので、合わせてO(N√NlogN)程度で済む。

int N;
int A[101010];
int num[101010];
int C[101010];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,18> bt;

const int SQ=500;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		num[A[i]]++;
	}
	
	ll ret=0;
	FOR(x,N) {
		int ma=0;
		FOR(i,SQ*2) if(x+i<N) {
			if(num[A[x+i]]<SQ) {
				C[A[x+i]]++;
				ma=max(ma,C[A[x+i]]);
			}
			if(ma*2>i+1) ret++;
		}
		FOR(i,SQ*2) if(x+i<N && num[A[x+i]]<SQ) C[A[x+i]]--;
	}
	
	FOR(i,100100) if(num[i]>=SQ) {
		int cur=1<<17;
		bt.add(cur,1);
		FOR(x,N) {
			if(A[x]==i) cur++;
			else cur--;
			ret+=bt(cur-1);
			bt.add(cur,1);
		}
		cur=1<<17;
		bt.add(cur,-1);
		FOR(x,N) {
			if(A[x]==i) cur++;
			else cur--;
			bt.add(cur,-1);
		}
	}
	
	
	
	
	cout<<ret<<endl;
}

まとめ

最大値とかorみたいな演算だと平方分割を使うことが多い気がする。