TopCoder SRM 735 Div2 Hard MajoritySubarray

これも気づくと実装は簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=14932

問題

N要素の数列Aが与えられる。
各要素はm未満の非負整数である。

この数列の連続した部分列のうち、１つの値が過半数を占めるようなものはいくつあるか。

解法

mが小さいので、0≦x＜mである個々のxに対し、xが過半数となるものがいくつあるかを求めてみよう。
元のAを以下のように書き換える。
B[i] := A[i]=xなら1,そうでないなら-1

すると、Aの部分列においてxが過半数を占める＝Bの(同じ要素からなる)部分列において総和が正である、と言い換えることができる。あとは累積和とBIT等を使い数え上げていけばO(Nm*logN)程度で解ける。

int N;
int A[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,20> bt;

class MajoritySubarray {
	public:
	long long getCount(int n, int seed, int m) {
		int i,j;
		FOR(i,n) {
			A[i]= (seed>>16)%m;
			seed = ((ll)seed * 1103515245 + 12345) & ((1LL<<31)-1);
		}
		ll ret=0;
		FOR(i,m) {
			ZERO(bt.bit);
			int cur=1<<18;
			FOR(j,n) {
				bt.add(cur,1);
				if(A[j]==i) cur++;
				else cur--;
				ret+=bt(cur-1);
			}
		}
		return ret;
		
		
	}
}

まとめ

一瞬頭抱えたけど、mが小さいことに気づいたらすんなり。